Как создать логическую игру из бумаги и карандаша, такую ​​как судоку?

Question

Этот вопрос не ограничивается судоку, но может включать в себя Какуро, Хитори, Нурикабе и т. Д. c.

Я понимаю алгоритм решения Судоку и другие подобные головоломки, но Мне трудно понять, как создать их.

Скажем, я хочу генератор Судоку (чтобы взять самый популярный). Я думаю, это должно работать в два этапа:

1. Создать правильное решение
2. Удалять части решения до тех пор, пока не останется нужное количество подсказок.

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

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

Существует ли обобщенный c алгоритм для его решения? Как я могу реализовать такую ​​вещь?

Я понимаю, что мой вопрос "широкий" и что я не показываю многое из того, что у меня есть (разделив проблему на две части), но я не понимаю нет никакого повода задуматься об алгоритме. Я не прошу решения, а скорее подсказки о том, как начать.

Answer 1

В общем случае вы можете подойти к этому следующим образом:

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

• Вызывать «поле влияния» данной ячейки, ячейки которой находятся либо в той же строке, либо в том же столбце, либо в тот же блок 3х3, что и в данной ячейке. Правило состоит в том, что эта ячейка не может иметь никаких значений, которые уже используются в ее области влияния. Если это означает, что осталось только одно действительное значение, поместите это значение в эту ячейку.

Другое правило может быть:

• Если есть значение, которое не может быть используется где-либо еще в том же блоке 3x3, затем поместите это значение в эту ячейку. Точно так же, если значение не может быть использовано где-либо еще в строке ячейки; или не может использоваться где-либо еще в столбце ячейки.

Очевидно, есть и другие правила. Эти правила могут быть более сложными. Оцените правила по тому, насколько трудно человеку проверить и применить их. Постарайтесь быть как можно полнее, глядя, как вы, как человек, рассуждаете при решении игры. Реализуйте эти правила как функции в программе. В примере с судоку такая функция правила может быть применена к заданной ячейке и возвращать успех (т. Е. Ячейка получает значение) или сбой (правило не может использоваться для вычитания ее значения).

Скажем так программа должна генерировать судоку заданной сложности. Мы интерпретируем это как означающее, что решение судоку потребует от игрока, по крайней мере, один раз использовать правило, которое имеет, по крайней мере, такую ​​сложность, или правило exoti c, которое никогда не было предусмотрено.

Теперь начните с решил судоку. Удалите случайным образом 50% значений. Проверьте, можно ли решить судоку, используя только известные правила, которые находятся в пределах уровня сложности. Если нет, восстановите 25% удаленных клеток и повторите. Если это можно решить, удалите на 25% больше клеток случайным образом. Продолжайте вдвое уменьшать количество задействованных ячеек (либо восстанавливая, либо удаляя их), подобно алгоритму двоичного поиска, пока не дойдете до конца этого поиска. Для игры в судоку этот процесс займет около 7 итераций. Тогда у вас будет своего рода «локальный минимум», где правила могут быть применены, чтобы найти решение.

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

Answer 2

Вы можете создать головоломку Судоку, решив одну из них, для которой ничего не назначено. Если ваш решатель прогрессирует, заполняя квадраты, вы можете «удалить» их, остановив (или откатив) этот процесс в соответствующей точке.