Головоломка - матрица

[jangle]

Попалось мне такая задачка, никак не могу понять как ее решить. Есть матрица 3 x 3 , клетки которой заполнены числами от 1 до 9. При этом, напротив каждой строки и столбца написана сумма всех чисел в клетках. Нужно вписать в клетки такие числа, чтобы сумма в каждой строке и столбце совпадала. Какой алгоритм решения этой задачи?

[Debugger]

Если 3 на 3, с числами от 1 до 9, то можно брутфорс.

[jangle]

Если 3 на 3, с числами от 1 до 9, то можно брутфорс.

Брутфорс это понятно. Но может есть какой-то алгоритм? Что-то связанное с магическими квадратами и прочей фигней.

[jangle]

Вот моя попытка угадать числа в клетках. Сошлись все строки и столбцы кроме последнего столбца.

Мне думается матрицу можно представить в виде следующего выражения:

- обозначим все клетки

X1 X2 X3
X4 X5 X6
X7 X8 X9

Получается уравнение:

X1 + X2 + X3 = 15
X4 + X5 + X6 = 8
X7 + X8 + X9 = 20

X1 + X4 + X7 = 13
X2 + X5 + X8 = 18
X3 + X6 + X9 = 11

И что дальше? Только брутфорс?

[Antonariy]

Вот моя попытка угадать числа в клетках.

Epic fail.

клетки которой заполнены числами от 1 до 9

[jangle]

Epic fail.

Блин точно! Мозги закипели и стали глючить.

[Antonariy]

Для начала можно решить задачу попроще: у нас 5 нечетных и 4 четных числа, нужно расставить их так, чтобы совпала четность сумм.
Даже в таком виде решить не получается, нет ли ошибки в условиях?

[jangle]

Для начала можно решить задачу попроще: у нас 5 нечетных и 4 четных числа, нужно расставить их так, чтобы совпала четность сумм.
Даже в таком виде решить не получается, нет ли ошибки в условиях?

С условием вроде все правильно. Не понял про четность сумм. Это что такое?
Как мне кажется, в первую строку и первый столбец можно ставить любые числа, лишь бы совпала нужная сумма.
А брутфорс делать в оставшихся 4 клетках.

[Antonariy]

С условием вроде все правильно.

Не факт. Числа от 1 до 9 с возможностью повтора или без? Если без, то второй вариант тоже не катит

Не понял про четность сумм. Это что такое?

Первая строка = 15, это нечетная сумма, она = 3*нечет или 2*нечет+1*чет или 1*нечет+2 нечет.
Соответственно четная сумма = 3*чет или 2*нечет+1*чет. Допустим, что нечет = true.

[jangle]

Не факт. Числа от 1 до 9 с возможностью повтора или без? Если без, то второй вариант тоже не катит

Да цифры с возможностью повтора. Это не магический квадрат.

[Debugger]

Брутфорс говорит, что в условии ошибка.
Если бы вместо 11 было бы 12, то решений было бы много.

[jangle]

Брутфорс говорит, что в условии ошибка.
Если бы вместо 11 было бы 12, то решений было бы много.

А код брутфорсера можешь выложить?

[iGrok]

Да, в условии ошибка.
15 + 8 + 20 = 43
13 + 18 + 11 = 42

А решать.. Считай, что это вырожденная СЛАУ:
1x1 + 1x2 + 1x3 + 0x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 = 15
0x1 + 0x2 + 0x3 + 1x4 + 1x5 + 1x6 + 0x7 + 0x8 + 0x9 = 8
0x1 + 0x2 + 0x3 + 0x4 + 0x5 + 0x6 + 1x7 + 1x8 + 1x9 = 20
1x1 + 0x2 + 0x3 + 1x4 + 0x5 + 0x6 + 1x7 + 0x8 + 0x9 = 13
0x1 + 1x2 + 0x3 + 0x4 + 1x5 + 0x6 + 0x7 + 1x8 + 0x9 = 18
0x1 + 0x2 + 1x3 + 0x4 + 0x5 + 1x6 + 0x7 + 0x8 + 1x9 = 11

Методов решения СЛАУ науке известно немало. Я не парился, и по быстрому нашёл вот это: http://matri-tri-ca.narod.ru/slu.html

При данных условиях:
"Ранг расширенной матрицы системы не равен рангу матрицы системы => система несовместна(не имеет решений)."

Если вместо 11 будет 12:
"Ранг расшеренной матрицы равен рангу матрицы системы, но меньше числа неизвестных => система совместна и имеет бесконечно много решений."
x1=-15+c1+c2+c3+c4; x2=18-c1-c3; x3=12-c2-c4; x4=8-c1-c2; x5=c1; x6=c2; x7=20-c3-c4; x8=c3; x9=c4;

Остаётся добавить условие - 0 < xn < 10, и прогонять через него подходящие решения.

[Debugger]

А код брутфорсера можешь выложить?

Да, конечно.

Puzzle.rar

(1.18 Кб) Скачиваний: 71

[Proxy]

А это разве не есть классический Японский кроссворд? Помнится была такая игра, даже книжки с такими играми продавались на железнодорожных вокзалах. Сборники Судоку + Японские кроссворды. Возможно если порешать штук 10, то и алгоритм толковый какой-нибудь будет найден.
И да, 3х3 пожалуй проще и быстрее всего брутфорсом, имхо, там не столь уж и много вариантов: 387420489.

[Debugger]

А это разве не есть классический Японский кроссворд? Помнится была такая игра, даже книжки с такими играми продавались на железнодорожных вокзалах. Сборники Судоку + Японские кроссворды. Возможно если порешать штук 10, то и алгоритм толковый какой-нибудь будет найден.

Нет, в этих кроссвордах несколько иные правила.

И да, 3х3 пожалуй проще и быстрее всего брутфорсом, имхо, там не столь уж и много вариантов: 387420489.

Если перебирать ячейки 11,12,21 и 22, то остальные можно определить автоматически (по сумме). Если вычисленные ячейки попадают под условие (т.е. от 1 до 9), то паззл решен.
Получается "всего-то" 6561 вариантов (9*9*9*9). Ручками не перебрать, но для ПК - самое то.

[jangle]

А это разве не есть классический Японский кроссворд?

Вряд ли. Это задание мне дали на собеседовании в одной крутой конторе. Задачу я не решил, собеседование провалил, но вопрос как это решается остался

[iGrok]

Это задание мне дали на собеседовании в одной крутой конторе. Задачу я не решил, собеседование провалил, но вопрос как это решается остался

Это задание решается за 20 секунд. Проверяются общие суммы по краям, и проверяющему выдаётся ответ, который они от тебя и ждали - "задача решения не имеет".

Вот если суммы совпадают - тогда труднее. Можно либо через СЛАУ, либо примерно перебором, задействуя внимательность и интуицию.