Решение судоку только для строк и столбцов

Если у вас 9 строк, то это 9 строк, как в судоку, но вместо этого они похожи на

530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

Который превращается в

534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Я думал, что это будет проще, но потом, когда я вставил его в свою программу, он оставил огромные пробелы.

Я думал, что могу просто пройтись по каждому столбцу и поместить наименьшее число в свободное место в первом столбце, если оно не мешает ни одному из других чисел, но по мере продвижения я понял, что мне нужно вернуться и удалить определенные номера, чтобы сделать его лучше.

Имейте в виду, что единственные применимые условия заключаются в том, что числа в одном столбце не могут быть одинаковыми, а числа в одной строке не могут быть одинаковыми, но нет полей.

Любой совет?


person keyerer    schedule 04.10.2012    source источник


Ответы (2)


Сначала определите все возможные числа для каждой ячейки, учитывая только ячейки, заполненные на этот ход. Если какая-либо ячейка имеет только одно возможное число, выберите ее и повторно оцените затронутые ячейки (в той же строке, столбце и квадрате 3x3).

Когда вы больше не можете найти ячейку только с одной возможностью, используйте рекурсивный поиск с возвратом.

person Lee Louviere    schedule 04.10.2012
comment
Для большинства средних и простых решений вам вообще не понадобится рекурсивный возврат. - person Lee Louviere; 04.10.2012