Решите судоку, используя итеративный поиск в ширину
У меня есть задача решить судоку с использованием итеративного алгоритма поиска в ширину, но я изо всех сил пытаюсь применить этот алгоритм именно к этой проблеме.
Я понял, что мне нужна очередь, и я должен перебирать эту очередь, пока она не станет пустой.
У меня есть следующий алгоритм для проверки значения, соответствует ли оно конкретной ячейке в какой-то момент:
- Убедитесь, что таких значений нет в строке.
- Убедитесь, что в столбце нет таких значений.
- Убедитесь, что в блоке нет таких значений.
Но когда я продолжаю работать с таким алгоритмом, в какой-то момент мне приходится вернуться и изменить ранее выбранное значение, потому что оно может оказаться неправильным.
Как я могу применить поиск с возвратом с помощью BFS к этой проблеме судоку?
Ответы 1
В BFS нет необходимости в возврате. Вместо этого BFS предоставляет вам множество параллельных путей. Если окажется, что один путь ведет к несогласованной сетке, он просто умирает. Единственное, что нужно сделать, это ничего не делать с ним, т. е. не помещать следующее полученное из него состояние в очередь, как вы обычно делаете.
Сам обход BFS можно организовать несколькими способами, но вот как он может выглядеть:
Первоначально очередь начинается с исходного состояния сетки. Затем повторяйте следующие шаги до тех пор, пока очередь не пуста и в ней еще есть свободные ячейки:
- Удалить состояние сетки из очереди.
- Возьмите следующую свободную ячейку.
- Определите, какие значения может получить эта свободная ячейка, не нарушая ни одно из перечисленных вами правил.
- Создайте состояние сетки для каждого из них и поставьте их в очередь.
Ветвь "умирает", когда третий шаг маркера дает возможные значения нет. В этом случае следующий шаг ничего не ставит в очередь, чего вы и хотите. Неверный путь устранен. Цикл продолжится и будет рассматривать другие альтернативные сетки, которые могут присутствовать в очереди.
Добавил некоторые пояснения.
Привет @trincot. Большое спасибо за ответ. Я немного смущен вашим ответом. Как я должен использовать очередь здесь? Потому что я думал, что я должен взять все соседние ячейки с текущей ячейкой, у которых в настоящее время нет номера, и поместить их в очередь. Можете ли вы пояснить, как должна выглядеть вся идея алгоритма (шаг за шагом)?