８クイーンパズルとは
８クイーンパズルとは、チェスのクイーンを8x8のチェス盤に、8つのクイーンを互いに取られないように配置するパズルです。
この問題は、ハノイの塔と並んで再帰処理の練習問題としてとても有名ですね。
Nクイーンパズルとして考える
ここでは8x8限定ではなく、任意の NxNに対応できるようなプログラムとして作成しました。
アルゴリズム的にはとてもオーソドックスなものだと思います。ちゃんと 92通りの解が求まっているので間違ってはいないかと。
例えば、4x4の盤だとすると、
-
まず、1行目に置いてみて、
-
次に2行目で、条件に合う位置に置いてみて、
-
次に3行目で、条件に合う位置に置いてみて、
-
次に4行目で、条件に合う位置に置いてみて、
-
最後まで来たので、解が得られたので列挙。
-
一つ戻って、4行目のクィーンを取り去って、別の条件に合う位置に置いてみて、
-
...
-
4行目のすべての位置で試し終わったら、3行目に戻って、3行目のクィーンを取り去って、別の条件に合う位置に置いてみて、...
と繰り返していきます。
いわゆるバックトラッキングアルゴリズムで、一種の深さ優先探索です。深さ優先で探索する際に、条件に一致していないものは探索から排除することで効率を上げています。
NxNのチェスの盤は、他のパズルでも利用しているBoardbase<T>クラスを継承したBoardクラスを定義して、１次元の配列としても、２次元配列としても利用できるようにしています。
ところで、この手のプログラムでいつも混乱してしまうのは、x軸とy軸の扱いです。
どちらが横軸でどちらが縦軸なんだろう？ってこと。
for (int x = 1; x < 8; x++)
for (int y = 1; y <= 8; y++)
Console.Write(board[x,y])
Console.WriteLine();
上のように、ついついxを外側のループで回すコードを書いちゃうんだけど、これだと、画面に表示されたときに、X軸が縦軸になっちゃうんですよね。
なので、横一列を求めるって時に、
- X固定でYを+1していくのか、
- Yを固定でxを+1していくのか
が混乱してしまって、コード書いているうちに縦と横が逆になってて、間違いに気が付かないってことが、何度となく起こりました。
そのため、このプログラムも含め、今後アップしていく予定のボードを使ったプログラムでは、
for (int y = 1; y <= 8; y++)
for (int x = 1; x < 8; x++)
Console.Write(board[x,y])
Console.WriteLine();
に統一しようと思います。
C#のコード
それでは、C#のコードを示します
Boardクラス / Pieceクラス
Boardは、nQueenパズルに特化した盤面を表すクラスです。BoardBaseクラス(後述)を継承しています。
Pieceクラスは、駒クラス。
using System;
using Puzzle;
using System.Collections.Generic;
using System.Linq;
namespace NQueenPuzzle {
class Piece {
public static readonly Piece Empty = new Piece { Value = '.' };
public static readonly Piece Queen = new Piece { Value = 'Q' };
public char Value { get; set; }
public override string ToString() {
return Value.ToString();
}
}
class Board : BoardBase<Piece> {
public int Size { get { return XSize; } }
public Board(int size) : base(size, size) {
foreach (var p in GetAllIndexes())
this[p] = Piece.Empty;
}
public Board(Board board) : base(board) {
}
public void Put(int place) {
this[place] = Piece.Queen;
}
public void Clear(int place) {
this[place] = Piece.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(1, y).Where(p => this[p] == Piece.Empty);
}
private IEnumerable<int> Settled() {
return GetAllIndexes().Where(p => this[p] == Piece.Queen);
}
private IEnumerable<int> Courses(int now) {
var (x, y) = ToLocation(now);
return Virtical(x, y)
.Concat(Horizontal(x, y))
.Concat(SlantL(x, y))
.Concat(SlantR(x, y)).Distinct();
}
public void Print() {
int i = 0;
foreach (var p in GetAllIndexes()) {
var c = this[p].Value;
Console.Write($"{c} ");
if (++i == Size) {
Console.WriteLine();
i = 0;
}
}
Console.WriteLine();
}
}
}
Solverクラス
nQueenを解くクラス。
盤面操作の面倒なところはBoardクラスに隠蔽されているので、Solveerクラスはとてもすっきりしたものになっています。
using System;
using System.Collections.Generic;
using System.Text;
namespace NQueenPuzzle {
class Solver {
private int count = 0;
public IEnumerable<Board> Solve(int n) {
var board = new Board(n);
return SolveInner(board, 1);
}
private IEnumerable<Board> SolveInner(Board board, int y) {
if (y > board.Size) {
count++;
yield return new Board(board);
}
foreach (int pos in board.Vacants(y)) {
if (board.CanPut(pos)) {
board.Put(pos);
foreach (var b in SolveInner(board, y + 1))
yield return b;
board.Clear(pos);
}
}
}
}
}
Programクラス
プログラムを制御するクラス。
Solverクラスを呼び出し解を求め、解を表示するだけの簡単なコードです。
using System;
namespace NQueenPuzzle {
class Program {
static void Main(string[] args) {
var solver = new Solver();
var bs = solver.Solve(8);
var count = 0;
foreach (var b in bs) {
b.Print();
count++;
}
Console.WriteLine(count);
}
}
}
ひとり言
ところで、nQueen問題なんて、もっと短いコードで書けるのに、と思った方もいると思います。僕もそれは否定しません。
BoardクラスやPieceクラスを定義せずに２次元配列を直接扱うようにすれば、確かにもっと短いコードになります。
しかし、わかりやすさが大きく損なわれます。
頭の回転が遅く短期記憶がさっぱりの僕は、このプログラムのように配列操作を隠蔽し抽象度を上げたほうがはるかに理解しやすいものになります。デバッグも楽です。コードを書く時にも一度に考える範囲が少なくて済みます。
そして、似たような問題に出会ったときに、プログラムの構造や考え方が再利用できるという利点も生まれてきます。
結果
8-クィーンパズルとして解いた結果を示します。Qがクィーンを置いた場所です。
Q . . . . . . .
. . . . . . Q .
. . . . Q . . .
. . . . . . . Q
. Q . . . . . .
. . . Q . . . .
. . . . . Q . .
. . Q . . . . .
Q . . . . . . .
. . . . . . Q .
. . . Q . . . .
. . . . . Q . .
. . . . . . . Q
. Q . . . . . .
. . . . Q . . .
. . Q . . . . .
Q . . . . . . .
. . . . . Q . .
. . . . . . . Q
. . Q . . . . .
. . . . . . Q .
. . . Q . . . .
. Q . . . . . .
. . . . Q . . .
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
. . . . . Q . .
Q . . . . . . .
. . . . Q . . .
. Q . . . . . .
. . . . . . . Q
. . Q . . . . .
. . . . . . Q .
. . . Q . . . .
... 途中省略 ...
. . Q . . . . .
. . . . Q . . .
. Q . . . . . .
. . . . . . . Q
. . . . . Q . .
. . . Q . . . .
. . . . . . Q .
Q . . . . . . .
. . Q . . . . .
. . . . . Q . .
. . . Q . . . .
. Q . . . . . .
. . . . . . . Q
. . . . Q . . .
. . . . . . Q .
Q . . . . . . .
92
Solverコンストラクタの引数に5を入れて、5-Queenとして解いた結果も示します。
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . . Q
. . Q . .
Q . . . .
. . . Q .
. . Q . .
Q . . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. Q . . .
. . . Q .
. Q . . .
. . . . Q
. . Q . .
Q . . . .
. . . . Q
. Q . . .
. . . Q .
Q . . . .
. . Q . .
. . . . Q
. . Q . .
Q . . . .
. . . Q .
. Q . . .
10
BoardBaseクラス
このBoardBaseクラスは、「碁石拾い」「コイン15 (10円玉、5円玉をつかったパズル)」で利用したものと同じものです。
前述のBoardクラスの基底クラスです。X × Y の盤面を表し、基本的な操作を定義しています。これは似たようなパズルでも再利用できるような汎用的な機能に絞っています。このBoardBaseクラスは、コンソールアプリに依存しない作りにしています。UWP、WinFormsでもそのまま使えると思います。
このBoardBaseを継承して、当パズル専用のBoardクラスを定義します。
内部では1次元配列を使っていますが、インデクサを定義して、1次元配列、2次元配列としても扱えるようにしています。
ただし、すべてのメソッドで１次元対応と２次元対応のものを用意するのは面倒なので、どちらか一方にしています。まあこれは好み以外の何物でもありません。
１次元のインデックスによるアクセスができるようにしている理由は、一重ループで処理が書けるので、コードが簡潔になるからです。LINQのコードも書きやすくなります。
2次元配列として見た場合の、X座標、Y座標は、0 からではなく、1から始まります。
つまり、board[1,1] は、いちばん左上を示し、8×8の盤ならば、board[8,8]が右下を示すことになります。
なお、盤の周りには番兵用の領域を用意しています。これにより範囲外かどうかの判断を簡単に出来るようにしています。これが成功したがどうかは微妙ですが...
上の図は 4×4の盤を表していますが、グレー部分が番兵が置いてある盤の周囲で、水色部分が実際の盤です。
盤面上の数値は、１次元配列のインデックスを表しています。
BoardBaseクラスはジェネリッククラスにしていて、そのパラメータの型は、盤面上に置けるクラスの型です。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Puzzle {
// 汎用の盤面クラス
// Tは、盤面に置けるオブジェクトの型。参照型でnew()ができれば何でも良い。
public abstract class BoardBase<T> where T : class, new() {
private T[] _pieces;
// 盤の行数（縦方向）
public int YSize { get; private set; }
// 盤のカラム数（横方向）
public int XSize { get; private set; }
// コンストラクタ
public BoardBase(int xsize, int ysize) {
this.YSize = ysize;
this.XSize = xsize;
_pieces = new T[(xsize + 2) * (ysize + 2)];
// 盤データの初期化 - 盤の周りはnull(番兵)をセットしておく
ClearAll();
}
// コピー用コンストラクタ
public BoardBase(BoardBase<T> board) {
XSize = board.XSize;
YSize = board.YSize;
this._pieces = board._pieces.ToArray();
}
// 番兵も含めたボード配列の長さ
public int BoardLength {
get { return _pieces.Length; }
}
// インデクサ (x,y)の位置の要素へアクセスする
public T this[int index] {
get { return _pieces[index]; }
set { _pieces[index] = value; }
}
// インデクサ (x,y)の位置の要素へアクセスする
public T this[int x, int y] {
get { return this[ToIndex(x, y)]; }
set { this[ToIndex(x, y)] = value; }
}
// Location から _coinのIndexを求める
public int ToIndex(int x, int y) => x + y * (XSize + 2);
// IndexからLocationを求める (ToIndexの逆演算)
public (int, int) ToLocation(int index) => (index % (XSize + 2), index / (XSize + 2));
// 本来のボード上の位置(index)かどうかを調べる
public virtual bool IsOnBoard(int index) {
if (0 <= index && index < BoardLength)
return this[index] != null;
return false;
}
// 全てのPieceをクリアする
public virtual void ClearAll() {
for (int index = 0; index < BoardLength; index++)
this[index] = null; // 番兵
foreach (var index in GetAllIndexes())
this[index] = new T(); // 初期値
}
// 盤上のすべての位置(index)を列挙する
public virtual IEnumerable<int> GetAllIndexes() {
for (int y = 1; y <= this.YSize; y++) {
for (int x = 1; x <= this.XSize; x++) {
yield return ToIndex(x, y);
}
}
}
// (x,y)からdirection方向の位置を列挙する (x,y)含む
public virtual IEnumerable<int> EnumerateIndexes(int x, int y, int direction) {
for (int index = ToIndex(x, y); IsOnBoard(index) && this[index] != null; index += direction)
yield return index;
}
// (x,y)から右(水平)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> Horizontal(int x, int y)
=> EnumerateIndexes(x, y, 1);
// (x,y)から下(垂直)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> Virtical(int x, int y)
=> EnumerateIndexes(x, y, this.XSize + 2);
// (x,y)から右斜め下(45度)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> SlantR(int x, int y)
=> EnumerateIndexes(x, y, this.XSize + 2 + 1);
// (x,y)から左斜め下(45度)の位置を列挙する (x,y)含む
public virtual IEnumerable<int> SlantL(int x, int y)
=> EnumerateIndexes(x, y, this.XSize + 2 - 1);
}
}
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。