Как сделать судоку

Алгоритм генерации судоку

Доброго времени суток!

Думаю, головоломка Судоку не нуждается в представлении. Многие из нас проводят за её решением достаточно много времени. Например, когда нужно убить время в дороге или просто поворочать мозги, чтобы не сохли. На хабре есть довольно много постов о решении головоломки. Но когда человек решает с десяток, а может и сотню головоломок, то найдётся пытливый ум, который задаст себе вопрос «А как же получается таблица Судоку, имеющая единственное решение? И как можно описать алгоритм для сетки 9×9?».

Приведённый алгоритм является вполне логичным. Но моей задачей было описание и реализация. Обо всём этом написано под катом.

1. Цифра может появиться только один раз в каждой строчке
2. Цифра может появиться только один раз в каждом столбике
3. Цифра может появиться только один раз в каждом районе (Район — меньший квадрат со стороной 3х3, на изображении ниже выделен фиолетовым цветом)

Шаг 1. Взять за основу базовую сетку

Сетка должна подчинятся правилам Судоку. Размещаем в первую строку 1 2… 8 9, в строках ниже смещаем на 3 позиции влево, т.е. 4 5… 2 3 и 7 8… 5 6.
Далее переходя в следующий район по вертикали смещаем на 1 позицию влево предыдущий район.

В итоге должна получиться вот такая сетка, её я и назову базовой:

Для реализации создадим класс grid. Заполним его в соответствии с Шагом 1, в котором table — список значений таблицы, метод show — просто наглядный вывод таблицы.

Шаг 2. Перетасовать сетку

Есть несколько видов перестановок, выполнив которые таблица Судоку останется в допустимом состоянии.
К ним относятся:

• Транспонирование всей таблицы — столбцы становятся строками и наоборот (transposing)

• Обмен двух строк в пределах одного района (swap_rows_small)
• Обмен двух столбцов в пределах одного района (swap_colums_small)

• Обмен двух районов по горизонтали (swap_rows_area)
• Обмен двух районов по вертикали (swap_colums_area)

Для каждой из перестановок напишем метод:

transposing

swap_rows_small

swap_colums_small

Для обмена столбцов можно поменять строки у транспонированной таблицы:

swap_rows_area

swap_colums_area

Может быть есть ещё более сложные преобразования, но, думаю, можно ограничиться этими. Этот каркас инвариантен своей структуре, такие перестановки есть почти тоже самое, что и действия над матрицами относительно определителя или вращение Кубика Рубика.

Теперь, для того чтобы получить случайную комбинацию, достаточно запустить в случайном порядке функции перемешивания. Так и поступим, amt — количество перемешиваний:

Шаг 3. Удаление клеток

После полученного решения нам необходимо получить задачу (именно в такой последовательности мы можем гарантировать однозначность решения). И это самая сложная часть. Какое количество можно убрать, чтобы гарантировать однозначность решения? Это один из важных факторов, от которого зависит сложность Судоку. Всего в Судоку 81 клетка, обычно считают лёгким когда на поле есть 30-35 «подсказок», средним — 25-30, и сложным — 20-25. Это данные большого набора реальных примеров. Нет никаких законов для сложности. Можно сделать 30-клеточный неразрешимый вариант и 22 клеточный «лёгкий».

• Случайный подход — можно попробовать выкинуть 50-60 клеток наугад, но где вероятность что Судоку можно будет решить? Например, если заполнены 3 строки ( = 27 клеток)
• Случайно с простым ограничением — для примера можно взять некое число N в качестве предела, так что N строк и столбцов могут быть пустыми. Принимая N = 0 — для лёгких уровней, N=1 — средний, N=2 — сложный

1. Выбрать случайную ячейку N
2. Отметить N просмотренной
3. Удалить N
4. Посчитать решения. Если оно не единственное, то вернуть N обратно

Я уверен, что есть и более сложные подходы в построении таблицы Судоку. Моя цель была достигнута, получился рабочий алгоритм. Теперь мне не нужно искать новые выпуски, я могу их генерировать 🙂
В принципе, здесь был приведён частный случай Судоку 9х9. Но нет ограничений для использования его на 16х16 и 25х25.

Судоку своими руками

Хочу рассказать вам, дорогие читатели блога, об одной своей программке на Icon, о которой очень хотелось рассказать когда-то давно (еще в 2016 году), но тогда не хватало времени, чтобы описать свой игровой эксперимент. Так уж сложилось, что самое интересное, что я делаю на Icon — это игры, и данный случай — не исключение.

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

Итак, начнем с того, что такое судоку.

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

Вот так выглядит обычное поле для игры в судоку:

Правила судоку интуитивно просты и понятны: нужно заполнить все игровое поле цифрами от 1 до 9 таким образом, чтобы цифры в строке или столбце не повторялись, при этом также важен тот факт, что в квадратах 3 на 3, также не должно быть повторяющихся цифр. Поскольку, на поле уже присутствуют некоторые из цифр, то располагая этой информацией и необходимо поставить недостающие (согласно описанным правилам), и таким образом осуществить решение самой головоломки.

Теперь можно приступить к реализации задуманного…

Для построения судоку нам необходимо создать саму сетку и разместить в ней некоторым образом цифры, сгенерировав их абсолютно случайным образом:

Работают эти процедуры так: сначала с помощью процедуры grid, мы в окне программы просто чертим серую сетку из 81 квадрата (т.е. делаем обычное игровое поле, размером 9 на 9); затем с помощью процедуры square мы выделяем жирными черными линиями 9 квадратов размером 3 на 3 (т.е. разделяем игровое поле на несколько крупных квадратов, согласно правилам судоку); далее используя вспомогательную процедуру lremove для удаления из списка n-ого элемента реализуем необходимую нам далее процедуру r_str, которая формирует одну строку нашего судоку и которая пригодиться нам далее.

Теперь, начинается самое интересное: создание алгоритма построения судоку из одной строки случайно сгенерированных неповторяющихся цифр (вот зачем нам процедура r_str).

Алгоритм построения судоку после очень долгих раздумий получился таким: сначала мы берем строку случайных цифр, а затем создаем из нее 8 оставшихся строк с помощью сдвига самой строки на некоторые фиксированные значения сдвига вправо (данные значения были найдены в ходе долгих поисков по интернету и некоторых экспериментов), затем все 9 строк из цифр мы размещаем на игровом поле, после чего случайным образом стираем некоторое количество цифр (количество цифр определено экспериментально).

Реализация соответственно будет такой:

Также нам потребуется создание списка, который будет хранить решение головоломки, поэтому создаем глобальную переменную с пустым списком solv и создаем процедуру рисования всех 9 строк пока без удаления из них цифр:

Процедура удаления цифр также весьма проста:

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

Если вспомнить наши предыдущие статьи по созданию всяких мелких игрушек на Icon, то процедуры осуществления хода и его отмены выглядят весьма банально, а изменяется только привязка к конкретным координатам в окне:

Объединим теперь все это в одну программу, собрав все процедуры и импорты в основную процедуру:

Итак, пользователь делает ход, щелкнув левой клавишей мыши по интересующей его клетке и осуществив вод нужной цифры, отмена хода осуществляется щелчком правой клавишей мыши по неправильно поставленной цифре (защита от дурака, к сожалению, не предусмотрена, поскольку писалось все, как говорится, на коленке); а отображение правильного решения осуществляется по нажатию клавиши s.

Это выглядит так:

Подводя итоги, скажу, что мой папа очень был доволен тем, что получил в свои руки классную минималистическую игрушку, за которой он может отдохнуть от работы, однако, для себя я вынес следующую мораль: не стоит писать код в таком стиле, даже если программа делается за один вечер, а необходимо детально вникнуть в проблему и создать качественный код, поскольку внезапно может выясниться, что исходник программы всплывает через несколько лет…

Как я могу генерировать головоломки Судоку?

Я пытаюсь сделать генератор головоломок судоку. Это намного сложнее, чем я ожидал, и чем больше я увлекаюсь этим, тем сложнее становится!

Мой текущий подход состоит в том, чтобы разбить проблему на 2 этапа:

1. Создайте полную (решенную) головоломку судоку.
2. Удалите числа до тех пор, пока они не будут решены и у них будет только 1 решение

На шаге 1, так как я использую методы грубой силы, я сталкиваюсь с некоторыми проблемами во время выполнения. Есть ли оптимальный способ заполнить полную головоломку судоку?

На шаге 2, какой алгоритм я должен использовать, чтобы «озадачить» решенную судоку?

У меня самая продаваемая игра Судоку в магазине приложений для iOS. Вот как я генерировал головоломки.

Сначала у меня есть приложение-генератор головоломок. Но это не часть кода игры. Это отдельное приложение, которое я использую для создания головоломок. Он сильно модифицирован, поэтому я могу настроить его для создания различных типов паттернов, рейтингов сложности, количества подарков и т. Д. Генерировать головоломки и получать постоянный уровень сложности сложно на лету, и это займет больше времени, чем игрок хотел бы ждать. Итак, я генерирую то, что я называю «начальными головоломками», и именно это используется кодом игры для генерации головоломок, в которые играют люди.

Я не отвечаю, как кодировать генератор здесь. Вы можете гуглить и найти тонны кода генератора головоломок онлайн. Начни там. Но чтобы сделать хорошую игру, нужно сделать хорошую игру. Моя игра не генерирует головоломки на лету.

Моё приложение-генератор головоломок работает так, что оно генерирует тысячи головоломок в минуту, но они не все хороши и не все соответствуют определенному уровню сложности. Генератор создает головоломку, затем решает ее, вычисляет рейтинг сложности и оценивает головоломку на основе методов, необходимых для ее решения, и определяет, требуется ли угадывание для ее решения (что обычно плохо). Он выбрасывает любые головоломки, которые не соответствуют критериям. Для сложных, но не невозможных головоломок на быстрой машине может потребоваться час, чтобы создать 100 головоломок, которые точно соответствуют моим требованиям. Вот почему я не делаю это в приложении. Создание головоломок на лету с этими жесткими характеристиками не сработает для того качества головоломок, которое есть в моем приложении.

Головоломки — это строки длиной 162 символа, 81 символ с цифрами и тире или точками, где должны быть пробелы, а затем еще 81 с решением. Затем столбцы для каждой статистики, например, сколько синглов, пар и т. Д.

Мой вывод из всех сеансов генерации — это разделенные запятыми строки со статистикой в ​​виде столбцов. Я возьму, может быть, 10 000 головоломок, принесу их, чтобы преуспеть, и рассортирую их по сложности. Затем внесите их в приложение, чтобы увидеть их на игровом поле. Я также смотрю на них для визуальной привлекательности и видимых образцов для загадки. Тогда я вручную выбираю из них.

Я называю их загадками семян и вот что я имею в виду. Числа в игре судоку на самом деле просто жетоны. Вместо цифр 1-9 они могут быть цветами, символами или буквами. Так что мои загадки с семенами — это не цифры, а буквы ai. Каждая головоломка с семенами меняется на лету, чтобы создать играбельную головоломку:

1. Перемешать числа / токены. Когда я превращаю буквы ai обратно в числа 1-9, таблица поиска рандомизируется. Это означает, что a не всегда 1. Это само по себе создает около 300 000 вариаций для каждой головоломки.
2. Поверните головоломку на 90, 180 или 270 градусов. Это добавляет еще 4 варианта.
3. Флоп головоломки по горизонтали, вертикали или оба. Это добавляет еще 4 варианта.

Следовательно, каждая начальная головоломка может создать 5 806 080 вариаций. Я проверил это на поле с реальными игроками. Люди не знают, что они играют в одну и ту же головоломку. На самом деле это невозможно. Только если они заметят, что шаблон, в котором даны, одинаков каждый раз. Но даже с 100 различными семенами никто не заметит. Миллион пользователей моей игры не имеет. Я также проверил это с решающими приложениями. Приложение решателя не решит головоломку так же, как при повороте или провале. Иногда он даже анализирует его как другой уровень сложности, хотя технически это та же головоломка.

Тем не менее, книга Big Bad Sudoku Book содержит 10 из 1000 головоломок с семенами на 5 уровнях сложности и несколько типов головоломок. Это значит, что в моей игре миллиарды головоломок. С каждыми 10 000 загадками семян есть 58 060 800 000 различных загадок.

В Книге Судоку версии 4 (выйдет в 2016 году) я нашел способ уточнить точную головоломку из этих 58 миллиардов и получить такую ​​же головоломку на устройстве каждого игрока.