2009年01月31日

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

  
さて、それでは本題の 8クィーンゲームです。
8×8のチェス盤に2人で交互にクィーンを置いていき、自分の手番のときに置き場所が無いほうが負けというゲームです。
なお、すでに置かれているクィーン(自分が置いたものも含め)の利き筋に新しいクィーンを置くことはできません。

前回のコードをかなりの部分(特にChessboardクラス)を流用しています。

なお、回転、鏡像のものを省くために、最初の一手については、打つ場所を限定しています。

実行した結果は、8×8の盤では、先手必勝でした。
なお、『ナノピコ教室」の解説によれば、10×10の盤では、後手必勝らしいのですが、僕のプログラムでは時間がかかりすぎて、途中で実行を中止してしまいました。

利き筋をその都度判定しているところを、クィーンを置いた際に、利き筋をマークするように変更することで、速度をはやくできると思いますが、時間もないので、今回はこの辺で。


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace _8QFight {
class Program {
static void Main(string[] args) {
Solver solver = new Solver(4);
char r = solver.Solve();
solver.Print();
if (r == Chessboard.Black)
Console.WriteLine("先手必勝です");
else
Console.WriteLine("後手必勝です");
}
}

class Record {
public Record Root;
public int PlaceX { get; set; }
public int PlaceY { get; set; }
public char Piece { get; set; }
public List<Record> Children { get; private set; }

public Record() {
Children = new List<Record>();
}

public void Add(Record rec) {
Children.Add(rec);
rec.Root = this.Root;
}

public void Clear() {
Children.Clear();
}

public void Print(int indent) {
if (Piece != 0)
Console.WriteLine("{0} {1} ({2},{3})", new string(' ', indent), Piece, PlaceX,PlaceY);
foreach (var x in Children)
x.Print(indent + 1);
}

public override string ToString() {
return string.Format("{0} ({1},{2})", Piece, PlaceX, PlaceY);
}
}

class Solver {
private Chessboard board;
public Record record;
private int width;
public Solver(int width) {
this.width = width;
}

public char Solve() {
int half = width / 2 - (width%2==0?1:0);
char win;
for (int y = 0; y <= half; y++) {
for (int x = y; x <= half; x++) {
int p = y * width + x;
this.board = new Chessboard(width);
record = new Record();
record.Root = record;
Record nr = Put(p, Chessboard.Black, record);

win = Evaluate(Chessboard.White, nr);
if (win == Chessboard.Black) {
return win;
}
}
}
return Chessboard.White;
}

public void Print() {
record.Print(0);
}

public char Evaluate(char piece, Record rec) {
foreach (var place in board.CanPutPlaces()) {
Record nr = Put(place, piece, rec);
try {
char win = Evaluate(Opponent(piece), nr);
if (win == piece) {
rec.Clear();
rec.Add(nr);
return piece;
}
} finally {
board.UnPut(place);
}
}
return Opponent(piece); // 候補が無い場合もここに来る。
}

private Record Put(int place, char piece, Record rec) {
board.Put(place, piece);
Record nr = new Record { PlaceX = place % width, PlaceY = place / width, Piece = piece };
rec.Add(nr);
return nr;
}

private char Opponent(char piece) {
return piece == Chessboard.Black ? Chessboard.White : Chessboard.Black;
}
}

class Chessboard {
public const char Empty = '.';
public const char White = 'O';
public const char Black = '#';
private const char Finished = '/';
private int maxsize;
private char[] cells;

public int Width { get; private set; }

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

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

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

public void Put(int place, char piece) {
cells[place] = piece;
}

public void UnPut(int place) {
cells[place] = Empty;
}

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

public bool CanPut(int place) {
var q = from x in Settled()
from p in Courses(x)
select p;
return q.All(p => place != p);
}

public IEnumerable<int> CanPutPlaces() {
for (int i = 0; i < cells.Length; i++)
if (cells[i] == Empty && (CanPut(i))) {
yield return i;
}
}

public IEnumerable<int> Settled() {
return Enumerable.Range(0, maxsize).Where(x => cells[x] != Empty);
}

public 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 cells) {
Console.Write(c);
if (++i == Width) {
Console.WriteLine();
i = 0;
}
}
Console.WriteLine();
}
}
}





※当記事に掲載したコードは、『ナノピコ教室・プログラミング問題集』(駒木悠二+有澤誠 編 共立出版株式会社)に掲載されている問題をGushwellがC#で解いたものです。

2009/2/4 追記
バグがあったので、コードを修正しました。(最初の一手で、打つ場所を限定している部分)
それと、10×10の盤で確かめてみました。まだ実行中ですが、途中経過から判断すると、2時間ちかくかかりそうです。
あまりにも遅すぎるので、速度改善するつもりです。


 

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