Есть ли формула для решения Судоку?
Последнее обновление
Нет формулы. Sudoku — это не математическая задача — это логическая головоломка, которая использует digits. Никакое уравнение или арифметическая формула напрямую не дает ответ. Что работает, так это систематическое constraint elimination.
Почему математика не решит это
Цифры 1-9 в судоку — это просто символы. Вы могли бы заменить их буквами или цветами, и головоломка была бы идентичной. Важна уникальность в блоках - Каждый символ появляется ровно один раз в каждой строке, столбце и блоке. Нет арифметической связи между ячейками, которую можно было бы использовать с помощью формулы.
Что на самом деле работает - Распространение ограничений
Судоку — это задача удовлетворения ограничений. Вы начинаете с 81 ячейки, каждая из которых ограничена своей строкой, столбцом и блоком. Размещение одной цифры распространяет новые ограничения - Эта цифра исключается из 20 других ячеек. Цепная реакция продолжается, пока головоломка не будет решена или не потребуется более сложная техника.
Иерархия техник, от простейшей к сложнейшей:
- Голые одиночки - Один кандидат остаётся в ячейке
- Скрытые одиночки - Одна позиция для цифры в блоке
- Голые и скрытые пары, тройки
- X-Wing, Swordfish
- Цепочки и многошаговая логика
Что компьютеры делают вместо этого
Computers решают Sudoku, используя backtracking search — Попробуйте digit, распространите constraints и отмените, если достигнута contradiction. Для humans это эквивалентно guessing, что не является ни удовлетворительным, ни поучительным. Human solving всегда предпочитает deductive techniques, которые гарантируют correctness без trial and error.