Как сгенерировать головоломку 5x5 sudoku?

Question

Я написал алгоритм для создания головоломок 5x5 sudoku. Вот как это работает. На моем сукку 5x5 есть только два противопоказания. В каждой строке и столбце может быть только один элемент.

1. Генерация случайных позиции (0,4)

2. Если позиция заполняется вернуться к 1.

3. Генерация случайного числа (1,5)

4. Если есть уже это число в строке или столбце вернуться к 3.

5. Заполнить позицию с номером

6. Если есть свободные места осталось вернуться к 1.

7. Удалить случайные числа.

Есть две основные проблемы.

1. Этот алгоритм генерации тупики, поэтому я проверить попыток, и если есть более 10 попыток, чтобы заполнить позицию сбросить все и попробовать еще раз.

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

Answer 1

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

Например, вы можете начать с этой сеткой, которая легко создавать, установив grid[i][j] в ((i + j) % 5) + 1:

1 2 3 4 5 
2 3 4 5 1 
3 4 5 1 2 
4 5 1 2 3 
5 1 2 3 4 

Затем, если поменять местами две строки, то все равно будет иметь действительную сетку, например, перестановка строк 1 и 3:

1 2 3 4 5 
4 5 1 2 3 < 
3 4 5 1 2 
2 3 4 5 1 < 
5 1 2 3 4 

Вы также можете поменять местами два столбца и до сих пор в конечном итоге с действительной сеткой, например, замена колонки 2 и 4:

1 2 5 4 3 
4 5 3 2 1 
3 4 2 1 5 
2 3 1 5 4 
5 1 4 3 2 
    ^^

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

Затем вы можете перейти к шагу 7.

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

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

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

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

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

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