2

私は最近、php内で（最初は）簡単な数独を解決できるかどうかを確認したいと思いました。私は、プログラミング上の理由から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

編集： sudoku2.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 に答える