Задачу судоку обычно составляют так: сначала создают доску с ответом, а потом стирают цифры. Приложение NumberPlace тоже каждый раз составляет задачу на месте этим способом. Расскажем, как это делается.

1. Создаём решённую доску

Сначала создаём одну решённую доску, которая подчиняется правилам. Начиная с левой верхней клетки, выбираем и ставим одну подходящую цифру. Если встретилась клетка, в которую не подходит ни одна цифра, возвращаемся на клетку назад и пробуем другую (поиск идёт с возвратами, поэтому его называют перебором с возвратом, backtracking).

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

112233445566778899349567182516842793872391645185239476724615839693478521458123967931786254267954318

2. Стираем цифры симметрично относительно центра

Дальше стираем цифры. В приложении мы стираем их, составляя пары из двух клеток, расположенных напротив друг друга относительно центра доски. Поэтому расположение цифр в готовой задаче не меняется, если повернуть доску на 180 градусов (симметрия относительно центра).

112233445566778899351822982914529672418396485512973726748

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

3. После каждого стирания проверяем, «решается ли приёмами»

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

Приёмы — это способы, в которых используют только то, что можно сказать наверняка: «сюда подходит только эта цифра» и «сюда эта цифра не подходит». Если задачу удалось решить до конца одними приёмами, другого ответа быть не может. То есть у задачи, которая решается приёмами, решение одно (почему у судоку одно решение).

4. Подбираем сложность под ★

Сложность ★ определяется самым трудным приёмом, который нужен для решения. Для каждой ★ приложение задаёт предел приёмов, которые можно использовать, и стирает цифры, пока задача решается только ими.

  • В ★1 используется только «цифра подходит только сюда», в ★2 добавляется «сюда подходит только эта цифра», в ★3 — запертые кандидаты и пары, а в ★4 и ★5 — сложные приёмы, такие как X-Wing и XY-Wing.
  • В ★1 и ★2 стирание прекращают, когда начальных цифр осталось столько, сколько нужно. Если стереть всё, что можно, задача станет слишком трудной.
  • Если получившаяся задача не подходит под условия ★ (нужные приёмы и число начальных цифр), её составляют заново из решённой доски.

При обычном составлении задачи, где нужны сложные приёмы, получаются нечасто (самое трудное судоку в мире). Поэтому задачу ★5 составляют заново до 500 раз, пока она не подойдёт. Даже так на компьютере в среднем уходит около 0,13 секунды. На смартфоне это может занять больше времени, поэтому приложение, пока вы играете, заранее составляет следующую задачу в фоновом режиме.

Если хотите составить задачу сами

Если составлять задачу на бумаге, так будет меньше ошибок.

  1. Запишите решённую доску (удобно взять ответ готовой задачи и переименовать в нём цифры).
  2. Понемногу стирайте цифры.
  3. После каждого стирания сами решайте задачу и проверяйте, можно ли решить её до конца, используя только клетки, у которых есть причина.
  4. Если где-то понадобилось гадание, верните последнюю стёртую цифру.

Даже если просто переименовать цифры (например, поменять местами все 1 и 2), получится задача, которая выглядит иначе.