エイト・クイーン

エイト・クイーン - Wikipedia のプログラムを書いてみました。

using System;

class Loc {
    public int Row { get; private set; }
    public int Col { get; private set; }
    public Loc(int row, int col) {
        Row = row;
        Col = col;
    }
}

class EightQueen {
    static void Display(Loc[] g) {
        int n = g.Length;
        for (int i = 0; i < n; i++) {
            Loc loc = g[i];
            for (int j = 0; j < n; j++) {
                Console.Write(loc.Col == j ? "Q" : ".");
            }
             Console.WriteLine();
        }
        Console.WriteLine();
    }

    static bool IsConflict(Loc loc, int n, Loc[] g) {
        for (int i = 0; i < n; i++) {
            // 縦/横でぶつかる
            if (loc.Row == g[i].Row || loc.Col == g[i].Col)
                return true;

            // ななめでぶつかる
            if (Math.Abs(loc.Row - g[i].Row) == Math.Abs(loc.Col - g[i].Col))
                return true;
        }
        return false;
    }

    static int Calc(int row, int n, Loc[] g) {
        if (row == n) {
            Display(g);
            return 1;
        }

        int ret = 0;
        for (int i = 0; i < n; i++) {
            var loc = new Loc(row, i);
            if (!IsConflict(loc, row, g)) {
                g[row] = loc;
                ret += Calc(row+1, n, g);
            }
        }
        return ret;
    }

    static void Queen(int n) {
        int ans = Calc(0, n, new Loc[n]);
        Console.WriteLine("n:{0} {1}", n, ans);
    }

    static void Main() {
        Queen(8);
    }
}

実行結果です。

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Q.......
.....Q..
.......Q
..Q.....
......Q.
...Q....
.Q......
....Q...

(省略)

.......Q
...Q....
Q.......
..Q.....
.....Q..
.Q......
......Q.
....Q...

n:8 92