Создание ЭФФЕКТИВНОГО Решателя Судоку

Question

Да, я знаю, что в этом нет ничего нового, и уже есть много вопросов (у него даже есть свой собственный тег), но я хотел бы создать Soloku Solver на Java исключительно для обучения себя написанию кода. это более эффективно.

Вероятно, самый простой способ сделать это в программе - это иметь массу циклов for, которые анализируют каждый столбец и строку, собирают возможные значения каждой ячейки, а затем отсеивают ячейки только с одной возможностью (независимо от того, содержат ли они только 1). число, или они являются единственной ячейкой в ​​своей строке / столбце, которая содержит это число), пока у вас не будет решена головоломка. Конечно, сама мысль о действии должна поднять красный флаг в голове каждого программиста.

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

Я хочу избегать математических алгоритмов, если это вообще возможно - это было бы слишком просто, и 100% не моя работа.

Если бы кто-то мог предоставить пошаговый, эффективный мыслительный процесс для решения головоломки Судоку (будь то человек или компьютер), я был бы очень счастлив :). Я ищу что-то расплывчатое (так что это вызов), но достаточно информативное (чтобы я не совсем растерялся), чтобы начать.

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

Юстиан Мейер

EDIT:

Глядя на мой код, я задумался: каковы будут некоторые возможности для сохранения этих решающих состояний (то есть сетки Судоку). 2D-массивы и 3D-массивы приходят на ум. Что может быть лучше? 2D может быть проще в управлении с поверхности, но 3D Arrays также предоставит номер "box" / "cage".

EDIT:

Nevermind. Я собираюсь пойти с 3D-массивом.

Answer 1

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

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

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

http://www.byteauthor.com/2010/08/sudoku-solver/

Answer 2

Если кому-то понадобится эталонная реализация Android, я написал решение, которое использует алгоритм из поста выше.

Полный код с открытым исходным кодом здесь: https://github.com/bizz84/SudokuSolver

Кроме того, это решение загружает головоломки Sudoku в формате JSON с веб-сервера и публикует результаты.

Answer 3

Это зависит от того, как вы определяете эффективность.

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

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

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

Вы можете использовать логический / математический метод, при котором ваш код пробует разные стратегии, пока головоломка не будет решена.Ищите в Google «стратегии судоку», чтобы увидеть разные стратегии.Используя логические / математические методы, ваш код может «объяснить», как была решена головоломка.

Answer 4

Вам следует подумать о том, чтобы свести проблему Судоку к проблеме SATisfiability .

Этот метод позволит вам не думать слишком mathematically, но больше logically об ИИ.

Цель шаг за шагом в основном:

* Find all the constraints that a Sudoku has. (line, column, box).
* Write these constraints as boolean constraints.
* Put all these constraints in a Boolean Satisfiability Problem.
* Run a SAT solver (or write your own ;) ) on this problem.
* Transform the SAT solution into the solution of the initial Sudoku.

Это было сделано Айвором Спенсом с использованием SAT4J , и вы можете найти Java-апплет его работы здесь: http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

Вы также можете напрямую загрузить код Java с веб-сайта SAT4J, чтобы увидеть, как он выглядит: http://sat4j.org/products.php#sudoku.

И, наконец, большое преимущество этого метода заключается в следующем: вы можете решить N*N Sudokus, а не только типичный 9*9, что, на мой взгляд, намного сложнее для ИИ:).