Less Than Threeとは
このパズルの名前「Less Than Three」は僕が勝手につけた名前です。
以下のような問題です。
- 6×6の格子点上に、黒石12個、白石12個を置いていきます。
- このとき、格子点上を繋ぐ直線上（縦、横、斜め）に3個以上の石を置いてはいけません。
- この時の斜めの直線は、以下に示すような、45度の斜め線以外の直線も考慮に入れます。
どうやって解いているか
この問題の解き方ですが、まず、横方向だけに注目して考えて見ることにします。どの直線にも３個以上置いてはいけないのですから、必ず横一列（１行） に2個ずつ置いていく必要があります。そうしないと12個の石を置くことができません。
２つの石を横一列（１行）のどこの置くかは、6個の要素から2個を取り出す組み合わせとなりますね。
ですので、まずは組み合わせを求める必要があります。これは、「n個の要素からk個を選ぶ組合せを列挙する」で示しCombinationというクラスをそのまま利用します。
このCombinationクラスで得られた結果を元に、石を横一列ごとに２つずつ置いていきます。
その際、石を置いた点を通る８つの直線すべてで、同じ色の石が２つ以内かを調べ、すべてが２つ以内ならば、次の行に石を置いていきます。
同じ色の石が３つ以上の直線があれば、失敗なのでバックトラックします。
6行すべてに石を置き終わったら、同じように白石を１行目、２行目、３行目...と石を置いていき、最後の行まで行けば、解が求まったことになります。
解が求まった時点で、その解をプリントしています。
ひとつの解が求まっても終わりとせず、すべての解を求めています。ただし、回転、鏡像などは除外していません。
IObserver / IObservable インターフェース
なお、このプログラムは、IObserver<T> / IObservable<T>インターフェースを利用しています。
Solverクラスには、解が見つかったことを通知する機能を持たせています。これをIObservable<T>を使って実装しています。
ジェネリックの型パラメータTは、オブザーバーへの通知情報を示すクラスであり、解の状態を保持しているBoardクラスのオブジェクトです。
IObservable<T>の具象クラス(Solver)が実装すべきメソッドはSubscribeです。 Subscribe メソッドは、オブザーバー・オブジェクト(通知を受け取るオブジェク ト)を受け取り、オブザーバーを登録します。
複数のオブザーバーを登録可能にするために、Listコレクションクラスでオブザーバーを保持します。といっても、このプログラムでは一つで十分なんですが、この手のプログラムのパターンにあわせてListにしています。
解が見つかったときに、OnNextメソッドを呼び出し、オブザーバーオブジェクト(購読者オブジェクト)に、解が見つかったことを知らせます。
購読者クラスは、ResultViewerクラスで、IObserver<Board>を実装しています。
OnNextメソッドで、結果をコンソールに出力しています。 以下 C#のコードを示します。
C#のコード
program.cs
プログラムの実行を司るクラスです。
using System;
namespace LessThanThreePuzzle {
class Program {
static void Main() {
Solver sol = new Solver();
sol.Subscribe(new ResultViewer());
sol.Solve();
}
}
}
Solver.cs
解を求めるクラスです。IObservable<Board>を実装しています。
using System;
using System.Collections.Generic;
using System.Linq;
namespace LessThanThreePuzzle {
public class Solver : IObservable<Board> {
private Board board = new Board();
private IEnumerable<int[]> _combinations;
public void Solve() {
// 重複無しの組み合わせを求める
_combinations = Combination.Enumerate(new int[] { 1, 2, 3, 4, 5, 6 }, 2, false)
.ToArray();
// まずは、1行目から黒を置いてゆく
InnerSolve(1, Stone.Black);
Complete();
}
// ｙで指定した行にstone(White or Black)を置く
public void InnerSolve(int y, Stone stone) {
if (y == 7) {
if (stone == Stone.Black)
// 今度は、１行目から白を置いてゆく
InnerSolve(1, Stone.White);
else if (stone == Stone.White) {
// 黒白両方置き終わった（解が見つかったので通知する)
Publish(board);
}
return;
}
// y行にstoneを２つずつ置く
foreach (var combi in _combinations) {
int a = combi[0];
int b = combi[1];
if (board[a, y] != Stone.Empty || board[b, y] != Stone.Empty)
continue;
board[a, y] = stone;
board[b, y] = stone;
try {
if (board.IsCorrect(a, y, stone) && board.IsCorrect(b, y, stone)) {
// 条件を満たしているので、次の行を処理する。
InnerSolve(y + 1, stone);
}
} finally {
// バックトラックするため、状態を戻す。
board[a, y] = Stone.Empty;
board[b, y] = Stone.Empty;
}
}
return;
}
#region IObservable<Board> 関連
private List<IObserver<Board>> observers = new List<IObserver<Board>>();
public IDisposable Subscribe(IObserver<Board> observer) {
observers.Add(observer);
return observer as IDisposable;
}
#endregion
// 状況変化を知らせるために購読者に通知する
private void Publish(Board board) {
foreach (var observer in observers)
observer.OnNext(board);
}
// 終了を通知する
private void Complete() {
foreach (var observer in observers) {
observer.OnCompleted();
}
}
}
}
Board.cs
盤面を表すクラスです。BoardBase<T>から派生しています。
using System;
using System.Collections.Generic;
using System.Linq;
using Puzzle;
namespace LessThanThreePuzzle {
public class Stone {
public static readonly Stone Black = new Stone { Value = 'X' };
public static readonly Stone White = new Stone { Value = 'O' };
public static readonly Stone Empty = new Stone { Value = '.' };
public char Value { get; set; }
}
public class Board : BoardBase<Stone> {
private int Up;
private int Down;
private int Left;
private int Right;
private int UpperLeft;
private int UpperRight;
private int BottomLeft;
private int BottomRight;
private int UpperLeftLeft;
private int UpperRightRight;
private int BottomLeftLeft;
private int BottomRightRight;
private int UpperUpperLeft;
private int UpperUpperRight;
private int BottomBottomLeft;
private int BottomBottomRight;
public Board() : base(6, 6) {
foreach (var index in GetAllIndexes()) {
this[index] = Stone.Empty;
}
// 計算回数を少なくするために、事前に求めておく。
Up = this.ToDirection(0, -1);
Down = this.ToDirection(0, 1);
Left = this.ToDirection(-1, 0);
Right = this.ToDirection(1, 0);
UpperLeft = this.ToDirection(-1, -1);
UpperRight = this.ToDirection(1, -1);
BottomLeft = this.ToDirection(-1, 1);
BottomRight = this.ToDirection(1, 1);
UpperLeftLeft = this.ToDirection(-2, -1);
UpperRightRight = this.ToDirection(2, -1);
BottomLeftLeft = this.ToDirection(-2, 1);
BottomRightRight = this.ToDirection(2, 1);
UpperUpperLeft = this.ToDirection(-1, -2);
UpperUpperRight = this.ToDirection(1, -2);
BottomBottomLeft = this.ToDirection(-1, 2);
BottomBottomRight = this.ToDirection(1, 2);
}
// x,y 座標にpieceを置いたが、条件を満たしているか
internal bool IsCorrect(int x, int y, Stone piece) {
return EightLines(x, y)
.All(line => line.Count(p => this[p] == piece) <= 2);
}
// indexで指定した位置を通る８本の線を列挙する
public IEnumerable<int[]> EightLines(int x, int y) {
// 縦方向 （この配列要素順は問わない、以下も同様）
yield return this.EnumerateIndexes(x, y, Up).Skip(1)
.Concat(EnumerateIndexes(x, y, Down))
.ToArray();
// 横方向
yield return this.EnumerateIndexes(x, y, Left).Skip(1)
.Concat(EnumerateIndexes(x, y, Right))
.ToArray();
// 右斜め４５％ （＼）
yield return this.EnumerateIndexes(x, y, UpperLeft).Skip(1)
.Concat(EnumerateIndexes(x, y, BottomRight))
.ToArray();
// 左斜め４５％ （／）
yield return this.EnumerateIndexes(x, y, UpperRight).Skip(1)
.Concat(EnumerateIndexes(x, y, BottomLeft))
.ToArray();
// 下右右 （傾斜が緩い 右斜め）
yield return this.EnumerateIndexes(x, y, UpperLeftLeft).Skip(1)
.Concat(EnumerateIndexes(x, y, BottomRightRight))
.ToArray();
// 下左左 （傾斜が緩い 左斜め）
yield return this.EnumerateIndexes(x, y, UpperRightRight).Skip(1)
.Concat(EnumerateIndexes(x, y, BottomLeftLeft))
.ToArray();
// 下下右 （傾斜がきつい 右斜め）
yield return this.EnumerateIndexes(x, y, UpperUpperLeft).Skip(1)
.Concat(EnumerateIndexes(x, y, BottomBottomRight))
.ToArray();
// 下下左 （傾斜がきつい 左斜め）
yield return this.EnumerateIndexes(x, y, UpperUpperRight).Skip(1)
.Concat(EnumerateIndexes(x, y, BottomBottomLeft))
.ToArray();
}
}
}
ResultViewer.CS
ResultViewerが表示全体をつかさどるクラスで、IObserver<Board>を実装しています。
ResultViewerが表示全体をつかさどるということを考え、Boardクラスではなく、このクラスにPrintメソッドを定義しました。
using System;
namespace LessThanThreePuzzle {
public class ResultViewer : IObserver<Board> {
public void OnCompleted() {
Console.WriteLine("end");
}
public void OnError(Exception error) {
Console.WriteLine("{0}", error.Message);
}
public void OnNext(Board board) {
Print(board);
}
private void Print(Board board) {
for (int y = 1; y <= board.YSize; y++) {
for (int x = 1; x <= board.XSize; x++) {
Stone p = board[x, y];
Console.Write("{0} ", p.Value);
}
Console.WriteLine();
}
Console.WriteLine("---");
}
}
}
Combination.cs
組み合わせを求めるクラスです。
using System;
using System.Collections.Generic;
using System.Linq;
namespace LessThanThreePuzzle {
public static class Combination {
public static IEnumerable<T[]> Enumerate<T>(IEnumerable<T> items, int k, bool withRepetition) {
if (k == 1) {
foreach (var item in items)
yield return new T[] { item };
yield break;
}
foreach (var item in items) {
var leftside = new T[] { item };
// item よりも前のものを除く （順列と組み合わせの違い)
// 重複を許さないので、unusedから item そのものも取り除く
var unused = withRepetition ? items : items.SkipWhile(e => !e.Equals(item)).Skip(1).ToList();
foreach (var rightside in Enumerate(unused, k - 1, withRepetition)) {
yield return leftside.Concat(rightside).ToArray();
}
}
}
}
}
結果
想像以上に解が多かったです。一部だけを掲載しています。
X X O O . .
O O . X . X
. X . O X O
X O X . O .
O . O . X X
. . X X O O
---
X X . . O O
O . O X . X
. O X O X .
X . X O . O
O X . . O X
. O O X X .
---
X O X O . .
. O X . X O
X X . O . O
O . O . X X
O X . X O .
. . O X O X
---
X . X O O .
O O X . X .
X X . O . O
O . O . X X
. X . X O O
. O O X . X
---
X . X O O .
. O X . X O
X X . O . O
O . O . X X
O X . X O .
. O O X . X
BoardBaseクラス
この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の盤を表していますが、グレー部分が番兵が置いてある盤の周囲で、水色部分が実際の盤です。
盤面上の数値は、１次元配列のインデックスを表しています。
なお、派生クラスや派生クラスを利用するクラスが、この番兵の存在に依存しないように、ToDirectionという関数を定義し、X方向、Y方向のペアで表す移動方向(ベクトル)をインデックスで表す方向に変換するようにしています。
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で公開したものを大幅に加筆・修正したものです。