php简单的数独求解器使用回溯

我最近想看看我是否能够在php中解决一个简单的数独（首先）。我知道PHP并不是编程原因的选择，但我知道PHP最好，并且我在java和c中的设计方面有问题。尽管如此，我没有看到它不应该起作用的任何理由。php简单的数独求解器使用回溯

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

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

的算法是这样的：

$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 | 。。。

我想有一个无限循环或导致这次崩溃的东西。也许这是不可解决的。我只是想知道我是否正确或忘记检查。我也尝试过使用easy-sudoku的固定值的算法。它也崩溃...也许有很多回溯。

最后，我想说，我不是反对更好的解决方案，但我只是想这个工作。如果你不能给我在此基础上的答案，你可以看看php文件：

sudoku.php

编辑： sudoku2.php

在此先感谢。

来源

2012-04-05 F. Müller

这是你的主要问题：

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

当你到这一点（这里实在不行，所以你要回去和改变一些东西以前），你不能递归，你是更深层次的，因为你的筹码量会随着错误的积累而变得太大。您需要实际返回到之前的堆栈级别并继续前进。

E.g.如果它已完成，您可以使solve返回TRUE;如果选项用完，则可以使FALSE返回。然后，每当您递归调用solve时，如果它返回TRUE，则返回TRUE，如果返回FALSE，则用$value++再次调用它。

来源

2012-04-05 01:54:52 dkamins

它仍然无法正常工作。但是我可以防止系统崩溃。不，我总是得到这样的信息：“不能解决这个数独”。我想我喜欢你说的。你可能会看看我上面发布的源代码？ “sudoku2.php”。 – 2012-04-05 14:22:24

它现在可以工作......我忘了在回溯到前一个单元格之前将单元格值重置为0。这就是诀窍。 – 2012-04-07 13:10:27

php简单的数独求解器使用回溯

回答

相关问题