ペグ・ソリティアを解く

C# の再起関数でペグ・ソリティアゲームの答えを見つけ出します。

プログラムの説明

次のファイルを格納して下さい。

/**************************************************/
/*★ ペグソリティアの答えを見つける     前田 稔 ★*/
/**************************************************/
using System;

class Prog
{
    static string[] st =
    {   "*********",  //0
        "***+++***",  //1
        "***+++***",  //2
        "*+++++++*",  //3
        "*+++ +++*",  //4
        "*+++++++*",  //5
        "***+++***",  //6
        "***+++***",  //7
        "*********"   //8
    };
/*
    static string[] st =
    {   "*********",  //0
        "***   ***",  //1
        "*** + ***",  //2
        "*  +++  *",  //3
        "*   +   *",  //4
        "*   +   *",  //5
        "***   ***",  //6
        "***   ***",  //7
        "*********"   //8
    };
    static string[] st =
    {   "*********",  //0
        "***   ***",  //1
        "*** + ***",  //2
        "*   +   *",  //3
        "*    +  *",  //4
        "*   ++  *",  //5
        "***   ***",  //6
        "***   ***",  //7
        "*********"   //8
    };
*/
    static char[,]  tbl = new char[9,9];
    // 検索の方向(上,下,左,右)
    static int[]    yd = { -1, 1, 0, 0 };
    static int[]    xd = { 0, 0, -1, 1 };

    //★Main() 関数
    public static void Main()
    {
        int x,y;

        //string[] st を char[,] t に格納
        for (y = 0; y < 9; y++)
            for (x = 0; x < 9; x++) tbl[y, x] = st[y][x];
        //最初の状態を表示
        disp(tbl);
        //答えを見つける
        srh(tbl);
        Console.WriteLine("終了しました");
        Console.ReadLine();
    }

    // 現在の状態を表示
    public static void disp(char[,] t)
    {
        int x,y;
        for (y = 0; y < 9; y++)
        {
            for (x = 0; x < 9; x++) Console.Write("{0}", t[y, x]);
            Console.WriteLine("");
        }
    }

    // ペグのカウント＆状態をコピー
    public static bool copy(char[,] t, char[,] tt)
    {   int     y, x, c;
        c = 0;
        for (y = 0; y < 9; y++)
            for (x = 0; x < 9; x++)
            {   if (tt[y, x]=='+')  c++;
                t[y, x] = tt[y, x];
            }
        if (c == 1) return true;
        return false;
    }

    // 再起でペグの手を検索
    static bool srh(char[,] tt)
    {
        char[,] t = new char[9,9];
        int     y, x, i;
        int     y1, y2, x1, x2;

//disp(tt);  Console.ReadLine();
        // ペグのカウント＆状態をコピー
        if (copy(t,tt))
        {
            Console.WriteLine("★ＯＫ");
            disp(tt);
            return true;
        }
        // 全てのペグをサーチ
        for (y = 1; y < 8; y++)
        {
            for (x = 1; x < 8; x++)
            {
                if (t[y, x] == '+')
                {   //上下左右を調べる
                    for (i = 0; i < 4; i++)
                    {
                        y1 = y + yd[i];
                        y2 = y1 + yd[i];
                        x1 = x + xd[i];
                        x2 = x1 + xd[i];
                        if (t[y1, x1] == '+' && t[y2, x2] == ' ')
                        {
                            t[y, x] = ' ';
                            t[y1, x1] = ' ';
                            t[y2, x2] = '+';
                            if (srh(t))
                            {
                                disp(tt);
                                return true;
                            }
                            t[y, x] = '+';
                            t[y1, x1] = '+';
                            t[y2, x2] = ' ';

                        }
                    }
                }
            }
        }
        return false;
    }
}

もう三百年以上もパズル好きを楽しませてきたペグ・ソリティアの問題を解いてみましょう。
わがままな娘がペグ・ソリティアに挑戦していて、答えが見つからないので「本当に解けるか否かを調べて」と言う挑発に乗り作成しました。 (^_^;)
パズルの問題をプログラムで解くのは意外と難しいものです。
今回も再起関数(自分自身を多重に呼び出す)を使います。
ペグ・ソリティアのルールです。
ゲームの説明と問題は次のページのお世話になりました。
ペグ・ソリティア
リンク出来ないときは「ウィキペディアなど」から「ペグ・ソリテール」で検索して下さい。
- もう三百年以上もパズル好きを楽しませてきたひとり遊びです。
- ペグを動かしていって、一つだけ残して(場所を問わず)全て取り去るのがこのゲームの目的です。
- それぞれのペグは、開いているスペースに向かって上下左右に２マス動くことができ、動くときに飛び越えたペグを取り去ります。
- 飛び越すペグが無い場合は動くことができません。また、斜めに動くこともできません。

ペグ・ソリティアの問題を定義する領域です。
+ 記号がペグで、空白が開いているスペースです。
添え字が領域外に出たことを判定しなくても良いように、周りを * で囲んでいます。
ページ先頭の画像と見比べて下さい。

    static string[] st =
    {   "*********",  //0
        "***   ***",  //1
        "*** + ***",  //2
        "*  +++  *",  //3
        "*   +   *",  //4
        "*   +   *",  //5
        "***   ***",  //6
        "***   ***",  //7
        "*********"   //8
    };

string[] のままでは判定しにくいので、問題を二次元 char に格納します。
yd[] と xd[] はペグの移動の方向(上,下,左,右)です。

    static char[,]  tbl = new char[9,9];
    // 検索の方向(上,下,左,右)
    static int[]    yd = { -1, 1, 0, 0 };
    static int[]    xd = { 0, 0, -1, 1 };

disp() メソッドで現在の状態を印字します。
copy() メソッドで現在の状態をコピーしながら残りのペグをカウントします。
ペグが一個になれば、答えが見つかったときです。
srh() が再起でゲームを解くメソッドです。
パラメータで渡された tt をローカル領域の t に copy() メソッドでコピーします。
copy() メソッドの戻り値が true のときは、答えが見つかったときです。
t に設定されている全てのペグをサーチします。
見つかったペグに対して、上,下,左,右に移動出来るかを調べます。
移動可能のとき、t を更新(ペグを移動)して srh() を再起コールします。
- srh() の戻り値が true のときは、答えが見つかったときです。
  現在の tt を表示して return true で終了します。
- srh() の戻り値が false のときは、答えが見つからなかったときです。
  t を元に戻して次の方向(次のペグ)を調べます。
再起のプログラムはソースコードを見ただけでは解りません。
簡単な問題を設定して出力結果を確認して下さい。
簡単な問題なら一瞬で解けますが、難問になると数分かかりることがあります。
あせらずに答えが出るまで数分間待って下さい。

超初心者のプログラム入門(C# Frame Work)

※・ ※・