Блог за чашечкой

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

Ну и ладно. Были игры и поинтереснее...

Ага, щас. Прошло несколько лет, а старое поражение никак не давало мне покоя. Тогда я учил Питон и написал свой первый решатель Судоку. Работал он примерно так:

1. Найди все пустые ячейки.
2. Напиши в каждую ячейку все числа от 1 до 9.
3. В каждой ячейке зачеркни все числа, которые повторяются в столбце, строке или квадрате.
4. Если осталось одно число, запиши его как единственное подходящее.
5. Вернись к пункту 1.

Случайные судоку из интернета я победил. Но с парочкой алгоритм не справлялся, сколько бы раз я ни запускал проверку. Оставалось 4 пустых ячейки:

123 457 689

456 8*9 3*7

789 3*6 4*5

И тут пришло откровение: у некоторых судоку больше одного решения. В трех квадратах выше 4 пустых ячейки: впиши 1–2, 2–1 или 2–1, 1–2, оба решения будут верными. Алгоритм обзавелся еще одним пунктом: если ничего не удается поставить — ставь наугад и отталкивайся от этого.

Вперед, бравый Питон! Сегодня ты победишь японского дракона...

А математики уже тогда всё решили. В 2012 Гэри Макгвайр (привет русскому уху и Гарри Магуайру) с коллегами посчитали количество возможных партий в Судоку ≈6 700 000 000 000 000 000 000. Столько не решить.

Тогда они отбросили однотипные судоку и запустили компьютер, который год решал оставшиеся партии. Сегодня у Гэри на сайте красуется вывод: уникальное решение найдется, если в судоку больше 16 заполненных ячеек. Иначе решений будет несколько, придется ставить наугад.

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

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

Дракон оказался слабым и немощным. Вместо громкого рыка квакнул и крякнулся.

А я с тех пор не играю в судоку.