2009年02月11日

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

  
1月31日の記事の続きです。

8Queenゲームですが、あまりにも遅いので早くしてみました。

変更点
・Chessboardのデータ構造の変更
・クィーンの置ける場所の判定方法の変更
の2点。

Chessboardのデータ構造は、チェスボードの周囲もデータに含め、利き筋を調べる際に「ボードから出たら」という判断を簡単にできるようにしました。
斜めの利き筋を調べるコードは行数は増えましたが、格段に理解しやすくなりました。
また、クィーンが置けるかどうかの判定は、クィーンを置く際に、他のクィーンの利き筋かどうかを調べて、置けるかどうかを判定するのではなく、クィーンを置いた時に、利き筋にマークをつけ、マークがある場所には置くことができないという判断に変更しました。
また、この変更にともない、一手先を調べる際にChessboardのクローンを作成し、そのクローンを使うようにしました。

実際に10×10のボードの場合どれくらいの時間でできるかを調べてみると、
僕のノートPCでは、1分5秒で終わりました。前のプログラムが2時間くらいかかっていたわけですから、100倍以上の速度アップとなりました。

ちなみに、『ナノピコ教室」の解答をい見ると、当時(1974年ごろ)の汎用機 HITAC8410で、100分で解けたとありました。
HITAC8410がどれくらいの速度なのかがわかりませんが、今のPCは、当時のコンピュータよりは、たぶん数万倍は早いと思う(勝手な想像です)ので、まだまだ速度改善はできるのかも知れませんが、その方法を思いつかないので、この辺でやめておきます。

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

namespace _8QFight {
class Program {
static void Main(string[] args) {
Stopwatch sw = new Stopwatch();
sw.Start();

Solver solver = new Solver(8);
char r = solver.Solve();
sw.Stop();
solver.Print();

if (r == Chessboard.Black)
Console.WriteLine("先手必勝です");
else
Console.WriteLine("後手必勝です");
Console.WriteLine(sw.Elapsed);
}
}

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}", Piece, PlaceX);
}
}

class Solver {
public Record record;
private int Width;
public Solver(int width) {
record = new Record();
record.Root = record;
Width = width;
}

public char Solve() {
Chessboard board;
board = new Chessboard(Width);

int half = Width / 2 + Width % 2;
char win;
for (int y = 1; y <= half; y++) {
for (int x = y; x <= half; x++) {
int p = y * (Width+2) + x;
board = new Chessboard(Width);
record = new Record();
record.Root = record;

Record nr = Put(board,p, Chessboard.Black,record);

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

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

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

private Record Put(Chessboard board,int place, char piece, Record rec) {
board.Put(place, piece);
Record nr = new Record { PlaceX = place%(Width+2), PlaceY=place/(Width+2), 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 = '#';
public const char Edge = ' ';
public const char Not = '-';
private const char Finished = '/';

private int maxsize;
private char[] cells;
private int startIndex;
private int endIndex;
private int OuterWidth { get; set; }
public int Width { get; private set; }

private Chessboard() {
}

public Chessboard(int width) {
this.Width = width;
OuterWidth = width + 2;
startIndex = OuterWidth + 1;
endIndex = OuterWidth * (OuterWidth - 1) - 2;
this.maxsize = (OuterWidth) * (OuterWidth);
cells = Enumerable.Repeat(Edge, maxsize).ToArray();
for (int x = 1; x <= width; x++)
for (int y = 1; y <= width; y++)
cells[y * (OuterWidth) + x] = Empty;
}

public Chessboard Clone() {
Chessboard nb = new Chessboard();
nb.Width = this.Width;
nb.OuterWidth = this.OuterWidth;
nb.startIndex = this.startIndex;
nb.endIndex = this.endIndex;
nb.maxsize = this.maxsize;
nb.cells = (char[])this.cells.Clone();
return nb;
}


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

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

public void Put(int place, char piece) {
foreach (var i in Courses(place))
if (cells[i] == Empty)
cells[i] = Not;
cells[place] = piece;
}

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

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

public bool CanPut(int place) {
return (cells[place] == Empty);
}

public IEnumerable<int> CanPutPlaces() {
for (int i = startIndex; i <= endIndex; i++ )
if (CanPut(i)) {
yield return i;
}
}

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

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

public IEnumerable<int> Horizontal(int now) {
return Enumerable.Range((now / OuterWidth) * OuterWidth+1, Width);
}

// 右上がり
public IEnumerable<int> SlantR(int now) {
int w1 = OuterWidth - 1;
int i = now - w1;
while (cells[i] != Edge) {
yield return i;
i -= w1;
}
i = now + w1;
while (cells[i] != Edge) {
yield return i;
i += w1;
}
}

public IEnumerable<int> SlantL(int now) {
int w1 = OuterWidth + 1;
int i = now - w1;
while (cells[i] != Edge) {
yield return i;
i -= w1;
}
i = now + w1;
while (cells[i] != Edge) {
yield return i;
i += w1;
}
}

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




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


 

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