Решатель судоку с грубой силой: возвращение назад? - PullRequest
Новая
       15

Решатель судоку с грубой силой: возвращение назад?

3 голосов
/ 23 июля 2010

Реализация алгоритма грубой силы для решения головоломок судоку завершается неудачей, если обнаружена ячейка, в которой размещение любой из цифр 1-9 будет недопустимым ходом.

реализация написана на C, с платой, представленной массивом 9x9.Солвер рассчитывает обратный отсчет от 9 до достижения допустимого числа, и если ни один не может быть достигнут, он выводит ноль на своем месте.

Ноль также представляет ячейку, которая должна быть заполнена. Вот вывод (усеченный)если строка нулей (пустая доска) является входной: 

9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0

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

Ответы [ 3 ]

2 голосов
/ 23 июля 2010

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

Например,в вашем примере: 

9 8 7 6 5 4 3 2 1
6 5 4 9 8 7 0 0 0

Вместо того, чтобы ставить ноль ниже трех, вы вместо этого вернетесь назад и попытаетесь поставить 6 ниже 4.

1 голос
/ 23 июля 2010

Вы можете сделать это, поместив ваши догадки в стек.Каждый раз, когда вы захотите вывести ноль, вместо этого вытолкните свой последний ответ с доски и продолжайте считать с него.

Так что, если вы угадаете 3 в (2,3), а затем смотрите (3,3) и доберитесь до нуля, вернитесь к (2,3) и попробуйте 2, затем 1, затем нажмите перед вашим (2,3) предположением и т. Д.

1 голос
/ 23 июля 2010

не относитесь к каждому «движению» как к правильному. Например. размещение последних 7 показалось нормальным, но делает так, чтобы в следующей ячейке не осталось никаких действительных ходов. Поэтому, попав в ситуацию «невозможно двигаться», вернитесь назад и попробуйте следующий вариант. Повторите, и у вас будет решение.

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

9 8 7 6 5 4 3 2 1
6 5 4 0 0 0 0 0 0
3 2 1 0 0 0 0 0 0

что законно, без возврата назад.

...