Енциклопедія судоку · Математика й обчислення

Математика судоку

Оновлено 2026-10-05

Латинський квадрат із блоками

У латинському квадраті кожен символ трапляється по одному разу в кожному рядку та кожному стовпці. Заповнене судоку є латинським квадратом розміру 9 із ще однією умовою: кожен із дев’яти блоків 3×3 також містить кожну цифру по одному разу.

Джерела: Wikipedia: Latin square

Скільки існує сіток

Бертрам Фельґенгауер (Bertram Felgenhauer) і Фрейзер Джарвіс (Frazer Jarvis) підрахували заповнені сітки 9×9 у 2005 році: їх 6 670 903 752 021 072 936 960, приблизно 6,67 × 10²¹. Багато з них є тією самою сіткою в іншому вигляді. Якщо вважати дві сітки однією, коли одну можна перетворити на іншу заміною позначень цифр, обертанням чи віддзеркаленням або переставлянням рядків і стовпців способами, що зберігають правильність сітки, залишиться 5 472 730 538 суттєво різних сіток. Це число обчислили Ед Расселл (Ed Russell) і Фрейзер Джарвіс.

Джерела: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Мінімум 17 заданих цифр

Жодне стандартне судоку 9×9 із 16 або меншою кількістю заданих цифр не має рівно одного розв’язку. Ґері Макґвайр (Gary McGuire), Бастіан Туґеманн (Bastian Tugemann) і Жиль Сіваріо (Gilles Civario) показали це за допомогою вичерпного комп’ютерного перебору та оголосили результат у січні 2012 року. Сімнадцять є мінімумом, а не гарантією: багато сіток із 17 заданими цифрами все одно мають більше ніж один розв’язок.

Джерела: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Судоку як розфарбування графа

Намалюй по одній вершині для кожної з 81 клітинки та з’єднай дві вершини, якщо їхні клітинки належать до спільного рядка, стовпця або блока. Цей граф судоку має 810 ребер, а кожна вершина має рівно 20 сусідів. Розв’язати головоломку означає доповнити розфарбування, визначене заданими цифрами, так, щоб з’єднані вершини ніколи не мали однакового кольору. Потрібно щонайменше дев’ять кольорів, оскільки кожен рядок, стовпець і блок є групою з дев’яти попарно з’єднаних вершин, а будь-яка заповнена сітка показує, що дев’яти достатньо.

Джерела: Wikipedia: Sudoku graph

Складно в загальному випадку, швидко для 9×9

Для сіток судоку, розмір яких може необмежено зростати (n²×n² із блоками n×n), задача визначення, чи можна дозаповнити частково заповнену сітку, є NP-повною. Цей результат Такаюкі Ято (Takayuki Yato) і Такахіро Сета (Takahiro Seta) опублікували 2003 року. Ефективні комп’ютерні програми зазвичай розв’язують звичайні головоломки 9×9 за частку секунди, хоча час залежить від програми, комп’ютера та головоломки.

Джерела: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Дивись також

Джерела

Усі статті →