プログラミング学び直しシリーズ。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