2009年01月29日

『ナノピコ教室』:8クイーンゲーム(1)

  

またまた、『ナノピコ教室』の問題です。
問題は、「8-Queenゲーム」で先手必勝かどうかを調べる問題なのですが、まずは、良く知れ渡っている「8-Queenパズル」をC#で解いてみることにしました。

8クイーンパズルとは、チェスのクイーンを8x8のチェス盤に、8つのクイーンを互いに取られないように配置するパズルです。

たとえば、こんな感じ。

8Queen

この問題は、再帰処理の練習問題としてはとても有名ですね。
もちろん、8x8限定ではなく、任意の NxNに対応できるようなプログラムとして作成しました。
アルゴリズム的には高速化などの手法を採っていないので、オーソドックスなものだと思います。

NxNのチェスの盤は、1次元の配列として表現しています。
なお、LINQの練習を兼ねて、IEnumerable を多用しています。
Chessboardクラスは、もっと簡単になるような気がします。特にクイーンの通り道である縦横斜めを求める部分はもう少し簡単にならないものかな。

ちゃんと 92通りの解が求まっているので間違ってはいないと思います。

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

namespace _8Queen {
class Program {
static void Main(string[] args) {
Puzzle p = new Puzzle();
p.Solve(8);
}
}

class Puzzle {
private int count = 0;

public void Solve(int n) {
Chessboard board = new Chessboard(n);
SolveInner(board,0);
Console.WriteLine(count);
}

private void SolveInner(Chessboard board,int y) {
if (y >= board.Width) {
board.Print();
count++;
return;
}
foreach (int pos in board.Vacants(y)) {
if (board.CanPut(pos)) {
board.Put(pos);
SolveInner(board, y + 1);
board.Clear(pos);
}
}
}
}

public class Chessboard {
private const char Empty = '.';
private const char Queen = 'Q';
private int maxsize;
private char[] board;

public int Width { get; private set; }

public Chessboard(int width) {
this.Width = width;
this.maxsize = width * width;
board = Enumerable.Repeat(Empty, maxsize).ToArray();
}

private int X(int now) {
return now % Width;
}

private int Y(int now) {
return now / Width;
}

public void Put(int place) {
board[place] = Queen;
}

public void Clear(int place) {
board[place] = Empty;
}

public bool CanPut(int place) {
foreach (int x in Settled()) {
foreach (int p in Courses(x)) {
if (place == p)
return false;
}
}
return true;
}

public IEnumerable<int> Vacants(int y) {
return Horizontal(y * Width).Where(x => board[x] == Empty);
}

private IEnumerable<int> Settled() {
return Enumerable.Range(0, maxsize)
.Where(x => board[x] == Queen);
}

private IEnumerable<int> Courses(int now) {
return Virtical(now)
.Concat(Horizontal(now))
.Concat(SlantL(now))
.Concat(SlantR(now)).Distinct();
}

private IEnumerable<int> Virtical(int now) {
int m = now % Width;
return Enumerable.Range(0, Width)
.Select(i => i * Width + m);
}

private IEnumerable<int> Horizontal(int now) {
return Enumerable.Range((now / Width) * Width, Width);
}

private IEnumerable<int> SlantR(int now) {
int w1 = Width - 1;
int first = now - Math.Min(w1- X(now), Y(now)) * w1;
int last = now + Math.Min(X(now), w1 - Y(now)) * w1;
for (int i = first; i <= last; i += w1)
yield return i;
}

private IEnumerable<int> SlantL(int now) {
int w1 = Width + 1;
int first = now - Math.Min(X(now), Y(now)) * w1;
int last = now + Math.Min(Width - 1 - X(now), Width - 1 - Y(now)) * w1;
for (int i = first; i <= last; i += w1)
yield return i;
}

public void Print() {
int i = 0;
foreach (var c in board) {
Console.Write(c);
if (++i == Width) {
Console.WriteLine();
i = 0;
}
}
Console.WriteLine();
}
}
}



 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51740610