Судоку — вроде бы простая игра, знакомая большинству людей. Он имеет сетку девять на девять, разделенную на девять «коробок» три на три. Ее логическая природа всегда интриговала меня, и поэтому я решил попробовать сделать свою собственную игру в судоку — это не может быть так сложно, подумал я.

Прежде чем я мог приступить к написанию пользовательского интерфейса для своего приложения, мне сначала понадобилась действующая сетка судоку для представления игроку. У меня оставалось два варианта: либо мне пришлось создавать свои собственные сетки, либо я мог использовать API для извлечения сеток. Простой поиск в Google выдаст несколько API судоку. Тем не менее, я решил продолжить свой прежний выбор — я хотел генерировать собственные сетки.

Когда вы решаете сетку судоку, вам нужно следовать только одному правилу:

  • Каждая цифра должна встречаться один раз в каждой строке, столбце или поле — никаких дубликатов.

Вот и все.

Однако, когда вы создаете сетку судоку, есть и другое правило:

  • Сетка должна иметь ровно одно решение, не больше и не меньше.

Имея это в виду, я начал планировать.

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

Мои усилия не были напрасными, так как для этого решения я создал метод is_valid(x,y,n,grid), который проверяет, допустима ли данная цифра в сетке, который я также использовал в своем окончательном решении.

Меня отправили обратно к чертежной доске. Я по-прежнему хотел использовать случайные цифры, иначе каждый раз получалась бы одна и та же головоломка. Но случайные цифры означали, что в какой-то момент он, скорее всего, застрянет, как и в случае с наивным подходом. Если алгоритм застрял, он должен был иметь возможность вернуться к точке, прежде чем он застрял, и вместо этого продолжить оттуда.
Я начал думать о том, как бы я решил сетку судоку, если бы я не не умеет пользоваться логикой. Я, вероятно, начал бы просто вводить правильные цифры, пока не достигал бы точки, когда игра становилась неразрешимой, и в этот момент я бы стирал цифры, пока не смог бы продолжить.

Мне нужно было посмотреть на проблему рекурсивно, и поэтому я получил что-то вроде этого:

  1. Выберите квадрат для заполнения
  2. Выберите цифру для указанного квадрата
  3. Если игра становится неразрешимой, удаляйте расставленные цифры до тех пор, пока она не станет разрешимой.

Сначала мне нужно было выяснить, какой квадрат я хочу, чтобы алгоритм заполнил первым. Я мог бы просто случайным образом выбрать квадрат, но я хотел свести к минимуму количество раз, которое алгоритму нужно было откатить. Выбирая квадрат с наименьшим количеством допустимых цифр, я ограничил шансы случайного выбора цифры, которая в какой-то момент помешала бы алгоритму закончить сетку. Чтобы найти лучший квадрат, я просто создал вложенный цикл for, чтобы проверить все 9 цифр во всех незаполненных квадратах, а затем сравнил цифры квадрата с текущим «лучшим» квадратом.

Вы могли заметить, что помимо координат lowestX и lowestY и возможного количества кандидатов в текущем лучшем квадрате lowestLength есть четвертая переменная lowestCandidates. Это используется для завершения шага 2 моего плана: выбор цифры для указанного квадрата. lowestCandidates — это массив, и любая цифра в этом массиве должна работать. Однако всегда использовать только первую цифру означало бы, что алгоритм может застрять в бесконечном цикле безуспешных попыток использовать одни и те же цифры снова и снова. Вместо этого алгоритм случайным образом выбирает допустимого кандидата из массива и вставляет его в квадрат. После того, как число заполнено, весь метод можно вызвать снова, на этот раз с еще одной цифрой, уже находящейся в сетке — повторять полоскание до тех пор, пока сетка не будет либо полной, либо неразрешимой. Если в какой-то момент метод «завершил» генерацию, а сетка не была завершена, алгоритм просто помечает последний заполненный квадрат как незаполненный и повторяет попытку.

Та-да! 🎉
Готовая, действующая сетка судоку. Ну наконец то.

Теперь, когда у меня была готовая сетка, мне просто нужен был код, удаляющий некоторые цифры, чтобы сетка стала играбельной. Это оказалось гораздо проще, чем генерировать сетку. Квадрат, из которого удаляется цифра, может быть выбран случайным образом и путем проверки количества возможных решений сетки с помощью вспомогательного метода (этот метод очень похож на метод, первоначально использовавшийся для создания сетки, вдохновленный для этого из Компьютерофильское видео). Сохранив резервную копию цифры, удаленной из сетки, ее можно было бы просто повторно вставить в квадрат на случай, если сетка больше недействительна (если существует более одного возможного решения). В большинстве случаев это давало хорошие головоломки судоку, но иногда алгоритм возвращал почти заполненную сетку судоку, потому что он удалял цифру, которая делала сетку недействительной в начале цикла. Чтобы обойти это, я позволил алгоритму иметь 10 попыток удаления цифр, каждый раз, когда сетка становилась недействительной, он повторно вставлял цифру и уменьшал переменную попыток до тех пор, пока не осталось попыток.

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

Заключение

Имея готовый алгоритм, который достаточно быстро создает головоломки (в среднем около 160 мс для готовой сетки, а также для частично заполненной сетки, готовой к представлению игроку), я был удовлетворен. Теперь мне просто нужно было представить сетку игроку, чего я добился с помощью простой html-таблицы, а также некоторого приятного JavaScript, в который я не буду вдаваться. Я также реализовал ведение заметок, что, как мне кажется, необходимо в игре судоку. Наконец, поскольку я чувствовал, что в игре не хватает награды за то, что игрок заканчивал игру, я сделал так, чтобы приложение сразу начинало играть в Never Gonna Give You Up Рика Эстли с YouTube после правильного заполнения сетки — мне было очень весело, рик- катая моих друзей таким образом.