2

我最近想看看我是否能够在 php.ini 中解决一个简单的数独（起初）。我知道 php 并不是真正出于编程原因的选择，但我最了解 php，而且我在 java 和 c 中的设计有问题。尽管如此，我看不出它不应该工作的任何理由。

首先我不想问你，因为那里有一些已解决的线程。但是我发现这些解决方案太复杂了，我无法理解（其他语言，复杂的结构）并且超出了我的目标。

我的问题是：有人可以根据我的目标给我一个提示吗？我想要一个简单的数独求解器，无需猜测，只需回溯。

该算法如下所示：

$cell;  // 1-81 - as parameter of the recursive function solve()
$value; // 1-9  - as parameter ...

class Sudoku {

function solve($cell = 1, $value = 1) {

    // skipping values

    if the current cell is fix:

        return solve(cell++, $value);

    // testing values (logic)

    if not:

        if the value is within the square (3x3) itself:

            return solve($cell, $value++);

        if the value is within the row:

            return solve($cell, $value++);

        if the value is within the col:

            return solve($cell, value++);

        if the value is bigger than 9:

            return solve($cell--, $value_prev);

        // all test passed, add the new value to list
        $this->values[$cell] = $value;

        if all fields are filled:
            return;

        if there are fields left:
            return solve($cell++, 1);
}
}

如果我创建一个空白数独，它将正确填满，直到单元格 43。脚本崩溃并出现致命错误：致命错误：允许的内存大小为 134217728 字节已用尽（尝试分配 261904 字节）。

值填写如下：

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

我想有一个无限循环或导致这次崩溃的东西。也许它不是这样解决的。我只是想知道我是否做对了，或者我忘了检查什么。我还尝试了这个算法，它使用来自简单数独的固定值。它也崩溃了……也许有太多的回溯。

最后，我想说我并不反对更好的解决方案，但我只是希望它能够奏效。如果您不能基于此给我答案，您可以查看 php 文件：

数独.php

编辑： 数独2.php

提前致谢。

4

1 回答 1

2

这是您的主要问题：

if the value is bigger than 9:
    return solve($cell--, $value_prev);

当你到达那个点时（没有任何效果，所以你必须回去改变以前的东西），你不能像现在这样更深地递归，因为你的堆栈会随着错误的积累而变得太大。您实际上需要返回到先前的堆栈级别并从那里继续前进。

例如，如果它是完整的，或者如果它用完了选项，你可能会solve退货。然后任何时候你递归调用，如果它返回，你返回，如果它返回，你再次调用它。TRUEFALSEsolveTRUETRUEFALSE$value++

于 2012-04-05T01:54:52.160 回答