問題
縦6×横6の升目の中に、10円玉6個、5円玉6個を入れてください。
そのとき、縦6列、横6列、対角線2列の合計14列の、どこも合計が15円になるようにしてください。
解の一つを以下に示します。
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| |10| | | |
|--|--|--|--|--|--|
| | | |10| | 5|
|--|--|--|--|--|--|
| | | 5| |10| |
|--|--|--|--|--|--|
| | | | | 5|10|
|--|--|--|--|--|--|
| |10| | 5| | |
|--|--|--|--|--|--|
オリジナルの問題(出典不明)は、100円玉と50円玉を使うパズルだったのですが、画面に表示する関係で、10円玉と5円玉に変更しています。
どうやって解くか
今回解いたプログラムでは、まずは、最上位の横の列（1行目）に、10円玉と5円玉を置き、次に2行目、次に3行目、...6行目と順にコインを置いてゆくという方法をとっています。
もちろん、途中で条件を満たさなく成ったら、試行をやめて、次の場所にコインを置きます。
これを再帰処理で求めています。
2次元配列を用意して、ゴリゴリ組んでいっても良いのですが、ここでは、盤面クラス(Boardクラス)にパズルを解くのに必要な盤面を操作する機能を定義しています。
パズルを解くSolverクラスでは、このBoardクラスを操作して解を求めています。
C#のコード
Coinクラス / Boardクラス
Coinクラスは、その名の通り盤面に置くことのできるコインを表しています。
implicit operator intでintへの型変換は暗黙の型変換ができるようにしています。
Boardクラスはこのパズル専用のクラスで、後述のBoardBaseクラスを継承しています。
盤面の状態をコンソール画面に表示する機能は、このクラスに実装しています。まあ、これはProgramクラスに実装してもよかったかもしれません。そうすれば、コンソールアプリに依存するのは、Programクラスだけにすることができます。
using System;
using System.Collections.Generic;
using System.Linq;
using Puzzle;
namespace Coin15App {
// 盤面に置くコインクラス
public class Coin {
public int Number { get; set; }
public static readonly Coin C10 = new Coin { Number = 10 };
public static readonly Coin C5 = new Coin { Number = 5 };
public static readonly Coin Zero = new Coin { Number = 0 };
public static implicit operator int(Coin coin) {
return coin.Number;
}
}
public class Board : BoardBase<Coin> {
public Board(int size) : base(size, size) {
}
public Board(Board board) : base(board) {
}
// 縦、横、対角線のすべてのLineを所得する
public IEnumerable<int[]> GetAllLines() {
for (int y = 1; y <= this.YSize; y++) {
yield return Horizontal(1, y).ToArray();
}
for (int x = 1; x <= this.YSize; x++) {
yield return Virtical(x, 1).ToArray();
}
yield return SlantR(1, 1).ToArray();
yield return SlantL(XSize, 1).ToArray();
}
// coin を置けるか
internal bool CanPut(int index, int coin) {
if (this[index].Number > 0)
return false;
foreach (var line in GetLines(index).ToArray()) {
var coins = line.Where(n => this[n].Number > 0).Select(n => this[n]).ToList();
int count = coins.Count;
if (count > 1)
return false;
int sum = coins.Sum(x => x.Number);
if (sum + coin > 15)
return false;
}
return true;
}
// position を通る、縦、横、対角線のLineを列挙する （対角線は通らない場合もある）
public IEnumerable<IEnumerable<int>> GetLines(int position) {
var (x, y) = ToLocation(position);
yield return Horizontal(1, y);
yield return Virtical(x, 1);
if (x == y)
yield return SlantR(1, 1);
else if (x + y == XSize + 1)
yield return SlantL(XSize, 1);
}
// 終了か （条件を満たしているか）
public bool IsFin() {
foreach (var line in GetAllLines()) {
if (line.Sum(x => this[x].Number) != 15)
return false;
}
return true;
}
// 盤の状態をプリント
public void Print() {
Console.WriteLine("|--|--|--|--|--|--|");
for (int y = 1; y <= YSize; y++) {
Console.Write("|");
for (int x = 1; x <= XSize; x++) {
int p = this[x, y].Number;
Console.Write("{0}|", p == 0 ? " " : p == 10 ? "10" : " 5");
}
Console.WriteLine("\n|--|--|--|--|--|--|");
}
Console.WriteLine();
}
}
}
Solverクラス
Solverクラスは、このパズルを解くクラスです。Boardクラスに定義したメソッドを使いながら、探索をおこない解を求めています。
まず、1行目に10円と5円を置き、次に（再帰呼び出しして）2行目に10円と5円を条件に合うように置き、次に... と最後の行まで再帰処理すれば答えが見つかります。
鏡像は、ほんの一部分だけを省いています。一部だけというのは、簡単に鏡像や回転を除くロジックが思いつかなかったというお恥ずかしい理由からです。
僕が考え付くのは、解いた答えを覚えておいて、新たな答えが鏡像か回転に当てはまるかをいちいち調べるという誰でも思いつく力技。でも面倒なので実装していません。これ以外に良いやり方ってないのかなー。
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;
namespace Coin15App {
public class Solver {
private Board board;
public Solver() {
this.board = new Board(6);
}
public IEnumerable<Board> Solve() {
foreach (var b in _Solve(1))
yield return b;
}
public IEnumerable<Board> _Solve(int y) {
if (y > board.YSize && board.IsFin()) {
yield return new Board(board);
yield break;
}
// yで示す横一列のインデックスの一覧を得る。
// 鏡像の一部を除く (すべてを取り除くには別の手法が必要？）
var places = y == 1
? board.Horizontal(1, y).Take(board.XSize / 2).ToArray()
: board.Horizontal(1, y).ToArray();
foreach (var i in places) {
// 10を試行
if (board.CanPut(i, Coin.C10)) {
board[i] = Coin.C10;
// 10を試行
foreach (var j in board.Horizontal(1, y)) {
if (board.CanPut(j, Coin.C5)) {
board[j] = Coin.C5;
foreach (var b in _Solve(y + 1))
yield return b;
board[j] = Coin.Zero;
}
}
board[i] = Coin.Zero;
}
}
}
}
}
Programクラス
プログラムを制御するProgramクラスは、Solverクラスで解を求め、その解を表示するだけのとても単純なクラスです。
using System;
using System.Collections.Generic;
using System.Linq;
namespace Coin15App {
class Program {
static void Main(string[] args) {
var solver = new Solver();
foreach (var x in solver.Solve()) {
x.Print();
}
}
}
}
BoardBaseクラス
このBoardBaseクラスは、「C#でパズルを解く - 碁石拾い」で利用したものと同じものです。
前述の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);
}
}
結果
想像以上に解の数が多かったですね。
答えの数が多いので、先頭の5個と最後の5個だけを掲載します。
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| |10| | | |
|--|--|--|--|--|--|
| | | |10| 5| |
|--|--|--|--|--|--|
| |10| 5| | | |
|--|--|--|--|--|--|
| | | | 5| |10|
|--|--|--|--|--|--|
| | | | |10| 5|
|--|--|--|--|--|--|
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| |10| | | |
|--|--|--|--|--|--|
| | | |10| 5| |
|--|--|--|--|--|--|
| | | 5| |10| |
|--|--|--|--|--|--|
| | | | 5| |10|
|--|--|--|--|--|--|
| |10| | | | 5|
|--|--|--|--|--|--|
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| |10| | | |
|--|--|--|--|--|--|
| | | |10| | 5|
|--|--|--|--|--|--|
| |10| 5| | | |
|--|--|--|--|--|--|
| | | | | 5|10|
|--|--|--|--|--|--|
| | | | 5|10| |
|--|--|--|--|--|--|
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| |10| | | |
|--|--|--|--|--|--|
| | | |10| | 5|
|--|--|--|--|--|--|
| | | 5| |10| |
|--|--|--|--|--|--|
| | | | | 5|10|
|--|--|--|--|--|--|
| |10| | 5| | |
|--|--|--|--|--|--|
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| |10| | | |
|--|--|--|--|--|--|
| | | | 5|10| |
|--|--|--|--|--|--|
| | | | | 5|10|
|--|--|--|--|--|--|
| |10| 5| | | |
|--|--|--|--|--|--|
| | | |10| | 5|
|--|--|--|--|--|--|
...
|--|--|--|--|--|--|
| | |10| | | 5|
|--|--|--|--|--|--|
| | | 5| | |10|
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| | |10| | |
|--|--|--|--|--|--|
| |10| | | 5| |
|--|--|--|--|--|--|
| | | | 5|10| |
|--|--|--|--|--|--|
|--|--|--|--|--|--|
| | |10| | | 5|
|--|--|--|--|--|--|
| | | 5| | |10|
|--|--|--|--|--|--|
| | 5| |10| | |
|--|--|--|--|--|--|
|10| | | 5| | |
|--|--|--|--|--|--|
| 5| | | |10| |
|--|--|--|--|--|--|
| |10| | | 5| |
|--|--|--|--|--|--|
|--|--|--|--|--|--|
| | |10| | | 5|
|--|--|--|--|--|--|
| | | | 5| |10|
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| | |10| | |
|--|--|--|--|--|--|
| |10| | | 5| |
|--|--|--|--|--|--|
| | | 5| |10| |
|--|--|--|--|--|--|
|--|--|--|--|--|--|
| | |10| | | 5|
|--|--|--|--|--|--|
| | | | 5| |10|
|--|--|--|--|--|--|
|10| | 5| | | |
|--|--|--|--|--|--|
| | | |10| 5| |
|--|--|--|--|--|--|
| 5|10| | | | |
|--|--|--|--|--|--|
| | 5| | |10| |
|--|--|--|--|--|--|
|--|--|--|--|--|--|
| | |10| | | 5|
|--|--|--|--|--|--|
| | | | 5| |10|
|--|--|--|--|--|--|
| | | 5|10| | |
|--|--|--|--|--|--|
|10| 5| | | | |
|--|--|--|--|--|--|
| 5| | | |10| |
|--|--|--|--|--|--|
| |10| | | 5| |
|--|--|--|--|--|--|
この記事は、Gushwell's C# Programming Pageで公開したものを大幅に加筆・修正したものです。