Решение головоломки с древовидной структурой данных

Question

В настоящее время я слежу за классом алгоритмов, и мы должны решить судоку.

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

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

Я не ищу оптимизации. Я искал объяснения по таким алгоритмам, как Генетический алгоритм или что-то подобное. Моя цель только учиться на этом этапе. Мне трудно взять то, что я прочитал в научных статьях, и перевести это на реальную реализацию.

Надеюсь, я разъяснил свой вопрос.

Большое спасибо!

РЕДАКТИРОВАТЬ: я редактировать сообщение, чтобы быть более точным.

Answer 1

Как и в большинстве задач поиска, также в Судоку вы можете связать дерево с проблемой.В этом случае узлы являются частичными присвоениями переменных, а ветви соответствуют расширениям присваивания в родительском узле.Однако хранить эти деревья в памяти не практично (или даже нереально), вы можете рассматривать их как концептуальный инструмент.Возврат фактически перемещается по такому дереву, используя переменное упорядочение, чтобы избежать исследования безнадежных ветвей.Лучшее (более быстрое) решение может быть получено с помощью методов распространения ограничений, поскольку известно, что все строки, столбцы и ячейки 3x3 должны содержать разные значения.Простым алгоритмом для этого является AC3, и он рассматривается в большинстве вводных книг по искусственному интеллекту, включая Russell & Norvig 2010 .

Answer 2

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