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簡單的數獨求解器使用回溯

回答

相關問題