Алгоритм возврата для создания сетки судоку не завершен

Question

Алгоритм возврата для создания сетки судоку не завершен

Я написал генератор судоку, который создает числа ячейка за ячейкой и сразу же после создания ячейки проверяет ее действительность (по горизонтали, вертикали и в блоке 3×3).

Теперь моя проблема в том, что алгоритм всегда застревает в какой-то момент, так как он не найдет действительное число для текущей ячейки. Иногда ближе к концу, иногда уже после записи 30 ячеек.

Это моя функция для проверки ячейки, которая должна менять номер в зависимости от его действительности:

private function checkCell($index)
{
while ($this->isValid($index) === false) {

$this->cell[$index]->setValue(rand(1, 9));
$this->counter++;

echo 'counter: ' . $this->counter;
echo PHP_EOL;

if ($this->counter > 1000) {
$this->display();
die();
}
}
}

isValid() проверяет, является ли ячейка действительной по горизонтали, вертикали и в блоке (это в настоящее время не работает, она просто возвращает true).

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

Вот функция, генерирующая мои клетки:

private function fillCell($index)
{
$rand = rand(1, 9);
$this->cell[$index]->setValue($rand);
$this->checkCell($index);
}

Что нужно изменить, чтобы алгоритм не зависал все время?

0

algorithm php sudoku

Решение

Другие решения

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

Что вы хотите сделать, это:

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

Оценка означает, что у вас есть все числа от 1 до 9 ровно один раз в каждой строке, каждом столбце и каждом квадрате 3х3.

Пример того, как это может выглядеть:

function back($pos) {
if ($pos >= 9*9) {
if (evaluate()) {
// we found a solution
// do soemthing with it
} else {
return;
}
}

$x = pos / 9;
$y = pos % 9;

if ($m[x][y] != 0) {
// we already have a value assigned for this position
back($pos+1);
return;
}

for ($v = 1; $v <= 9; $v++) {
$m[x][y] = $v;
back($pos+1);
}
$m[x][y] = 0; // clean up tested value before going back
}

back(1)

Приведенный выше алгоритм может быть оптимизирован путем оценки строк / столбцов на каждом шаге, а не только один раз в конце. Если алгоритм пытается разместить число x, но x уже найден в строке / столбце, то мы можем просто перейти к x + 1, поскольку мы знаем, что x создаст неверное решение.

0

Источник

Accepted Answer

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

Я бы предложил начать с известной действительной сетки и случайным образом перемешать ячейки. Если клетка не может быть перемещена, мы можем просто пропустить ее.

Честное предупреждение для читателя, следующее будет содержать псевдокод, а не рабочий код.

Совершенно действительная стартовая сетка:

1 2 3 | 4 5 6 | 7 8 9
7 8 9 | 1 2 3 | 4 5 6
4 5 6 | 7 8 9 | 1 2 3
------|-------|------
9 1 2 | 3 4 5 | 6 7 8
6 7 8 | 9 1 2 | 3 4 5
3 4 5 | 6 7 8 | 9 1 2
------|-------|------
8 9 1 | 2 3 4 | 5 6 7
5 6 7 | 8 9 1 | 2 3 4
2 3 4 | 5 6 7 | 8 9 1

Мы можем хранить это в одном массиве измерений, как вы, похоже, делаете.

Мы следуем простой логике:

Мы создаем массив одного измерения, содержащий ячейки

$cells = array(
1,2,3,4,5,6,7,8,9,7,8,9,1,2,3,4,5,6,4,5,6,7,8,9,1,2,3,
9,1,2,3,4,5,6,7,8,6,7,8,9,1,2,3,4,5,3,4,5,6,7,8,9,1,2,
8,9,1,2,3,4,5,6,7,5,6,7,8,9,1,2,3,4,2,3,4,5,6,7,8,9,1,
);

Мы создаем еще один массив, содержащий числа из 0 в 80 в случайном порядке, которые являются индексами $cells
```
$indexes = range(0, 80);
shuffle($indexes);
```
Перебираем $indexes и используйте значение, чтобы выбрать случайный $cell в $cells
```
foreach($indexes as $index) {
$cell = $cells[$index];
}
```
Для каждого $cellперебираем $cells, На каждой итерации мы создаем временную сетку, в которой мы меняем значение текущей ячейки на значение целевой ячейки. Если временная сетка действительна, мы сохраняем целевой индекс в массиве кандидатов
```
// pseudo code because that's a lot of work
$candidates = getCandidates($cell, $cells);
```
Мы случайным образом выбираем одного из кандидатов и меняем ячейки. Если ни один кандидат не доступен, мы просто игнорируем этот шаг
```
candidatesCount = count(candidates);
if(candidatesCount > 0) {
$candidate = $candidates[range(0, candidatesCount -1)];
// switch values
$cells[$index]    = $cells[$candidate];
$cells[candidate] = $cell;
}
```
Повторять до $cells обрабатывается

Есть, вероятно, более эффективные способы, чтобы продолжить, но эта логика не может застрять.

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

0