c# - ランダムに生成された迷路での再帰的バックトラッキングの使用

Question

私は約 5 年間プログラミングをしていますが、動的な迷路を作成するのに何の問題もありませんでした。しかし、再帰的なバックトラッキングになると、どこから始めればよいかまったくわかりません。私は多くのチュートリアル、トピック、およびいくつかのアルゴリズム wiki (ダイクストラのアルゴリズム) を読みましたが、それらは私には意味がありません。

基本的な再帰がどのように機能するかは知っていますが、以前に検索されたパスを保存せずに再帰的なバックトラッキングがどのように可能であるか (私にはそう思われます)、または追跡されているパスが突然 2 つに分割された場合に何が起こるかを理解し始めることはできません。

私のプログラムは次のように動作します: 迷路は 484 のパネル (mazeTiles という名前の Panel[] 配列) から構成されます。22 列あり、各列には 22 枚のパネルが入ります。黒いパネルの背景は壁で、白いパネルは通過可能です。

これは実行時にどのように見えるかです (そして、左上の開始四角形 (赤) から緑四角形への有効なパスがない場合にのみ表示されるエラー メッセージ):

http://postimg.org/image/6c7wgxtz1/

表示されるエラーメッセージは、明らかに解けるのに「迷路が解けません」というもの。このエラー メッセージは、Button2_Click メソッドにあります。

以下は、チュートリアルから取得した (および変更した) コードです。問題はメソッド内にあることは間違いありませんが、これをトラブルシューティングする方法がわかりません。

    private void button2_Click(object sender, EventArgs e)
    {
        int startPosition = 0;

        for (int i = 0; i < mazeTiles.Length; i++)
        {
            if (mazeTiles[i].BackColor == Color.Red)
            {
                startPosition = i;
            }
        }

        bool[] alreadySearched = new bool[484];

        if (!solveMaze(startPosition, alreadySearched))
            MessageBox.Show("Maze can not be solved.");
    }

    private bool solveMaze(int position, bool[] alreadySearched)
    {
        bool correctPath = false;

        //should the computer check this tile
        bool shouldCheck = true;

        //Check for out of boundaries
        if (position >= mazeTiles.Length || position < 0 )
            shouldCheck = false;
        else
        {
            //Check if at finish, not (0,0 and colored light blue)
            if (mazeTiles[position].BackColor == Color.Green)
            {
                correctPath = true;
                shouldCheck = false;
            }
            //Check for a wall
            if (mazeTiles[position].BackColor == Color.Black)
                shouldCheck = false;
            //Check if previously searched
            if (alreadySearched[position])
                shouldCheck = false;
        }
        //Search the Tile
        if (shouldCheck)
        {
            //mark tile as searched
            alreadySearched[position] = true;
            //Check right tile
            correctPath = correctPath || solveMaze(position + 1, alreadySearched);
            //Check down tile
            correctPath = correctPath || solveMaze(position + 22, alreadySearched);
            //check left tile
            correctPath = correctPath || solveMaze(position - 1, alreadySearched);
            //check up tile
            correctPath = correctPath || solveMaze(position - 22, alreadySearched);
        }

        //make correct path gray
        if (correctPath)
            mazeTiles[position].BackColor = Color.Gray;

        return correctPath;
    }

赤い四角から緑の四角までのすべてのパスまたは最も速いパスを見つけて保存する必要があります (最も速いパスのみをマークします)。緑の四角は静的ですが、赤の四角と迷路全体はランダムに生成されます。