8-9 15パズル

問題

15パズルを解きます。

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct JyoutaiDef
    {
        internal int Level;
        internal string MoveLog;
        internal int[,] Ban;
        internal string PreMove;

        internal void init()
        {
            Ban = new int[,] {{ 1, 2, 3, 4,},  //1
                              { 0, 5, 6, 7,},  //2
                              { 9,10,11, 8,},  //3
                              {13,14,15,12,}}; //4;
            PreMove = "";
        }

        internal bool IsGoal()
        {
            int mustNumber = 0;
            for (int Y = 0; Y <= 3; Y++) {
                for (int X = 0; X <= 3; X++) {
                    ++mustNumber;
                    if (mustNumber != 16 && Ban[Y, X] != mustNumber) return false;
                }
            }
            return true;
        }
    }
    static void Main()
    {
        var Jyoutai = new JyoutaiDef();
        Jyoutai.init();

        var que = new Queue<JyoutaiDef>();
        que.Enqueue(Jyoutai);

        int answerLevel = int.MaxValue;

        while (que.Count != 0) {
            Jyoutai = que.Dequeue();

            if (++Jyoutai.Level > answerLevel) continue;

            if (Jyoutai.IsGoal()) {
                Console.WriteLine("answer");
                Console.WriteLine(Jyoutai.MoveLog);
                answerLevel = Jyoutai.Level;
                continue;
            }

            int X = 0, Y = 0;
            while (Jyoutai.Ban[Y, X] != 0) {
                if (++Y == 4) {
                    X++; Y = 0;
                }
            }

            //左の数字を、右に移動
            if (X != 0 && Jyoutai.PreMove != "←") {
                JyoutaiDef Saved = Jyoutai; Saved.Ban = (int[,])Jyoutai.Ban.Clone();
                Saved.Ban[Y, X - 1] = 0;
                Saved.Ban[Y, X] = Jyoutai.Ban[Y, X - 1];
                Saved.MoveLog += "→,";
                Saved.PreMove = "→";
                que.Enqueue(Saved);
            }

            //右の数字を、左に移動
            if (X != 3 && Jyoutai.PreMove != "→") {
                JyoutaiDef Saved = Jyoutai; Saved.Ban = (int[,])Jyoutai.Ban.Clone();
                Saved.Ban[Y, X + 1] = 0;
                Saved.Ban[Y, X] = Jyoutai.Ban[Y, X + 1];
                Saved.MoveLog += "←,";
                Saved.PreMove = "←";
                que.Enqueue(Saved);
            }

            //上の数字を、下に移動
            if (Y != 0 && Jyoutai.PreMove != "↑") {
                JyoutaiDef Saved = Jyoutai; Saved.Ban = (int[,])Jyoutai.Ban.Clone();
                Saved.Ban[Y - 1, X] = 0;
                Saved.Ban[Y, X] = Jyoutai.Ban[Y - 1, X];
                Saved.MoveLog += "↓,";
                Saved.PreMove = "↓";
                que.Enqueue(Saved);
            }

            //下の数字を、上に移動
            if (Y != 3 && Jyoutai.PreMove != "↓") {
                JyoutaiDef Saved = Jyoutai; Saved.Ban = (int[,])Jyoutai.Ban.Clone();
                Saved.Ban[Y + 1, X] = 0;
                Saved.Ban[Y, X] = Jyoutai.Ban[Y + 1, X];
                Saved.MoveLog += "↑,";
                Saved.PreMove = "↑";
                que.Enqueue(Saved);
            }
        }
    }
}

実行結果

answer
←,←,←,↑,↑,

解説

Queueジェネリックは強力ですねぇ

23-11 15ゲーム