sudoku solver

решатель судоку

Простой решатель головоломок судоку, написанный на PHP.

ПРИМЕЧАНИЕ. Этот проект все еще находится в стадии разработки.

Установка

Запустите следующую команду в корне проекта, чтобы установить sudoku-solver.

 composer install

Терминология

 Square      One of the m x n values on the puzzle board
Row         Horizontal M squares
Column      Vertical N squares
Region      An m x n subset of squares
Group       M/N number of squares in a row (horizontally or vertically) 

Стратегии решения головоломок

Стратегии, используемые этим решателем, основаны на стратегиях, описанных в Sudoku Dragon.

Стратегии

Стратегии следует применять неоднократно, пока головоломка не будет решена.

1. Единственное правило выбора

   • Просканируйте каждую строку, столбец и регион на предмет одного варианта в группе.

2. Правило единственной возможности

   • Просканируйте каждую пересекающуюся строку и столбец в поисках единственного варианта в группе.

3. Только квадратное правило

   • Сканируйте каждую строку/столбец с двумя пустыми ячейками.
   • Назовите два недостающих числа: А и В.
   • Просканируйте каждую пересекающуюся строку, столбец или область и попытайтесь исключить вариант А.
   • Если вариант А можно исключить для определенной ячейки, заполните в этой ячейке вариант Б.
   • Заполните вариант А в другой пустой ячейке.

4. Правило двух из трех

   • Сверху вниз сканируйте три строки или столбца за раз в поисках определенного числа, начиная с 1.

5. Правило исключения подгруппы

   • TODO

6. Грубая сила

   • Пробуйте все варианты, пока не будет найдено решение :)

Ресурсы

• https://www.educative.io/edpresso/how-to-check-if-a-sudoku-board-is-valid
• https://puzzling.stackexchange.com/questions/158/how-many-minimal-clue-sudoku-puzzles-are-there
• https://www.technologyreview.com/s/426554/mathematicians-solve-minimum-sudoku-problem/