Я пытаюсь сделать генератор головоломок судоку. Это намного сложнее, чем я ожидал, и чем больше я увлекаюсь этим, тем сложнее становится!
Мой текущий подход состоит в том, чтобы разбить проблему на 2 этапа:
- Создайте полную (решенную) головоломку судоку.
- Удалите числа до тех пор, пока они не будут решены и у них будет только 1 решение
На шаге 1, так как я использую методы грубой силы, я сталкиваюсь с некоторыми проблемами во время выполнения. Есть ли оптимальный способ заполнить полную головоломку судоку?
На шаге 2, какой алгоритм я должен использовать, чтобы «озадачить» решенную судоку?
algorithm
puzzle
content-generation
user223150
источник
источник
Ответы:
У меня самая продаваемая игра Судоку в магазине приложений для iOS. Вот как я генерировал головоломки.
Сначала у меня есть приложение-генератор головоломок. Но это не часть кода игры. Это отдельное приложение, которое я использую для создания головоломок. Он сильно модифицирован, поэтому я могу настроить его для создания различных типов паттернов, рейтингов сложности, количества подарков и т. Д. Генерировать головоломки и получать постоянный уровень сложности сложно на лету, и это займет больше времени, чем игрок хотел бы ждать. Итак, я генерирую то, что я называю «начальными головоломками», и именно это используется кодом игры для генерации головоломок, в которые играют люди.
Я не отвечаю, как кодировать генератор здесь. Вы можете гуглить и найти тонны кода генератора головоломок онлайн. Начни там. Но чтобы сделать хорошую игру, нужно сделать хорошую игру. Моя игра не генерирует головоломки на лету.
Моё приложение-генератор головоломок работает так, что оно генерирует тысячи головоломок в минуту, но они не все хороши и не все соответствуют определенному уровню сложности. Генератор создает головоломку, затем решает ее, вычисляет рейтинг сложности и оценивает головоломку на основе методов, необходимых для ее решения, и определяет, требуется ли угадывание для ее решения (что обычно плохо). Он выбрасывает любые головоломки, которые не соответствуют критериям. Для сложных, но не невозможных головоломок на быстрой машине может потребоваться час, чтобы создать 100 головоломок, которые точно соответствуют моим требованиям. Вот почему я не делаю это в приложении. Создание головоломок на лету с этими жесткими характеристиками не сработает для того качества головоломок, которое есть в моем приложении.
Головоломки - это строки длиной 162 символа, 81 символ с цифрами и тире или точками, где должны быть пробелы, а затем еще 81 с решением. Затем столбцы для каждой статистики, например, сколько синглов, пар и т. Д.
Мой вывод из всех сеансов генерации - это разделенные запятыми строки со статистикой в виде столбцов. Я возьму, может быть, 10 000 головоломок, принесу их, чтобы преуспеть, и рассортирую их по сложности. Затем внесите их в приложение, чтобы увидеть их на игровом поле. Я также смотрю на них для визуальной привлекательности и видимых образцов для загадки. Тогда я вручную выбираю из них.
Я называю их загадками семян и вот что я имею в виду. Числа в игре судоку на самом деле просто жетоны. Вместо цифр 1-9 они могут быть цветами, символами или буквами. Так что мои загадки с семенами - это не цифры, а буквы ai. Каждая головоломка с семенами меняется на лету, чтобы создать играбельную головоломку:
Следовательно, каждая начальная головоломка может создать 5 806 080 вариаций. Я проверил это на поле с реальными игроками. Люди не знают, что они играют в одну и ту же головоломку. На самом деле это невозможно. Только если они заметят, что шаблон, в котором даны, одинаков каждый раз. Но даже с 100 различными семенами никто не заметит. Миллион пользователей моей игры не имеет. Я также проверил это с решающими приложениями. Приложение решателя не решит головоломку так же, как при повороте или провале. Иногда он даже анализирует его как другой уровень сложности, хотя технически это та же головоломка.
Тем не менее, книга Big Bad Sudoku Book содержит 10 из 1000 головоломок с семенами на 5 уровнях сложности и несколько типов головоломок. Это значит, что в моей игре миллиарды головоломок. С каждыми 10 000 загадками семян есть 58 060 800 000 различных загадок.
В Книге Судоку версии 4 (выйдет в 2016 году) я нашел способ уточнить точную головоломку из этих 58 миллиардов и получить такую же головоломку на устройстве каждого игрока.
источник
Существует простой способ заполнить полную головоломку судоку - заполнение группы и круговое смещение.
Чтобы пользователь не заметил очевидный шаблон, было бы неплохо рандомизировать порядок строк и столбцов, чтобы шаблон больше не существовал. До тех пор, пока все 9 чисел в каждой строке / столбце перемещаются вместе как одна атомная единица, доска Судоку всегда будет действительной.
Вы получаете полностью заполненную головоломку судоку. Для более подробной информации, вы можете искать "сделать судоку".
источник
Это не слишком сложно, при условии, что у вас есть решатель судоку.
Создание решателей судоку - сложная / интересная проблема, поэтому лучше сохранить ее для другого вопроса. Или вы можете просто прочитать это и посмотреть, как вы идете.
1, 2, 3, 4, ...
и выбрать первый, который работает. Вам нужно перетасовать этот порядок так , что он пытается, скажем,4, 7, 2, 9, ...
. Этот процесс должен быть таким же быстрым, как ваш решатель.Это очень простой (и наивный) метод, поэтому нет гарантии, что вы получите головоломки определенной сложности - помимо количества пропущенных чисел, которое есть - или даже если вы можете даже удалить желаемое количество чисел. Надеюсь, это поможет в любом случае.
источник
Я просто думаю, что интересно указать на эту веб-страницу , так как она очень помогла мне в разработке нашего проекта. Создание судоку с уникальным решением далеко от простой задачи. В ссылке вы можете найти, как автор (он действительно проделал большую работу, это не я, а!), Нашел несколько различных стратегий. У вас может быть идея создать свой собственный решатель судоку.
Теперь, перейдя к теме, есть также способ генерировать аналогичные судоку, просто
Ура и удачи с алгоритмом: D
источник
Мой решатель использует грубую силу и может найти решение в течение 20 миллисекунд. Используя метод удаления, описанный выше, мой генератор создает головоломку за 200 миллисекунд.
Обычно он генерирует головоломку с оставшимися 24-34 цифрами, и я до сих пор не знаю, как в мире им удается создать 17-значную головоломку.
источник