はじめに
この記事
で紹介したプログラムのアルゴリズムを説明します。
個人的にはいろんな言語の中で Ruby が一番シンプルだと感じていてるので、Ruby 版のソルバー（solver.rb）を例示しながらアルゴリズムを説明して行きます。
戦略
-
全ての可能性を試す
全てのピースの全ての姿勢の組合せを再帰呼び出しによるバックトラッキングで試して行きます。 -
左上から敷き詰める
左上を起点として、右方向に空きエリアを探します。空きがなければ１列下の左端から右端に向かって空きを探します。空きが見つかればそこに配置します。 -
対称性の排除
6x10 のペントミノは2,339通りの解がありますが、盤面を左右反転や上下反転した場合の解を考慮せずに探索すると4倍の 9,356 通りが見つかります。
そこで、対称な解を排除するために 'F' の配置を制限します。 -
最適化
コードの簡潔さを優先し、最適化は行いません。
最適化の例は別の投稿で示します。
座標の定義
- 盤面の座標
Ｘ軸、Ｙ軸をそれぞれ水平方向、垂直方向とします。6x10 の場合、左上が(0,0)、右下が(5,9)です。
0 1 2 3 4 5 X
+---+---+---+---+---+---+
0 |0,0| | | | | |
+---+---+---+---+---+---+
1 | | | | | | |
+---+---+---+---+---+---+
2 | | | | | | |
～ ～ ～ ～ ～ ～ ～
～ ～ ～ ～ ～ ～ ～
8 | | | | | | |
+---+---+---+---+---+---+
9 | | | | | |5,9|
+---+---+---+---+---+---+
Y
- ピースの座標
ピースの形状と向きにを一意な 座標列（５つの座標 (x,y) の配列）として定義します。
座標の取り方はピースの最も左上を (0,0) とします。なのでＹ座標は必ず 0 以上ですがＸ座標は負値になる場合があります。下図の例では左側ピースの座標列は[(0,0),(1,0),(-1,1),(0,1),(0,2)] 、右側は[(0,0),(0,1),(1,1),(2,1),(1,2)]と定義します。
-1 0 1 X 0 1 2 X
+---+---+ +---+
0 |0,0 | 0 |0,0|
+---+ +---+ + +---+---+
1 | | 1 | |
+---+ + +---+ +---+
2 | | 2 | |
+---+ +---+
Y Y
[(0,0),(1,0),(-1,1),(0,1),(0,2)] [(0,0),(0,1),(1,1),(2,1),(1,2)]
ピース：Piece
ピースは12種類ありその形状から F I L N P T U V W X Y Z という ID を持ちます。
各ピースは 0度／90度／180度／270度回転、表裏反転の組み合わせで最大８通りの座標列が定義できます。ピースの対称性により 'T'、'U'、'V'、’W'、'Z' は４通り、'I' は２通りの座標列が定義できます。 'X' は１通りしかありません。
座標列のデータ
例えば、'F' の８通りの座標列は、以下のような配列で定義できます。
[ [[0, 0], [1, 0], [-1, 1], [0, 1], [0, 2]],
[[0, 0], [-1, 1], [0, 1], [1, 1], [1, 2]],
[[0, 0], [0, 1], [1, 1], [-1, 2], [0, 2]],
[[0, 0], [0, 1], [1, 1], [2, 1], [1, 2]],
[[0, 0], [1, 0], [1, 1], [2, 1], [1, 2]],
[[0, 0], [-1, 1], [0, 1], [1, 1], [-1, 2]],
[[0, 0], [-1, 1], [0, 1], [0, 2], [1, 2]],
[[0, 0], [-2, 1], [-1, 1], [0, 1], [-1, 2]]
]
残りのピースについても丁寧に定義していけば良いのですが面倒です。実際のプログラムではもう少しスマートにピースの絵の文字列から座標列を計算しています。
基になるデータは以下の PIECE_DEF です。
PIECE_DEF = %Q(
+-------+-------+-------+-------+-------+-------+
| | I | L | N | | |
| F F | I | L | N | P P | T T T |
| F F | I | L | N N | P P | T |
| F | I | L L | N | P | T |
| | I | | | | |
+-------+-------+-------+-------+-------+-------+
| | V | W | X | Y | Z Z |
| U U | V | W W | X X X | Y Y | Z |
| U U U | V V V | W W | X | Y | Z Z |
| | | | | Y | |
+-------+-------+-------+-------+-------+-------+
).split("\n").each_with_index.map do |l, y|
l.split('').each_with_index.map { |c, x| [ c, x, y ] }
end.flatten(1).each_with_object( Hash.new([]) ) do |cxy, h|
h[ cxy[0] ] += [ [ cxy[1] / 2, cxy[2] ] ]
end
やっていることは、文字ごとに位置（列と行）を集めて Hash にしているだけです。文字の間に空白を入れてるので、Ｘ座標は横方向の位置を 1/2 する必要があります。結果として以下のような Hash が得られます。
PIECE_DEF = {
"F" => [[2, 3], [3, 3], [1, 4], [2, 4], [2, 5]],
"I" => [[6, 2], [6, 3], [6, 4], [6, 5], [6, 6]],
+、-、| 等の文字に対しても座標列を作ってしまいますが、使わないので良しとします。
initialize: 回転、反転、正規化
ひとつの座標列を基にして、それを回転、反転、正規化することで８通りの座標列を作ります。対称性のあるピースの場合は重複した座標列ができるのでそれを排除します。
class Piece
def initialize( id, fig_def, next_pc )
@figs = Array.new(8) do |r_f| # rotation and flip
fig = fig_def.map do |x,y|
( r_f % 4 ).times{ x, y = -y, x } # rotate
( r_f < 4 )? [x, y] : [-x, y] # flip
end.sort_by do |x,y| # sort
[y, x]
end
fig.map do |x,y| # normalize
[ x - fig[0][0], y - fig[0][1] ]
end
end.uniq # uniq
fig_def を基にして @figs を作ります。 @figs は座標列の配列です。各ピースは固有の @figs を持つことになります。
回転・反転の組み合わせは８通りあるので８回ループを回します。
90度の回転は x, y = -y ,x で計算できるので、180度や270度はこれを２回、３回繰り返します。反転は x, y = -x, y です。反転するのはループ後半の４回です。
座標列を一意に決めるために、まず座標列をソートします。Ｙ座標を優先してソートしたいので x, y を逆にしたものをキーにしてソートしてます。
.sort_by do |x,y| # sort
[y, x]
end
次にピースの座標列の先頭を (0,0) にするために、全ての座標から先頭の座標値を引き算します。
fig.map do |x,y| # normalize
[ x - fig[0][0], y - fig[0][1] ]
end
これで正規化が完了し一意な座標列が得られました。
最後にピースの対称性により重複している座標列を排除するために uniq しています。Ruby の uniq は配列の要素で比較してくれるのですが、言語によっては比較関数を作る必要があります。
盤面：Board
盤面を表すデータは 6x10 や 12x5 の配列で、サイズは60です。配列の要素は言語によって文字列だったり文字コードだったりします。
class Board
def initialize( w, h )
@width = w
@height = h
@cells = Array.new( @height ) { Array.new( @width ) { :SPACE } }
if w * h == 64 # 8x8 or 4x16
@cells[h/2 - 1][w/2 - 1] = '@'; @cells[h/2 - 1][w/2 - 0] = '@'
@cells[h/2 - 0][w/2 - 1] = '@'; @cells[h/2 - 0][w/2 - 0] = '@'
end
end
初期値として空白（を表す定数）を入れておき、ピースを配置する際には対応する要素にそのピースのID（'X' や 'F'）を入れます。
8x8 や 4x16 も設定可能で、その場合は盤面の中央に 2x2 の穴を空けてピースを配置できないようにしています。
表示：render
盤面を１行ずつスキャンしながら上下左右のピース同士の境界をチェックして、盤面全体の文字列を作成します。
# 2
# (-1,-1) | (0,-1)
# ---4--+--1----
# (-1, 0) | (0, 0)
# 8
ELEMS = [
# 0 3 5 6 7 9 10 11 12 13 14 15
" ,,,+---,,----,+ ,+---,,+---,| ,+---,+ ,+---,+ ,+---",
" ,,, ,, , , ,,| ,| ,| ,| ,| ,| ,| "
].map { |s| s.split(',') }.transpose
def render()
Array.new( @height + 1 ) do |y|
Array.new( @width + 1 ) do |x|
ELEMS[ ( ( at( x+0, y+0 ) != at( x+0, y-1 ) )? 1: 0 ) |
( ( at( x+0, y-1 ) != at( x-1, y-1 ) )? 2: 0 ) |
( ( at( x-1, y-1 ) != at( x-1, y+0 ) )? 4: 0 ) |
( ( at( x-1, y+0 ) != at( x+0, y+0 ) )? 8: 0 ) ]
end.transpose.map(&:join)
end.flatten.join( "\n" )
end
ピース同士の接し方を12パターンに分けて、境界線の線素（ELEMS）を選びます。線素は + - | といった文字を組み合わせた文字列です。transpose を使うことでシンプルなコードになっています。
配置可能の確認：check
盤面上の (ox, oy) という位置に fig という座標列が配置可能か調べます。
def check?( ox, oy, fig )
fig.all? { |x,y| at( x + ox, y + oy ) == :SPACE }
end
def at( x, y )
( x >= 0 && x < @width && y >= 0 && y < @height )? @cells[y][x] : '?'
end
盤面からはみ出す可能性があるので、配列にアクセスする前にチェックしています。対応する座標の要素が全て空白ならそこに配置可能と判定します。
配置：place
盤面にピースの id（'F' とか ’L'）を書き込みます。事前にcheck しているので配列からはみ出す心配はありません。
def place( ox, oy, fig, id )
fig.each { |x,y| @cells[ y + oy ][ x + ox ] = id }
end
配置したピースを取り出すには id に 空白を設定して place します。
空白の探索：find_space
盤面をスキャンして空白を探します。
def find_space( x, y )
while @cells[ y ][ x ] != :SPACE
if ( x += 1 ) == @width
x = 0
y += 1
end
end
return [ x, y ]
end
x, y は直前に配置したピースの位置です（十字ピース 'X' を配置した直後は(0,0) ）。Ｘ方向、Ｙ方向に配列を愚直にスキャンして空白が見つかったらその座標を返します。未配置のピースがある限り必ず空白が見つかるので、オーバーランのチェックはしていません。
ソルバー：Solver
以下のようにして Solver を実行します。
solver = Solver.new( width, height )
solver.solve( 0, 0 )
Solver.new で盤面やピースを生成して、solve(0,0) により盤面の左上(0,0)から12個のピース全ての組合せを試しながら敷き詰めていきます。
中身を順番に説明します。
初期処理: initialize
先に説明した Board と Piece を作ります。
class Solver
def initialize( w, h )
@solutions = 0
@board = Board.new( w, h )
pc = nil
'FLINPTUVWXYZ'.reverse.each_char do |id|
pc = Piece.new( id, PIECE_DEF[id], pc )
end
@Unused = Piece.new( '!', [], pc ) # dummy piece
# limit the symmetry of 'F'
pc.figs = pc.figs[ 0, (w == h)? 1 : 2 ]
end
Board の作成は特に説明不要なので Piece について説明します。
PIECE_DEF はピースの座標列を定義した Hash です。これを基にしてピース毎に最大８個の座標列を作ることは先に説明した通りです。
12個のピースは 'F' を先頭として'Z 'までを単方向リストで繋がります。ピースを作りながら繋げるために'Z' から作って最後に'F' を作っています。そして @Unused をピース'F' に繋いでいます。
この @Unused からたどれるピースはまだ盤面に配置されていないピースで、初期状態では全てのピースが未配置です。
ループの回し方は、'ZYXWVUTPNILFX'.each_char としても全く問題ないです。ピースを作る順番がリストの並びと逆なので敢えて 'XFLINPTUVWXYZ'.reverse.each_char としています。
F の座標列を制限
８通りある 'F' の座標列を１通りか２通りに制限することで、対称な解を排除します。6x10 や 5x12 のような長方形の場合は「反転と180度回転なし、90度回転あり」、8x8の正方形の場合は「反転も回転もなし」とします。
# limit the symmetry of 'F'
pc.figs = pc.figs[ 0, (w == h)? 1 : 2 ]
バックトラッキング ：solve
解探索の中心部です。solve() は再帰的に呼び出されます。
def solve( x, y )
if (prev = @Unused).next != nil
x, y = @board.find_space( x, y )
while ( pc = prev.next ) != nil
prev.next = pc.next
pc.figs.each do |fig|
if @board.check?( x, y, fig )
@board.place( x, y, fig, pc.id )
solve( x, y )
@board.place( x, y, fig, :SPACE )
end
end
prev = (prev.next = pc)
end
else
まだピースが全て収まっていない場合、つまり未配置ピースがある場合、 if (prev = @Unused).next != nil は true なので if 文の中で単方向リストをたどって未配置のピースを順番に配置していきます。ピースは回転と反転の組み合わせで複数の座標列を持つので、pc.figs.each で順番に座標列を試しています。
単方向リストのたどり方を図で示しながら説明します。
下図の盤面では７つのピースが配置されていて、＊ の位置に次のピースを配置しようとしています。
+-----------+-----------+
| V | P |
| +-------+ +---+
| | W | | N |
| +---+ +---+---+ |
| | X | | |
+---+ +---+ | +---+
| | | | L |
+---+ +---+---+ | |
| Y | | * | | |
| +---+ +---+ |
| | | |
| +---+ +---+ |
| | | |
| | +-------+
| | |
+---+ |
| |
| |
| |
+-----------------------+
'Y' が配置された後のリストは以下の通りで、この盤面において このリストの順番にピースを選び配置を試みます。（「この盤面において」というのがポイントです）
'F' は試し終わったとして、その次の 'I' を試すときのリストを以下に示します。
リストを操作するために、solve() の中で pc と prev というふたつのローカル変数を使います。 それぞれ配置対称のピースとひとつ手前のピースです。図では pc は 'I' 、prev は 'F' です。ピース自体は単方向リストで繋がっていますが、prev により双方向リストと同じようにノードを操作できます。prev はローカル変数なので盤面毎に存在します。（「盤面毎」というのがポイントです）
この状態で prev.next = pc.next とすると 'I' がリストから外れて下図のようになります。
'I' を配置すると（盤面が更新され）リストはこの状態のまま再帰的に solve() が呼ばれ、その solve() の中で未配置ピースをたどる際には 'I' はスキップされます。
リストを元の状態に戻すには prev.next = pc とします。
さらに配置対称のピースを 'I' から 'T' に進めるため prev = pc とします。実際のコードではリストを元に戻す操作と合わせて while ループの最後で prev = (prev.next = pc) としています。
while ループの先頭に戻ると pc = prev.next が実行され、リストは下図のようになります。
(1) のチャートと比べると prev と pc がひとつ進んでいることが見て取れます。
解の表示
全てのピースが盤上に収まると未配置のピースはなくなり、 @Unused.next は nil です。以下の if 文は else が実行されます。
def solve( x, y )
if (prev = @Unused).next != nil
# ・・・リスト操作と再帰呼び出し ・・・
else
@solutions += 1
curs_up = (@solutions > 1)? ("\033[%dA" % [@board.height * 2 + 2]) : ""
printf( "%s%s%d\n", curs_up, @board.render(), @solutions )
end
ここで、解の数（@solutions）をカウントアップしてから、盤面の状態（@board.render()）と解の数を表示します。大量の解を表示すると画面が流れて見難いので、２回目以降はカーソルを盤面のトップに移動してから表示します。そのためのエスケープシーケンス文字列が "\033[%dA" で、%d には盤面の縦サイズに応じた行数が入ります。
参考