はじめに
（2025/9/2：タイトルを変更しました。内容に変更はありません。）
この記事は ペントミノ・ソルバーのアルゴリズム の続編です。
先の記事よりシンプルなプログラムをベースに説明しているので、アルゴリズムの理解としては本記事を先に見ていただく方が良いです。
プログラム（simple.rb）は全体でも100行程度で、以下の三つで構成されます。
- 初期データの生成
- 盤面の操作、表示
- 解の探索
それぞれが 30～40行程度なので、全体を見渡すことは容易です。
Ruby に慣れている方なら、プログラムを見るだけでやっていることを理解できるでしょう。
解探索の戦略
-
全ての可能性を試す
全てのピースの全ての姿勢の組合せを再帰呼び出しによるバックトラッキングで試して行きます。 -
左上から敷き詰める
左上を起点として、右方向に空きエリアを探します。空きがなければ１列下の左端から右端に向かって空きを探します。空きが見つかればそこに配置します。 -
対称性の排除
6x10 のペントミノは2,339通りの解がありますが、盤面を左右反転や上下反転した場合の解を考慮せずに探索すると4倍の 9,356 通りが見つかります。
そこで、対称な解を排除するために 'F' の配置を制限します。 -
最適化
コードの簡潔さを優先し、最適化は行いません。
座標の定義
- 盤面の座標
Ｘ軸を水平方向、Ｙ軸を垂直方向とする平面上に60個のセルで盤面を構成します。
セルの座標は、6x10 の場合左上が(0,0)、右下が(5,9)です。
0 1 2 3 4 5 X
+---+---+---+---+---+---+
0 |0,0| | | | | |
+---+---+---+---+---+---+
1 | | | | | | |
+---+---+---+---+---+---+
2 | | | | | | |
～ ～ ～ ～ ～ ～ ～
～ ～ ～ ～ ～ ～ ～
8 | | | | | | |
+---+---+---+---+---+---+
9 | | | | | |5,9|
+---+---+---+---+---+---+
Y
- ピース座標
ピースは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' は１通りしかありません。
ピースの形状や置き方を一意な 座標列（５つの座標 (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)]
simple.rb では座標データ(x,y)は「長さが 2 のint型の配列」で扱っています。
ピース毎の座標列
ピース ID 毎の座標列（の配列）を以下のような Hash で定義します。
{ "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]]
],
"I"=>[ [[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]],
[[0, 0], [1, 0], [2, 0], [3, 0], [4, 0]]
],
....
"X"=>[ [[0, 0], [-1, 1], [0, 1], [1, 1], [0, 2]]
],
....
}
このようなデータをハードコードするのは面倒ですし、コードが長くなってしまいます。実際のプログラムでは以下のように ピースのASCII ART から座標列を計算してスマートに Hash を得ています。
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 | |
+-------+-------+-------+-------+-------+-------+
).lines.flat_map.with_index do |line, y|
line.chars.map.with_index do |c, x|
[c, [x/2, y]] # (A)
end
end.each_with_object( Hash.new([]) ) do |(c,xy), h|
h[c] += [ xy ] # (B)
end.transform_values do |points| # (C)
Array.new( 8 ) do |r_f|
points.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.then do |pts| # normalize
pts.map { |x,y| [ x - pts[0][0], y - pts[0][1] ] }
end
end.uniq # uniq
end
(A)： 文字と位置（列と行）のペアの配列を作ります。lines、chars、map.with_index によりシンプルに座標が得られます。 ASCII ART で1セルを2文字で構成するので、横方向の文字位置を 1/2 してＸ座標とします。
(B)： 文字をキー、座標列を値とする Hash にしています。 each_with_object を使うことで配列から Hash の生成が非常にシンプルに書けます。
ここまでの結果として以下のような Hash が得られます。
{
"F" => [[2, 3], [3, 3], [1, 4], [2, 4], [2, 5]],
"I" => [[6, 2], [6, 3], [6, 4], [6, 5], [6, 6]],
この座標列をベースにして (C) 以降で回転、反転、正規化などを行って、最終的にピース ID 毎の「座標列の配列」を得ます。
回転、反転
回転は 0度、90度、180度、270度の4種類あり、反転は 表、裏の2種類あるのでそれらの組合せで8種類です。
end.transform_values do |points| # (C)
Array.new( 8 ) do |r_f|
ID 文字の座標列（points）に対してを回転と反転を行って要素数が8の「座標列の配列」を作っていきます。ブロック変数 r_f の範囲は 0～7 で、その値により90度回転の回数、反転する／しないを決めます。
回転（rotate）
90度回転は x, y = -y ,x で計算できるので、180度や270度はこれを２回、３回繰り返します。回転の回数は r_f % 4 、つまり 0～3 です。
( r_f % 4 ).times { x, y = -y, x } # rotate
左回りか右回りかはどちらでもいいので x, y = y ,-x としても構いません。
反転（flip）
ループ前半（r_f: 0 ～ 3）とループ後半（r_f: 4 ～ 7）で回転の回数（r_f % 4 ）は同じです。ですのでループの前半と後半で反転する／しないを切り替えます。
r_f < 4 の場合は反転せず、r_f >= 4 の場合反転します。反転は x, y = -x, y で計算できます。
( r_f < 4 )? [x, y] : [-x, y] # flip
Ｘ軸周りに反転するかＹ軸周りに反転するかはどちらでもいいので x, y = x, -y としても構いません。
正規化、重複の排除
正規化（normalize）
回転、反転で得られた座標列のままでは左上のセルが (0,0) にはなっていません。
そこでまず、座標列の中の５つの座標値を昇順にソートします。ピースは上から敷き詰めるので、座標の比較は x 座標より y 座標を優先して比較してソートします。
end.sort_by do |x,y| # sort
[y, x]
end
これは以下と同じ結果になります。
end.sort do |a,b| # sort
a[1] == b[1] ? a[0] <=> b[0] : a[1] <=> b[1]
end
次に、先頭の座標が (0,0) になるように５つの座標値から先頭の座標を引き算します。
これで、所望の座標列が得られます。
end.then do |pts| # normalize
pts.map { |x,y| [ x - pts[0][0], y - pts[0][1] ] }
end
重複の排除（uniq）
対称性のあるピースでは規化した結果、重複する座標列が得られます。Ruby の uniq は配列の要素の値で比較してくれるので、単純に uniq を呼び出すだけで重複を排除できます。
Array.new( 8 ) do |r_f|
.... 中略
end.uniq # uniq
'F' の座標列を制限
6x10 のペントミノの解は 2,339通りです。しかし、何もしなければその4倍（9,356通り）の解が見つかります。これは盤面をX軸で反転、Y軸で反転、180度回転（X軸で反転してY軸でも反転）した場合の解も異なる解としてしまうためです。
このような対称な解を排除するために、８通りある 'F' の座標列を０度回転と90度回転の２通りに制限します。
PIECE_DEF['F'].slice!(2 .. -1) # limit the symmetry of 'F'
slice!(2 .. -1) により最初の２つの座標列が残ります。
なお、制限するピースは座標列が8通りあれば F でなくても良いです。
盤面：cells
盤面を保持するために二次元の配列を定義します。
@width, @height = 6, 10
@cells = Array.new( @height ) { Array.new( @width, :SPACE ) }
盤面のサイズは 6x10 です。
配列要素の初期値は空白を表す定数 :SPACE です。ピースが配置されると対応する要素にそのピースのID（'X' や 'F'）が入ります。
盤面の操作
ID の取得: at
def at( x, y )
( x >= 0 && x < @width && y >= 0 && y < @height )? @cells[y][x] : nil
end
x,y として盤面外の値が入る場合があるので、その場合は nil を返します。
配置可能の確認：check?
def check?( x, y, fig )
fig.all? { |u,v| at( x + u, y + v ) == :SPACE }
end
盤面上の (x, y) という位置に fig という座標列が配置可能か調べます。
盤面からはみ出す可能性があるので、at() を使ってチェックしています。対応する座標の要素が全て :SPACE ならそこに配置可能と判定します。
配置：place
def place( x, y, fig, id )
fig.each { |u,v| @cells[y + v][x + u] = id }
end
盤面にピースの ID（'F' とか ’L'）を書き込みます。事前に check? しているので盤面からはみ出すことはありません。
配置したピースを取り出すには :SPACE を id に設定します。
place( x, y, fig, :SPACE ) # unplace
空白の探索：find_space
def find_space( x, y )
while @cells[y][x] != :SPACE
x += 1
x, y = [0, y + 1] if x == @width
end
[ x, y ]
end
引数の x, y を起点にＸ方向、Ｙ方向に cells を愚直にスキャンして空白が見つかったらその座標を返します。未配置のピースがある限り必ず空白が見つかるので、オーバーランのチェックはしていません。
解の探索
バックトラッキングにより探索を進めます。
一つのピースを配置する度に呼び出されるのが solve で、再帰的に呼び出されます。
def solve( x, y, pieces )
x, y はピースを配置可能な左上の空白を探すための初期座標、pieces は 未だ配置されていないピース ID の配列です。配置が進む度に未配置のピースが減って行きます。
探索の開始
最初の呼び出しでは全ピースが未配置で、 (0,0) から配置していくので以下のようになります。
solve( 0, 0, %w( F I L N P T U V W X Y Z) )
探索中の状態
探索途中の盤面と piece の状態を示しておきます。
下図の盤面では 'Y' が配置された結果７つのピースが配置されていています。
+-----------+-----------+
| V | P |
| +-------+ +---+
| | W | | N |
| +---+ +---+---+ |
| | X | | |
+---+ +---+ | +---+
| | | | L |
+---+ +---+---+ | |
| Y | | * | | |
| +---+ +---+ |
| | | |
| +---+ +---+ |
| | | |
| | +-------+
| | |
+---+ |
| |
| |
| |
+-----------------------+
'Y' が配置された後の piece は以下の通りです。
[ "F", "I", "T", "U", "Z" ] # pieces
この後＊ の位置に残りのピースを配置していくことになります。
solve には以下の引数が渡されることになります。
solve( 0, 4, [ "F", "I", "T", "U", "Z" ] )
(0,4) は 直近に配置した 'Y' の座標です。
バックトラッキングによる探索：solve
def solve( x, y, pieces )
if pieces.size > 0
x, y = find_space( x, y )
pieces.each_with_index do |id,i|
rest = pieces.clone.tap { |r| r.delete_at(i) }
PIECE_DEF[ id ].each do |fig|
if check?( x, y, fig ) # check
place( x, y, fig, id ) # place
solve( x, y, rest ) # call recursively
place( x, y, fig, :SPACE ) # unplace
end
end
end
else
@solutions += 1
printf( "%s%s%d\n",
(@solutions > 1)? ("\033[%dA" % [@height * 2 + 2]) : "",
render(),
@solutions )
end
引数の x, y は一番左上の空白を探すための開始位置、pieces は 未だ配置されていないピース ID の配列です。
まだ解が見つかっていなければ未配置ピースがあり if pieces.size > 0 は true です。その場合、未配置のピースから一つを選んで配置して盤面を更新し、solve を再帰的に呼び出します。
12個のピースを配置するということは、solve() を12回 ネストして呼び出しすることになり、１つのピースを配置した盤面の状態は、solve() のコンテキストとして保持されます。
solve() の中で、pieces から i 番目の要素を取り出した残りの配列を作る必要があります。Ruby の delete_at() は破壊的なので pieces.delete_at(i) とするのはマズいです。また、delete_at() は取り出し要素を返すので以下のように書く必要があります。
rest = pieces.clone
rest.delete_at(i)
実際のコードでは少し工夫して同じことを1行で書いています。
rest = pieces.clone.tap { |org| org.delete_at(i) }
解の表示
全てのピースが盤上に収まると未配置のピースはなくなり、 pieces.size は 0 です。以下の if 文は else が実行されます。
if pieces.size > 0
# 中略
else
@solutions += 1
printf( "%s%s%d\n",
(@solutions > 1)? ("\033[%dA" % [@height * 2 + 2]) : "",
render(),
@solutions )
end
ここで、解の数（@solutions）をカウントアップしてから、盤面の状態（render()）と解の数を表示します。大量の解を表示すると画面が流れて見難いので、２個目以降はカーソルを盤面のトップに移動してから表示します。そのためのエスケープシーケンス文字列が "\033[%dA" で、%d には盤面の縦サイズに応じた行数が入ります。
盤面の表示：render
いろいろ試行錯誤した結果、見やすい盤面表示をシンプルなコードで実現しています。
# 2
# (-1,-1) | (0,-1)
# ---4--+--1----
# (-1, 0) | (0, 0)
# 8
ELEMS = [ # (A)
# 0 3 5 6 7 9 10 11 12 13 14 15
" ,,,+---,,----,+ ,+---,,+---,| ,+---,+ ,+---,+ ,+---",
" ,,, ,, , , ,,| ,| ,| ,| ,| ,| ,| "
].map { |s| s.split(',') }
def render()
Array.new( @height + 1 ) do |y|
Array.new( @width + 1 ) do |x|
ids = [ [0,0], [0,1], [1,1], [1,0] ].map { |u,v| at( x-u, y-v ) } # (B)
( ( ids[0] != ids[1] ? 1 : 0 ) +
( ids[1] != ids[2] ? 2 : 0 ) +
( ids[2] != ids[3] ? 4 : 0 ) +
( ids[3] != ids[0] ? 8 : 0 ) ) # (C)
end.then do |codes|
[ codes.map{ |c| ELEMS[0][c] }.join, # (D)
codes.map{ |c| ELEMS[1][c] }.join ]
end
end.join( "\n" )
end
盤面を１行ずつスキャンしながら上下左右のピース同士の境界をチェックして、盤面全体の文字列を作成します。
(A)： ひとつの cell に対する境界線の描き方を 16パターンに分けて、境界線の線素（ELEMS）を定義しておきます。
ある cell に着目したとき、その cell／上／左上／左 の4つの cell の中で隣り合う cell の ID が同じかどうかを比較すれば、境界線のパターンが決まります。４ヶ所の比較なので、それぞれに 1, 2, 4, 8 の４つの値を割り当て、その組み合わせで 0～15 の値を得ます。
線素は + - | といった文字を組み合わせた文字列で、ひとつの境界線は4文字、縦2行で表現します。
(B)： 着目している座標 (x,y) と、その上、左上、左の4ヶ所の ID を取り出します。その際、at() の呼び出しで ( -1, -1 ) や ( 6, 10 ) といった配列サイズを超える座標値をとる場合があります。そのため at() では座標値のチェックが必要になります。
(C)： 隣り合う座標で ID を比較し、４ヶ所の比較結果から 0～15 の値を計算します。これが線素のパターン値です。
(D)： 線素のパターン値に従って選んだ線素をテキスト1行分ずつ連結します。
以下はある盤面で、線素のパターン値 0～15 を HEX表記して重ねた例です。パターン値と線素の関係が見て取れると思います。
+---+---+-----------+---+---+-----------+ +---+---+-----------+---+---+-----------+
| | | | | | | | 9 | D | D 5 5 | D | D | D 5 5 | C
| | | +---+ | | +-------+ | | | | +---+ | | +-------+ |
| | | | | | | | | | A | A | A | 9 | C | A | A 3 5 | C | A
| | +---+ +---+ +---+---+ | | | | +---+ +---+ +---+---+ | |
| | | | | | | | | A | A | B 6 | B 6 3 | D | C | A | A
| | +---+ +---+---+---+ +---+---+ | | +---+ +---+---+---+ +---+---+
| | | | | | | | A | A 3 | C 3 | D | D 6 3 | F | E
| +-------+---+---+ +---+ +---+ | | +-------+---+---+ +---+ +---+ |
| | | | | | | | A | B 5 7 | D | E 3 | C | 9 6 | A
+---+ +-------+ +---+ +---+ | +---+ +-------+ +---+ +---+ |
| | | | | | B 6 | 9 5 6 3 | C 3 | E 0 | A
+-------+---------------+-------+-------+ +-------+---------------+-------+-------+
3 5 7 5 5 5 7 5 7 5 6
おわりに
ペントミノ・ソルバーのアルゴリズムを紹介しました。
プログラムの初歩の勉強題材として工夫のしどころがいろいろあって面白いのではないかと思います。
変更履歴
- 2025/9/2：タイトルを「ペントミノ・ソルバーのアルゴリズム（簡素編）」から「ペントミノ・ソルバー（簡素版）のアルゴリズム」に変更。
参考