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

■■■問題■■■

高橋君は、パズルが好きです。今日は、8クイーン問題に挑戦しようとしています。
8クイーン問題とは、
8×8 のチェスボード上の縦・横・斜め45度の同一直線状にそれぞれクイーンが1つしか存在しないように、
合計8つのクイーンを置く問題です。



図:出力例1の図。縦・横・斜め45度の同一直線状にそれぞれクイーンが1つのみ存在する。

高橋君は、3つのクイーンを置いたところで残りのクイーンをどう置いたら良いのか判らなくなってしまいました。
残りの5つのクイーンを含めた8つのクイーンの位置を求めなさい。 

■■■入力■■■

c11 c12 ・・・ c18
c21 c22 ・・・ c28
・
・
c81 c82 ・・・ c88

●1行目から 8行目の各行は 8文字の文字列が与えられる。
●i行目の先頭から j番目の文字である cij は、i行目j列目にクイーンが置かれているかどうかを表す。
●cij は、'.' もしくは 'Q' で与えられ、
  '.' であればクイーンが置かれていないことを、
  'Q' であればクイーンが置かれていることを表す。

■■■出力■■■

8つのクイーンを置き終わった後の状態のうちの1つを、入力と同様のフォーマットで出力せよ。
答えが存在しない場合は、"No Answer"と1行で出力せよ。 

C#のソース

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

class Program
{
    static string InputPattern = "Input1";

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

        if (InputPattern == "Input1") {
            WillReturn.Add("........");
            WillReturn.Add("........");
            WillReturn.Add(".......Q");
            WillReturn.Add("........");
            WillReturn.Add("..Q.....");
            WillReturn.Add("........");
            WillReturn.Add(".Q......");
            WillReturn.Add("........");
            //Q.......
            //....Q...
            //.......Q
            //.....Q..
            //..Q.....
            //......Q.
            //.Q......
            //...Q....
            //上記のようにクイーンを置いた時、条件を満たすことが出来ます
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add(".....Q..");
            WillReturn.Add(".Q......");
            WillReturn.Add("........");
            WillReturn.Add("........");
            WillReturn.Add("........");
            WillReturn.Add("Q.......");
            WillReturn.Add("........");
            WillReturn.Add("........");
            //No Answer
            //初期配置で既に1行目と6行目のクイーンが斜め45度の同一直線状に存在するので、
            //この地点で条件を満たしておらず答えは存在しません。
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static int UB = 8 - 1;

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

    static void Main()
    {
        List<string> InputList = GetInputList();
        char[,] BanArr = new char[UB + 1, UB + 1];
        for (int Y = 0; Y <= InputList.Count - 1; Y++) {
            for (int X = 0; X <= InputList[Y].Length - 1; X++) {
                BanArr[X, Y] = InputList[Y][X];
            }
        }

        //既存の盤面での有効チェック
        for (int X = 0; X <= UB; X++) {
            for (int Y = 0; Y <= UB; Y++) {
                if (BanArr[X, Y] == 'Q') {
                    if (IsValid(BanArr, X, Y) == false) {
                        Console.WriteLine("No Answer");
                        return;
                    }
                }
            }
        }

        //深さ優先探索で解を探索
        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) {
                PrintAnswer(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);
            }
        }
        Console.WriteLine("No Answer");
    }


    //座標を引数として、既存のクイーンの効き筋なら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;
    }

    //解を出力
    static void PrintAnswer(char[,] pBanArr)
    {
        var sb = new System.Text.StringBuilder();

        for (int Y = 0; Y <= UB; Y++) {
            for (int X = 0; X <= UB; X++) {
                sb.Append(pBanArr[X, Y]);
            }
            if (Y < UB) sb.AppendLine();
        }
        Console.WriteLine(sb.ToString());
    }
}

解説

深さ優先探索で解いてます。