日本古来からある碁石を使ったパズル「碁石拾い」を解くプログラムをC#(コンソールアプリ)で書いてみました。
碁石拾いとは
ルールは、
1.縦・横に進みながら碁石を拾ってゆく。
2.途中の石は必ず取らなければならない。
3.どこから拾い始めてもよい。
4.碁石のない場所で曲がることは出来ない。また、元の方向へ引き返すことは出来ない。
です。詳しくは、
などを参照してください。
深さ優先探索で解を求める
どこから拾い始めても良いということなので、石が置いてあるすべての場所に対して、その位置を開始位置として、深さ優先の探索で解を求めています。
n個の石が置いてある場合は、最大でn回探索を行います。解が見つかった時点で探索は終了しています。
主要なクラスは、Solverクラスと、Boardクラスです。Solverクラスはパズルを解くクラス。Boardクラスは碁盤を表すクラスです。
Solverクラスでは、コンストラクタで盤面の初期状態を渡してもらっていますので、どのようなパターンでも解くことができます。
C#のコード
以下に、作成したC#のコードを簡単な説明とともに載せています。
Stoneクラス / Boardクラス
Stoneクラスは、碁盤に置く碁石を表すクラスです。
Boardクラスは碁盤を表します。BoardBaseクラスを継承しています。BoardBaseクラスは最後に示します。
using System;
using System.Linq;
using Gushwell.Puzzle;
namespace GoishiHiroi {
class Stone {
public static readonly Stone Empty = new Stone { Value = '.' };
public static readonly Stone White = new Stone { Value = 'O' };
public char Value { get; set; }
}
class Board : BoardBase<Stone> {
// コンストラクタ
public Board(char[,] data) : base(data.GetLength(0), data.GetLength(1)) {
for (int x = 0; x < data.GetLength(0); x++)
for (int y = 0; y < data.GetLength(1); y++)
this[x + 1, y + 1] = data[x, y] == ' ' ? Stone.Empty : Stone.White;
}
// コピーコンストラクタ
public Board(Board board) : base(board) {
}
// すべてを取り除けたか
internal bool IsFin() {
return GetAllIndexes().All(p => this[p] == Stone.Empty);
}
// directionの方向へ移動
public int Go(int p, int direction) {
while (this[p] != null) {
if (this[p] == Stone.White)
return p;
p += direction;
}
return -1;
}
public int Left {
get { return -1; }
}
public int Right {
get { return 1; }
}
public int Up {
get { return -this.XSize - 2; }
}
public int Down {
get { return this.XSize + 2; }
}
public void Print() {
for (int y = 1; y <= this.YSize; y++) {
for (int x = 1; x <= this.XSize; x++) {
var p = this[x, y];
Console.Write(p.Value + " ");
}
Console.WriteLine();
}
Console.WriteLine();
}
}
}
Solverクラス
Solverクラスは問題を解くクラスです。
盤面操作の面倒なところはBoardクラスに隠蔽されているので、Solveerクラスはとてもすっきりしたものになっています。
SolveInnerが、引数pを開始位置とした時の解を求めるメソッドです。その骨格はとても単純なものです。再帰処理の威力ですね。
なお、解が求まったところで探索を終了しています（すべてのパターンを探索していない）。
つまり、最適解が見つかる保証はありません。最適解を求めようとすると、膨大な探索を行うことになり、碁石のパターンによっては現実的な時間で探索が終わらない可能性もあったため、このようなロジックにしています。
using System;
using System.Collections.Generic;
using System.Linq;
namespace GoishiHiroi {
class Solver {
private Board _board;
public List<int> Moves { get; set; } = new List<int>();
public Solver(char[,] data) {
_board = new Board(data);
}
public bool Solve(int start) {
return SolveInner(start, 0);
}
private bool SolveInner(int p, int prevDir) {
if (_board.IsFin()) {
return true;
}
foreach (var dir in Directions(prevDir)) {
var np = _board.Go(p, dir);
if (np < 0)
continue;
_board[np] = Stone.Empty;
Moves.Add(np);
if (SolveInner(np, dir))
return true;
_board[np] = Stone.Black;
Moves.Remove(np);
}
return false;
}
private IEnumerable<int> Directions(int prevDir) {
if (prevDir != _board.Left)
yield return _board.Right;
if (prevDir != _board.Right)
yield return _board.Left;
if (prevDir != _board.Up)
yield return _board.Down;
if (prevDir != _board.Down)
yield return _board.Up;
}
public IEnumerable<int> StoneIndexes() {
return _board.GetAllIndexes().Where(i => _board[i] == Stone.Black);
}
}
}
Programクラス
碁盤に石を置き、Solverクラスを使い解を求めています。結果はListでどの順番で石を取ったかを表しています。このintの値は、Boardを1次元配列としてみた時のインデックスです。
この値を使い、視覚的にわかるように石を順に取っていくのが、Printメソッドです。石を'X'、取りさった後は'='で表示しています。Enterキーを押すごとに、石を取っていきます。
このとき、Console.SetCursorPosition()メソッドを使って、画面が流れないように工夫しています。
データはテキストファイルから取得しています。なお、Boardのサイズに制約はないので、大きなサイズのデータを与えることもできます。
using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
namespace GoishiHiroi {
class Program {
static void Main(string[] args) {
char[,] data = Initialize();
var answer = Solve(data);
if (answer == null)
Console.WriteLine("解は見つかりませんでした");
else
Print(data, answer);
}
// 初期状態設定
private static char[,] Initialize() {
string[] lines = File.ReadAllLines("data.txt")
.Select(x => x.Trim('"'))
.ToArray();
int w = lines[0].Length;
int h = lines.Length;
char[,] data = new char[w, h];
for (var y = 0; y < h; y++) {
for (int x = 0; x < w; x++) {
data[x, y] = lines[y][x];
}
}
return data;
}
// 開始位置はすべての石が対象。ただし、解が見つかったところで探索はやめる。
private static List<int> Solve(char[,] data) {
var solver = new Solver(data);
foreach (var p in solver.StoneIndexes()) {
if (solver.Solve(p))
return solver.Moves;
}
return null;
}
private static void Print(char[,] data, IEnumerable<int> ans) {
Console.Clear();
var board = new Board(data);
board.Print();
foreach (var p in ans) {
Console.SetCursorPosition(0, data.GetLength(1) + 1);
Console.Write("Enterキーで進みます");
Console.ReadLine();
var (x, y) = board.ToLocation(p);
// SetCursorPositionの座標は0から始まるので１引く
Console.SetCursorPosition(--x * 2, --y);
Console.Write('=');
}
Console.SetCursorPosition(0, data.GetLength(1) + 1);
}
}
}
入力データファイルとして、以下のようなデータを用意します。
" O O "
" OOOOOO "
" O O "
" O O "
" OOOOOO "
" O O "
" "
全ての行が同じ長さかどうかが見てわかるように、データには前後に"をつけるようにしています。
BoardBaseクラス
前述の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 Gushwell.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);
}
}
このBoardBaseクラスは、他のパズルでも利用していく予定です。
実行例
実行途中の画面です。Enterキーを押すごとに、ひとつ石を拾います。
Oが碁石、=が石を取った後を示しています。
. . = . . = . .
. O O O O = = .
. . O . . O . .
. . O . . O . .
. O O O = = = .
. . O . . O . .
. . . . . . . .
Enterキーで進みます
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。