php easy sudokuソルバのバックトラックを使用して

Question

私は最近、私がPHP内で簡単なスドクを解くことができるかどうかを見たいと思っていました。私は、PHPは本当にプログラミングの理由のためのchoiseではない知っているが、私は最高の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 | 。 。 。

このクラッシュの原因となる無限ループなどがあります。多分このように解決できないかもしれません。私はちょうど私が正しいことをしているのか、私がチェックするのを忘れていたのかを知りたかった。 私はeasy-sudokuの固定値でこのアルゴリズムを試しました。それはあまりにもクラッシュする...多分バックトラックすることがあります。

最後に、私はより良い解決策に反対していないと言いたいと思いますが、これを機能させたいだけです。 あなたが私にこれに基づいて答えを与えることができない場合は、PHPファイルを見て持つことができます。

sudoku.php

編集：事前に sudoku2.php

感謝を。

Answer 1

これはあなたの主な問題である：

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

あなたは（何も動作するので、あなたが戻って、以前に何かを変更する必要がある場合）、そのポイントに到達すると、あなたがそうであるように、あなたは、より深く再帰することはできませんあなたのスタックはあまりにも大きく成長し、間違いが蓄積されるからです。あなたは実際に前のスタックレベルに戻り、そこから続ける必要があります。

など。 solveが完了した場合はTRUE、またはオプションが不足している場合はFALSEとなります。 solveを再帰的に呼び出すと、TRUEが返され、TRUEが返され、FALSEが返された場合は、$value++が返されます。