生成数独网格的回溯算法未完成

Question

我编写了一个数独生成器，它逐个单元格地创建数字，并在单元格创建后立即检查它是否有效（水平、垂直和 3x3 块）。

现在我的问题是算法总是卡在某个点，因为它找不到当前单元格的有效数字。有时接近尾声，有时已经写了 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() 检查单元格在水平、垂直和块中是否有效（这目前不起作用，它只是 returns true）。

计数器用于调试目的，所以我可以看到它何时卡住。

这是生成我的细胞的函数：

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

应该更改什么以使算法不会一直卡住？

Answer 1

问题可能是算法有点太随机了。您最终创建了一个无效且无法进一步完成的网格。

我建议从一个已知的有效网格开始，随机打乱单元格。如果一个单元格不能移动，我们可以简单地跳过它。

对 reader 的公平警告，以下内容将包含伪代码而不是工作代码。

一个完全有效的起始网格：

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 并将该值用于 select $cells
中的随机 $cell
```
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

可能有更有效的方法来进行，但这个逻辑不能卡住。

请注意，随机播放将自行撤消并生成原始网格的可能性很小。但它仍然是一个有效的网格。

Answer 2

您绝对不想制作使用随机数的回溯算法。它可以无限地结束运行。

您想做的是：

找到第一个空单元格
在此单元格中尝试从 1 到 9 的所有可能值。当所有值都尝试过后，返回。
对于您在单元格中尝试的每个值（在第 2 步），递归调用回溯算法。（回到第 1 步）
如果函数被调用并且没有空单元格，则评估电路板。如果一切正常，您就找到了解决方案！不行就回去

评估的意思是，检查从 1 到 9 的所有数字是否在每一行、每一列和每个 3x3 正方形上恰好出现一次。

外观示例：

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)

可以通过在每一步评估 lines/columns 来优化上述算法，而不是在最后只评估一次。如果算法尝试放置数字 x，但 x 已经在 line/column 上找到，那么我们可以继续尝试 x+1，因为我们知道 x 会创建一个无效的解决方案。

生成数独网格的回溯算法未完成

Backtracking algorithm to generate a sudoku grid does not complete

php

algorithm

sudoku