Cマガ電脳クラブ(第148回) スライディング・スリー

問題

Fig.1のように，5×5の盤にＡ〜Ｅの計5個のコマが置いてある。
このうち3個のコマを動かして，
盤の縦5本横5本斜め2本の同一直線上に2個以上のコマがこないようにしたい。

1個のコマが移動できるのは1回の直進のみで，
タテヨコ・ナナメのどれかの方向に何マス移動してもよい (チェスのクイーンの動き) 。
ほかのコマを飛び越したり，重ねたりすることはできない。

また，3個のコマの移動は同時ではなく，1個ずつ順番に行われる。
Fig.1をスタートとして，どのコマをどのように動かせば完成できるだろうか。

    Fig.1  スライディング・スリーのコマの初期配置
            ┌─┬─┬─┬─┬─┐
            │　│　│　│　│　│
            ├─┼─┼─┼─┼─┤
            │　│　│Ａ│　│Ｂ│
            ├─┼─┼─┼─┼─┤
            │　│　│　│Ｃ│Ｄ│
            ├─┼─┼─┼─┼─┤
            │　│　│　│　│　│
            ├─┼─┼─┼─┼─┤
            │　│　│Ｅ│　│　│
            └─┴─┴─┴─┴─┘

ソース

using System;
using System.Collections.Generic;

class Program
{
    const int UB = 5 - 1;

    struct JyoutaiDef
    {
        internal char[,] BanArr;
        internal HashSet<char> UsedPieceNameSet;
    }

    static void Main()
    {
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.BanArr = new char[UB + 1, UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                WillPush.BanArr[X, Y] = ' ';
            }
        }
        WillPush.BanArr[2, 1] = 'A'; WillPush.BanArr[4, 1] = 'B';
        WillPush.BanArr[3, 2] = 'C'; WillPush.BanArr[4, 2] = 'D';
        WillPush.BanArr[2, 4] = 'E';
        WillPush.UsedPieceNameSet = new HashSet<char>();
        Stk.Push(WillPush);

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

            //クリア判定
            if (Popped.UsedPieceNameSet.Count == 3) {
                if (IsClear(Popped.BanArr)) {
                    Console.WriteLine("解を発見");
                    PrintBan(Popped.BanArr);
                }
                continue;
            }

            for (int X = 0; X <= UB; X++) {
                for (int Y = 0; Y <= UB; Y++) {
                    char CurrChar = Popped.BanArr[X, Y];
                    if (CurrChar == ' ') continue;
                    if (Popped.UsedPieceNameSet.Contains(CurrChar))
                        continue;

                    PointDef[] CanMovePosList = DeriveCanMovePosList(Popped.BanArr, X, Y);
                    foreach (PointDef EachPos in CanMovePosList) {
                        WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                        WillPush.BanArr[X, Y] = ' ';
                        WillPush.BanArr[EachPos.X, EachPos.Y] = CurrChar;
                        WillPush.UsedPieceNameSet = new HashSet<char>(Popped.UsedPieceNameSet);
                        WillPush.UsedPieceNameSet.Add(CurrChar);
                        Stk.Push(WillPush);
                    }
                }
            }
        }
    }

    //クリア判定
    static bool IsClear(char[,] pBanArr)
    {
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (pBanArr[X, Y] == ' ') continue;
                if (IsValid(pBanArr, X, Y) == false) return false;
            }
        }
        return true;
    }

    //座標を引数として、既存の駒の効き筋ならFalseを返す
    static bool IsValid(char[,] pBanArr, int pCurrX, int pCurrY)
    {
        //上チェック
        for (int Y = pCurrY - 1; 0 <= Y; Y--)
            if (pBanArr[pCurrX, Y] != ' ') return false;

        //下チェック
        for (int Y = pCurrY + 1; Y <= UB; Y++)
            if (pBanArr[pCurrX, Y] != ' ') return false;

        //左チェック
        for (int X = pCurrX - 1; 0 <= X; X--)
            if (pBanArr[X, pCurrY] != ' ') return false;

        //右チェック
        for (int X = pCurrX + 1; X <= UB; X++)
            if (pBanArr[X, pCurrY] != ' ') return false;

        //左下チェック
        for (int X = pCurrX - 1, Y = pCurrY + 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y++)
            if (pBanArr[X, Y] != ' ') return false;

        //左上チェック
        for (int X = pCurrX - 1, Y = pCurrY - 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y--) {
            if (pBanArr[X, Y] != ' ') return false;
        }

        //右下チェック
        for (int X = pCurrX + 1, Y = pCurrY + 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y++) {
            if (pBanArr[X, Y] != ' ') return false;
        }

        //右上チェック
        for (int X = pCurrX + 1, Y = pCurrY - 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y--) {
            if (pBanArr[X, Y] != ' ') return false;
        }

        return true;
    }

    struct PointDef
    {
        internal int X;
        internal int Y;
    }

    //座標を引数として、移動可能な座標の配列を返す
    static PointDef[] DeriveCanMovePosList(char[,] pBanArr, int pCurrX, int pCurrY)
    {
        var WillReturn = new List<PointDef>();

        Func<int, int, bool> AddFunc = (pX, pY) =>
        {
            if (pBanArr[pX, pY] == ' ') {
                WillReturn.Add(new PointDef() { X = pX, Y = pY });
                return true;
            }
            return false;
        };

        //上チェック
        for (int Y = pCurrY - 1; 0 <= Y; Y--)
            if (AddFunc(pCurrX, Y) == false) break;

        //下チェック
        for (int Y = pCurrY + 1; Y <= UB; Y++)
            if (AddFunc(pCurrX, Y) == false) break;

        //左チェック
        for (int X = pCurrX - 1; 0 <= X; X--)
            if (AddFunc(X, pCurrY) == false) break;

        //右チェック
        for (int X = pCurrX + 1; X <= UB; X++)
            if (AddFunc(X, pCurrY) == false) break;

        //左下チェック
        for (int X = pCurrX - 1, Y = pCurrY + 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y++) {
            if (AddFunc(X, Y) == false) break;
        }

        //左上チェック
        for (int X = pCurrX - 1, Y = pCurrY - 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y--) {
            if (AddFunc(X, Y) == false) break;
        }

        //右下チェック
        for (int X = pCurrX + 1, Y = pCurrY + 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y++) {
            if (AddFunc(X, Y) == false) break;
        }

        //右上チェック
        for (int X = pCurrX + 1, Y = pCurrY - 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X++, Y--) {
            if (AddFunc(X, Y) == false) break;
        }

        return WillReturn.ToArray();
    }

    //盤面を出力
    static void PrintBan(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();
        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                char CurrChar = pBanArr[X, Y];
                if (CurrChar == ' ') sb.Append('□');
                else sb.Append((char)('Ａ' + pBanArr[X, Y] - 'A'));
            }
            sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

実行結果

解を発見
□□□□Ｄ
□Ｂ□□□
□□□Ｃ□
Ａ□□□□
□□Ｅ□□

解説

深さ優先探索でナイーブに解いてます。

ARC-001-C パズルのお手伝い