4

現在、ペグ ソリティアのゲームを解決するための再帰アルゴリズムをプログラミングしています。

アルゴリズムは、ボードを解決するために「バックトラッキング」アプローチを使用する必要があります。私は正しい解決策に非常に近いものを得ることができたと思います。私のコードは、解決可能なすべてのボードのボードを正しく解決しているようです。また、ボードが解決できない場合も正しく判断しているようですが、ペグの数が多すぎない場合に限られます。

私の再帰的な方法は次のようになります。

public static void solve()
{
    if(isSolved())
    {
        long endTime=System.currentTimeMillis();
        System.out.println("Solved");
        solved=true;
        printArr(board);

    }
    else
    {
            for(int i=0;i<7;i++)
            {
                for(int j=0;j<7;j++)
                {
                    for (int k=0;k<4;k++)
                    {
                        if(makeMove(new int[]{i,j,k}))
                        {
                            if(solved!=true)
                            {
                                solve();
                                undoMove();
                            }
                        }


                    }
                }
            }
        }
    }

ボードは標準的なペグ ソリティア ボードです。私の isSolved() メソッドが、ボードが解決されたかどうかを正しく判断していると確信しています。私の makeMove 関数は、行、列、方向 (i、j、k) を取ります。それらの座標でペグを見つけ、要求された方向にペグを移動できるかどうかを確認します。可能であれば、移動を行い、その移動を移動の配列に追加して、true を返します。そうでない場合は false を返します。

私の元に戻すメソッドは、最後の移動を配列からポップし、ボードを以前のレイアウト (ポップされた移動が行われる前) に戻します。

約 25 個以上のペグを持つランダム ボードの場合、プログラムは単純に終了しないようです。無期限に処理を続けます。解決可能なボードと、ペグの少ないさまざまな解決不可能なボードは、正しい結果で一貫して 10 秒以内に終了するようです。

何か案は？

4

1 に答える 1