Построение ЭФФЕКТИВНОГО решения Sudoku

Question

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

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

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

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

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

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

Жюстьян Meyer

EDIT:

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

EDIT:

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

Answer 1

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

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

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

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

Answer 4

Вы должны подумать о том, чтобы уменьшить проблему Судоку до SATisfiability problem.

Этот метод позволит избежать слишком мыслить 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. 

Это было сделано с помощью Ivor SpenceSAT4J и вы можете найти Java Applet его работы здесь: http://www.cs.qub.ac.uk/~I.Spence/SuDoku/SuDoku.html.

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

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