トップページに戻る    次のC#のサンプルへ    前のC#のサンプルへ

Cマガ電脳クラブ(第020回) Non-crossing Knight's Tour

問題

今回は、Non-crossing Knight's Tourだ。
その名のとおりチェスのナイトが自分が通った道筋と交差しないようにして盤の上を旅行するのだ。
ナイトが、道筋の交差なしに、6×6の盤の上を15手移動している例をFig.1に示す。

では、この盤の上をナイトは最高何手移動できるだろうか。その手数と、Fig.1のような動き方を示し、

さらに、その動き方が回転・鏡像解を除いて何通りあるかを答えていただきたい。
ただし、ナイトは各マスの正方形の中心を訪れることとし、また、同じマスには2度以上訪れてはいけない。
なお、チェスのナイトは、Fig.2のように8方向に動くことができる。

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 6 - 1;

    struct SenbunDef //ナイトの移動の線分
    {
        internal int StaX; //ナイトの移動開始X座標
        internal int StaY; //ナイトの移動開始Y座標
        internal int EndX; //ナイトの移動終了X座標
        internal int EndY; //ナイトの移動終了Y座標
    }

    struct JyoutaiDef
    {
        internal int CurrX;
        internal int CurrY;
        internal List<SenbunDef> SenbunList;
    }

    static void Main()
    {
        var stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;

        //最初のPush処理
        Action<int, int> FirstPushSyori = (pX, pY) =>
        {
            WillPush.CurrX = pX;
            WillPush.CurrY = pY;
            WillPush.SenbunList = new List<SenbunDef>();
            stk.Push(WillPush);
        };
        //6*6で回転解を除外するので、開始候補は絞れる
        FirstPushSyori(0, 0);
        FirstPushSyori(0, 1); FirstPushSyori(1, 1);
        FirstPushSyori(0, 2); FirstPushSyori(1, 2); FirstPushSyori(2, 2);

        int MostMoveCnt = 1;
        var MostMoveLogArrList = new List<int[,]>();

        while (stk.Count > 0) {
            JyoutaiDef Popped = stk.Pop();

            //最大手数を更新した場合
            if (MostMoveCnt < Popped.SenbunList.Count) {
                MostMoveCnt = Popped.SenbunList.Count;
                MostMoveLogArrList.Clear();
            }
            //最大手数と等しかったら、移動のログを保存
            if (MostMoveCnt == Popped.SenbunList.Count) {
                bool IsOKEndPoint = true;
                //終点が下記のいずれかの解は除外 (始点がこれらの解と対をなすため)
                if (Popped.CurrX == 0 && Popped.CurrY == 0) IsOKEndPoint = false;
                if (Popped.CurrX == 0 && Popped.CurrY == 1) IsOKEndPoint = false;
                if (Popped.CurrX == 0 && Popped.CurrY == 2) IsOKEndPoint = false;
                if (Popped.CurrX == 1 && Popped.CurrY == 1) IsOKEndPoint = false;
                if (Popped.CurrX == 1 && Popped.CurrY == 2) IsOKEndPoint = false;
                if (Popped.CurrX == 2 && Popped.CurrY == 2) IsOKEndPoint = false;

                if (IsOKEndPoint)
                    MostMoveLogArrList.Add(CreateMoveLogArr(Popped.SenbunList));
            }

            PushSyori(stk, Popped, Popped.CurrX + 1, Popped.CurrY - 2);
            PushSyori(stk, Popped, Popped.CurrX + 2, Popped.CurrY - 1);
            PushSyori(stk, Popped, Popped.CurrX + 2, Popped.CurrY + 1);
            PushSyori(stk, Popped, Popped.CurrX + 1, Popped.CurrY + 2);
            PushSyori(stk, Popped, Popped.CurrX - 1, Popped.CurrY + 2);
            PushSyori(stk, Popped, Popped.CurrX - 2, Popped.CurrY + 1);
            PushSyori(stk, Popped, Popped.CurrX - 2, Popped.CurrY - 1);
            PushSyori(stk, Popped, Popped.CurrX - 1, Popped.CurrY - 2);
        }

        RemoveKaiten(MostMoveLogArrList); //回転解を除外

        Console.WriteLine("最大手数は{0}手です。", MostMoveCnt);
        Console.WriteLine();

        for (int I = 0; I <= MostMoveLogArrList.Count - 1; I++) {
            Console.WriteLine("解{0}", I + 1);
            Console.WriteLine(CreateMoveLog(MostMoveLogArrList[I]));
        }
    }

    static void PushSyori(Stack<JyoutaiDef> pStk, JyoutaiDef pPoppedJyoutai,
        int pToX, int pToY)
    {
        //有効な移動かを判定
        if (IsValidMove(pToX, pToY, pPoppedJyoutai) == false) return;

        JyoutaiDef WillPush;
        WillPush.CurrX = pToX;
        WillPush.CurrY = pToY;
        WillPush.SenbunList = new List<SenbunDef>(pPoppedJyoutai.SenbunList);

        SenbunDef WillAdd;
        WillAdd.StaX = pPoppedJyoutai.CurrX;
        WillAdd.StaY = pPoppedJyoutai.CurrY;
        WillAdd.EndX = pToX;
        WillAdd.EndY = pToY;
        WillPush.SenbunList.Add(WillAdd);

        pStk.Push(WillPush);
    }

    //有効な移動かを判定
    static bool IsValidMove(int pToX, int pToY, JyoutaiDef pPoppedJyoutai)
    {
        //盤面の外ならNG
        if (pToX < 0 || UB < pToX) return false;
        if (pToY < 0 || UB < pToY) return false;

        //一度通った座標への再訪ならNG
        if (pPoppedJyoutai.SenbunList.Exists(X =>
            X.StaX == pToX && X.StaY == pToY)) return false;

        SenbunDef wkSenbun;
        wkSenbun.StaX = pPoppedJyoutai.CurrX;
        wkSenbun.StaY = pPoppedJyoutai.CurrY;
        wkSenbun.EndX = pToX;
        wkSenbun.EndY = pToY;

        //直前の線分以外との交点の有無チェック
        //(直前の線分は訪問済座標への再訪チェックだけでOK)
        for (int I = 0; I <= (pPoppedJyoutai.SenbunList.Count - 1) - 1; I++) {
            if (HasCrossPoint(pPoppedJyoutai.SenbunList[I], wkSenbun))
                return false;
        }
        return true;
    }

    static bool HasCrossPoint(SenbunDef pSenbun1, SenbunDef pSenbun2)
    {
        int Senbun1MinX = Math.Min(pSenbun1.StaX, pSenbun1.EndX);
        int Senbun1MaxX = Math.Max(pSenbun1.StaX, pSenbun1.EndX);
        int Senbun2MinX = Math.Min(pSenbun2.StaX, pSenbun2.EndX);
        int Senbun2MaxX = Math.Max(pSenbun2.StaX, pSenbun2.EndX);

        int Senbun1MinY = Math.Min(pSenbun1.StaY, pSenbun1.EndY);
        int Senbun1MaxY = Math.Max(pSenbun1.StaY, pSenbun1.EndY);
        int Senbun2MinY = Math.Min(pSenbun2.StaY, pSenbun2.EndY);
        int Senbun2MaxY = Math.Max(pSenbun2.StaY, pSenbun2.EndY);

        //定義域が交わってない場合
        if ((Senbun2MinX <= Senbun1MaxX && Senbun1MinX <= Senbun2MaxX) == false)
            return false;

        //値域が交わってない場合
        if ((Senbun2MinY <= Senbun1MaxY && Senbun1MinY <= Senbun2MaxY) == false)
            return false;

        //各線分の傾きと切片を求める
        decimal a1, a2;
        decimal b1, b2;
        DeriveKatamukiSeppen(pSenbun1, out a1, out b1);
        DeriveKatamukiSeppen(pSenbun2, out a2, out b2);

        //移項する
        decimal wkA = a1 - a2;
        decimal wkB = b2 - b1;

        if (wkA == 0) return false; //交点がない場合
        decimal wkX = wkB / wkA;

        //交点のX座標が両方の線分の定義域にあればOK
        return Senbun1MinX <= wkX && wkX <= Senbun1MaxX
            && Senbun2MinX <= wkX && wkX <= Senbun2MaxX;
    }

    //線分の傾きと切片を求める
    static void DeriveKatamukiSeppen(SenbunDef pSenbun1, out decimal pA, out decimal pB)
    {
        pA = (decimal)pSenbun1.StaY - pSenbun1.EndY;
        pA /= pSenbun1.StaX - pSenbun1.EndX;

        pB = pSenbun1.StaY - pA * pSenbun1.StaX;
    }

    //下記の形式で移動のログをint型の2次元配列で作成
    //00,00,02,00,00,00
    //01,00,00,00,00,00
    //00,03,00,00,00,05
    //00,00,00,04,00,00
    //08,00,00,00,06,00
    //00,00,07,00,00,00
    static int[,] CreateMoveLogArr(List<SenbunDef> pSenbunList)
    {
        int[,] MoveLogArr = new int[UB + 1, UB + 1];
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                //ListジェネリックのFindIndexメソッド
                //msdn.microsoft.com/ja-jp/library/0k601hd9(v=vs.90).aspx
                int wkIndSta = pSenbunList.FindIndex(I => I.StaX == X && I.StaY == Y);
                int wkIndEnd = pSenbunList.FindIndex(I => I.EndX == X && I.EndY == Y);
                if (wkIndSta >= 0) MoveLogArr[X, Y] = wkIndSta + 1;
                else if (wkIndEnd >= 0) MoveLogArr[X, Y] = wkIndEnd + 2;
                else MoveLogArr[X, Y] = 0;
            }
        }
        return MoveLogArr;
    }

    //下記の形式で移動のログをstring型で作成
    //00,00,02,00,00,00
    //01,00,00,00,00,00
    //00,03,00,00,00,05
    //00,00,00,04,00,00
    //08,00,00,00,06,00
    //00,00,07,00,00,00
    static string CreateMoveLog(int[,] pMoveLogArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.AppendFormat("{0:00}", pMoveLogArr[X, Y]);
                if (X != UB) sb.Append(',');
            }
            sb.AppendLine();
        }
        return sb.ToString();
    }

    //回転を除外
    static void RemoveKaiten(List<int[,]> pTargetList)
    {
        Predicate<int> IsExist = (pCurrInd) =>
        {
            for (int I = 0; I <= pCurrInd - 1; I++) {
                bool IsOK1 = false, IsOK2 = false, IsOK3 = false, IsOK4 = false;
                bool IsOK5 = false, IsOK6 = false, IsOK7 = false; //回転1から7

                for (int X = 0; X <= UB; X++) {
                    for (int Y = 0; Y <= UB; Y++) {
                        int CurrVal = pTargetList[pCurrInd][X, Y];
                        if (pTargetList[I][UB - X, Y] != CurrVal) IsOK1 = true;
                        if (pTargetList[I][UB - X, UB - Y] != CurrVal) IsOK2 = true;
                        if (pTargetList[I][X, UB - Y] != CurrVal) IsOK3 = true;
                        if (pTargetList[I][Y, X] != CurrVal) IsOK4 = true;
                        if (pTargetList[I][UB - Y, X] != CurrVal) IsOK5 = true;
                        if (pTargetList[I][UB - Y, UB - X] != CurrVal) IsOK6 = true;
                        if (pTargetList[I][Y, UB - X] != CurrVal) IsOK7 = true;
                    }
                }
                if (IsOK1 == false || IsOK2 == false || IsOK3 == false || IsOK4 == false
                 || IsOK5 == false || IsOK6 == false || IsOK7 == false)
                    return true;
            }
            return false;
        };

        for (int I = pTargetList.Count - 1; I >= 0; I--) {
            if (IsExist(I)) pTargetList.RemoveAt(I);
        }
    }
}

実行結果

最大手数は17手です。

解1
00,18,00,00,15,00
00,00,16,07,00,13
17,06,01,14,09,00
00,00,08,03,12,00
05,02,00,10,00,00
00,00,04,00,00,11

解説

ListジェネリックのFindIndexメソッドと
ListジェネリックのExistsメソッドを使い分けてます。

MSDN --- List<T>.FindIndexメソッド
MSDN --- List<T>.Existsメソッド

検証用のWindowsフォームアプリのソースと実行結果

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;

namespace _12_20_Kensyou
{
    public partial class Form1 : Form
    {
        public Form1()
        {
            InitializeComponent();
        }

        private void Form1_Load(object sender, EventArgs e)
        {
            //480ピクセル*480ピクセルのPictureBoxを使用
            Bitmap canvas = new Bitmap(PictureBox1.Width, PictureBox1.Height);
            using (Graphics g = Graphics.FromImage(canvas)) {
                for (int Y = 0; Y <= 5; Y++) {
                    for (int X = 0; X <= 5; X++) {
                        g.FillRectangle((X + Y) % 2 == 0 ? Brushes.White : Brushes.AntiqueWhite,
                            80 * X, 80 * Y, 80, 80);
                    }
                }
                g.DrawLines(Pens.Black, DerivePointsFromArr());
            }

            PictureBox1.Image = canvas;
        }

        private Point[] DerivePointsFromArr()
        {
            int[,] RevArr = new int[,] {{00,18,00,00,15,00},
                                        {00,00,16,07,00,13},
                                        {17,06,01,14,09,00},
                                        {00,00,08,03,12,00},
                                        {05,02,00,10,00,00},
                                        {00,00,04,00,00,11}};
            int[,] wkArr = new int[RevArr.GetUpperBound(0) + 1, RevArr.GetUpperBound(1) + 1];
            for (int X = 0; X <= RevArr.GetUpperBound(0); X++) {
                for (int Y = 0; Y <= RevArr.GetUpperBound(0); Y++) {
                    wkArr[X, Y] = RevArr[Y, X];
                }
            }

            var PointsList = new List<Point>();
            for (int I = 1; I <= wkArr.Cast<int>().Max(); I++) {

                for (int X = 0; X <= wkArr.GetUpperBound(0); X++) {
                    for (int Y = 0; Y <= wkArr.GetUpperBound(0); Y++) {
                        if (wkArr[X, Y] == I) {
                            PointsList.Add(new Point(80 * X + 40, 80 * Y + 40));
                        }
                    }
                }
            }
            return PointsList.ToArray();
        }
    }
}

実行結果