ALDS1_13_A: 8 Queens Problem

問題へのリンク

C#のソース

using System;
using System.Collections.Generic;
using System.Linq;

//Q089 8クイーン問題 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_13_A&lang=jp
class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("2");
            WillReturn.Add("2 2");
            WillReturn.Add("5 3");
            //......Q.
            //Q.......
            //..Q.....
            //.......Q
            //.....Q..
            //...Q....
            //.Q......
            //....Q...
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    const int UB = 8 - 1;

    struct JyoutaiDef
    {
        internal int CurrX;
        internal char[,] BanArr;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();

        int[] wkArr = { };
        Action<string> SplitAct = pStr =>
            wkArr = pStr.Split(' ').Select(pX => int.Parse(pX)).ToArray();

        char[,] BanArr = new char[UB + 1, UB + 1];
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                BanArr[X, Y] = '.';
            }
        }

        foreach (string EachStr in InputList.Skip(1)) {
            SplitAct(EachStr);
            BanArr[wkArr[1], wkArr[0]] = 'Q';
        }
        //PrintBan(BanArr);

        //深さ優先探索で解を探索
        var Stk = new Stack<JyoutaiDef>();
        JyoutaiDef WillPush;
        WillPush.CurrX = 0;
        WillPush.BanArr = BanArr;
        Stk.Push(WillPush);

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

            //クイーンをセットするX座標を求める
            int WillSetX = -1;
            for (int X = Popped.CurrX; X <= UB; X++) {
                bool HasQueen = false;
                for (int Y = 0; Y <= UB; Y++) {
                    if (Popped.BanArr[X, Y] == 'Q') {
                        HasQueen = true; break;
                    }
                }
                if (HasQueen == false) {
                    WillSetX = X; break;
                }
            }

            //クリア判定
            if (WillSetX == -1) {
                PrintBan(Popped.BanArr);
                return;
            }

            for (int Y = 0; Y <= UB; Y++) {
                if (IsValid(Popped.BanArr, WillSetX, Y) == false)
                    continue;

                WillPush.CurrX = WillSetX + 1;
                WillPush.BanArr = (char[,])Popped.BanArr.Clone();
                WillPush.BanArr[WillSetX, Y] = 'Q';
                Stk.Push(WillPush);
            }
        }
    }

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

        //下チェック
        for (int Y = TargetY + 1; Y <= UB; Y++) {
            if (pBanArr[TargetX, Y] == 'Q') return false;
        }

        //左チェック
        for (int X = TargetX - 1; 0 <= X; X--) {
            if (pBanArr[X, TargetY] == 'Q') return false;
        }

        //右チェック
        for (int X = TargetX + 1; X <= UB; X++) {
            if (pBanArr[X, TargetY] == 'Q') return false;
        }

        //左下チェック
        for (int X = TargetX - 1, Y = TargetY + 1;
             0 <= X && X <= UB && 0 <= Y && Y <= UB; X--, Y++) {
            if (pBanArr[X, Y] == 'Q') return false;
        }

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

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

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

        return true;
    }

    // 2次元配列のデバッグ出力
    static void PrintBan(char[,] pBanArr)
    {
        for (int Y = 0; Y <= pBanArr.GetUpperBound(1); Y++) {
            for (int X = 0; X <= pBanArr.GetUpperBound(0); X++) {
                Console.Write(pBanArr[X, Y]);
            }
            Console.WriteLine();
        }
    }
}

解説

1列にクイーンを1個おくので、
置く場所を深さ優先探索で求めてます。