8-12 ハノイの塔

問題

ハノイの塔(円盤は3枚)を解きます。

ソース

using System;
using System.Collections.Generic;

class Program
{
    struct jyoutaiDef
    {
        internal int Level;
        internal string MoveLog;
        internal List<int> Jiku1;
        internal List<int> Jiku2;
        internal List<int> Jiku3;

        internal void init()
        {
            Jiku1 = new List<int> { 3, 2, 1 };
            Jiku2 = new List<int>();
            Jiku3 = new List<int>();
            MoveLog = string.Empty;
        }

        internal bool IsGoal()
        {
            if (Jiku3.Count != 3) return false;
            for (int I = 0; I <= 2; I++) {
                if (Jiku3[I]+I != 3) return false;
            }
            return true;
        }

        internal jyoutaiDef GetClone()
        {
            jyoutaiDef willReturn;
            willReturn.Level = this.Level;
            willReturn.MoveLog = (string)this.MoveLog.Clone();
            willReturn.Jiku1 = new List<int>();
            foreach (int each in this.Jiku1) willReturn.Jiku1.Add(each);
            willReturn.Jiku2 = new List<int>();
            foreach (int each in this.Jiku2) willReturn.Jiku2.Add(each);
            willReturn.Jiku3 = new List<int>();
            foreach (int each in this.Jiku3) willReturn.Jiku3.Add(each);
            return willReturn;
        }
    }

    static void Main(string[] args)
    {
        var jyoutai = new jyoutaiDef();
        jyoutai.init();

        var que = new Queue<jyoutaiDef>();
        que.Enqueue(jyoutai);

        int answerLevel = int.MaxValue;
        int restCnt = 999999;

        while (que.Count != 0) {
            jyoutai = que.Dequeue();
            //Console.WriteLine(jyoutai.MoveLog);

            if (--restCnt == 0) {
                Console.WriteLine("CountStop!!!");
                return;
            }

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

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

            //軸1から移動
            if (jyoutai.Jiku1.Count > 0) {
                int moveVal = jyoutai.Jiku1[jyoutai.Jiku1.Count - 1];
                if (jyoutai.Jiku2.Count == 0
                || jyoutai.Jiku2[jyoutai.Jiku2.Count - 1] > moveVal) {
                    jyoutaiDef saved = jyoutai.GetClone();
                    saved.Jiku2.Add(moveVal);
                    saved.Jiku1.Remove(moveVal);
                    saved.MoveLog += "Level" + saved.Level.ToString() + "円盤" + moveVal.ToString() + "を軸1から軸2へ";
                    saved.MoveLog += Environment.NewLine;
                    que.Enqueue(saved);
                }
                if (jyoutai.Jiku3.Count == 0
                || jyoutai.Jiku3[jyoutai.Jiku3.Count - 1] > moveVal) {
                    jyoutaiDef saved = jyoutai.GetClone();
                    saved.Jiku3.Add(moveVal);
                    saved.Jiku1.Remove(moveVal);
                    saved.MoveLog += "Level" + saved.Level.ToString() + "円盤" + moveVal.ToString() + "を軸1から軸3へ";
                    saved.MoveLog += Environment.NewLine;
                    que.Enqueue(saved);
                }
            }

            //軸2から移動
            if (jyoutai.Jiku2.Count > 0) {
                int moveVal = jyoutai.Jiku2[jyoutai.Jiku2.Count - 1];
                if (jyoutai.Jiku1.Count == 0
                || jyoutai.Jiku1[jyoutai.Jiku1.Count - 1] > moveVal) {
                    jyoutaiDef saved = jyoutai.GetClone();
                    saved.Jiku1.Add(moveVal);
                    saved.Jiku2.Remove(moveVal);
                    saved.MoveLog += "Level" + saved.Level.ToString() + "円盤" + moveVal.ToString() + "を軸2から軸1へ";
                    saved.MoveLog += Environment.NewLine;
                    que.Enqueue(saved);
                }
                if (jyoutai.Jiku3.Count == 0
                || jyoutai.Jiku3[jyoutai.Jiku3.Count - 1] > moveVal) {
                    jyoutaiDef saved = jyoutai.GetClone();
                    saved.Jiku3.Add(moveVal);
                    saved.Jiku2.Remove(moveVal);
                    saved.MoveLog += "Level" + saved.Level.ToString() + "円盤" + moveVal.ToString() + "を軸2から軸3へ";
                    saved.MoveLog += Environment.NewLine;
                    que.Enqueue(saved);
                }

            }

            //軸3から移動
            if (jyoutai.Jiku3.Count > 0) {
                int moveVal = jyoutai.Jiku3[jyoutai.Jiku3.Count - 1];
                if (jyoutai.Jiku1.Count == 0
                || jyoutai.Jiku1[jyoutai.Jiku1.Count - 1] > moveVal) {
                    jyoutaiDef saved = jyoutai.GetClone();
                    saved.Jiku1.Add(moveVal);
                    saved.Jiku3.Remove(moveVal);
                    saved.MoveLog += "Level" + saved.Level.ToString() + "円盤" + moveVal.ToString() + "を軸3から軸1へ";
                    saved.MoveLog += Environment.NewLine;
                    que.Enqueue(saved);
                }
                if (jyoutai.Jiku2.Count == 0
                || jyoutai.Jiku2[jyoutai.Jiku2.Count - 1] > moveVal) {
                    jyoutaiDef saved = jyoutai.GetClone();
                    saved.Jiku2.Add(moveVal);
                    saved.Jiku3.Remove(moveVal);
                    saved.MoveLog += "Level" + saved.Level.ToString() + "円盤" + moveVal.ToString() + "を軸3から軸2へ";
                    saved.MoveLog += Environment.NewLine;
                    que.Enqueue(saved);
                }
            }

        }
    }
}

実行結果

answer
Level1円盤1を軸1から軸3へ
Level2円盤2を軸1から軸2へ
Level3円盤1を軸3から軸2へ
Level4円盤3を軸1から軸3へ
Level5円盤1を軸2から軸1へ
Level6円盤2を軸2から軸3へ
Level7円盤1を軸1から軸3へ

解説

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