2018-04-07T10:17:58.000+09:00

C# で愚直にN-Queens問題

プログラミング学び直しシリーズ。Nクイーン問題 (8クイーン問題) をC# で愚直に解く。

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

class MainClass
{
    public static void Main(string[] args)
    {
        nQueen(
            int.Parse(Console.ReadLine())
        );
    }

    static void nQueen(int n)
    {
        var queens = new List<Queen>();
        for (int y = 0; y < n; y++)
        {
            for (int x = 0; x < n; x++)
            {
                if (check(queens, x, y))
                {
                    queens.Add(new Queen(x, y));
                    break;
                }
                else
                {
                    while (x == (n - 1) || y == (n - 1))
                    {
                        var q = queens.Last();
                        y = q.y;
                        x = q.x;
                        queens.Remove(q);
                    }
                }
            }
        }

        foreach (var q in queens)
        {
            Console.WriteLine(q);
        }
    }

    static bool check(List<Queen> queens, int x, int y)
    {
        foreach (var q in queens)
        {
            if (q.x == x || q.y == y || Math.Abs(x - q.x) == Math.Abs(y - q.y))
                return false;
        }
        return true;
    }

    class Queen
    {
        public int x { get; set; }
        public int y { get; set; }

        public Queen(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        public override string ToString()
        {
            return string.Format("x={0}, y={1}", x, y);
        }

    }

}

出力例。例えば8の場合:

x=2, y=0
x=4, y=1
x=1, y=2
x=7, y=3
x=5, y=4
x=3, y=5
x=6, y=6
x=0, y=7