今回は「裏表パズル」を解いてみましょう。裏表パズルはルービック・キューブを平面にしたようなパズルです。たとえば、表を白、裏を黒に塗り、任意の行 (または列) を裏返しにして模様を完成させる、または、同じ色に揃えるのがパズルの目的です。次の図を見てください。
表 裏 表 裏 表 裏
１２３ １２３ １２３ １２３ １２３ １２３
Ａ□□□ ■■■ Ａ□□□ ■■■ Ａ□□□ ■■■
Ｂ□□□ ■■■ = C 行 => Ｂ□□□ ■■■ = 2 列 => Ｂ□■□ ■□■
Ｃ□□□ ■■■ Ｃ■■■ □□□ Ｃ■■■ □□□
図 : 裏表パズルの動作
上図の C 行を 2 列を中心に回転して裏返しにします。すると、C 行は黒になりますが、このとき (C, 3) の裏が (C, 1) の表に、(C, 1) の裏が (C, 3) の表になることに注意してください。次に、2 列を B 行を中心に回転させると、(A, 2) の裏が (C, 2) の表になるので黒のまま、(C, 2) の裏が (A, 2) の表になるので白のままで、(B, 2) が裏返しになるので (B, 2) が黒になります。
このように、行（または列）を回転させて裏返しにするところが裏表パズルの面白いところです。裏表パズルの詳しい説明は、高木茂男氏の著書「パズル遊びへの招待 オンライン版」の「裏表パズル」をお読みください。
それでは問題です。
■□■ □□□ □■■ ==> □□□ ■■■ □□□ START GOAL 問題 : 裏表パズル
3 行 3 列盤の裏表パズルで、表をすべて白にする最短手順を求めてください。
今回は単純な幅優先探索でプログラムを作ります。使用するプログラミング言語は Python3 (ver 3.8.10) です。最初に大域変数を定義します。
┌─┬─┬─┐ │０│１│２│ ├─┼─┼─┤ │３│４│５│ ├─┼─┼─┤ │６│７│８│ └─┴─┴─┘ 図 : 盤面の番号
リスト : 大域変数の定義
# 定数
B = 0
W = 1
# ライン
line3 = [
[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8]
]
白と黒は B (0) と W (1) で表すことにします。盤面は一次元配列 (Python のタプル) で表します。盤面の位置と配列の添字の対応を上図のように定義すると、3 * 3 盤のライン (行, 列) はリスト line3 で表すことができます。
ラインの裏返しは簡単です。次のリストを見てください。
リスト : ラインを裏返す
def reverse_line(b, n, ls):
l = ls[n]
i, j = 0, len(l) - 1
a = list(b)
while i <= j:
x = l[i]
y = l[j]
a[x], a[y] = a[y] ^ 1, a[x] ^ 1
i += 1
j -= 1
return tuple(a)
関数 reverse_line() の引数 b が盤面をタプル、n が反転するラインの番号、ls がラインを表すリストです。3 * 3 盤だけではなく、他の大きさの盤面にも対応できるように、汎用的にプログラムしています。白と黒を反転させるには、盤面の値と 1 の排他的論理和 (XOR) を計算すれば簡単にできます。
たとえば、反転するラインが [0, 1, 2] とすると、b[0] は b[2] の裏の値に、b[1] は b[1] の裏の値に、b[2] は b[0] の裏の値になります。つまり、ラインの先頭と末尾から順番に 1 と XOR を計算して、それを交換すればいいわけです。b はタプルなので、値を書き換えることができません。list(b) でリストに変換して変数 a にセットします。
変数 l に反転するライン ls[n] をセットします。変数 i と j は l の先頭と末尾の位置に初期化します。あとは while ループで i と j が交差するまで、盤面の値 a[l[i]] と a[l[j]] と 1 の XOR を計算し、その値を交換します。最後に return で a をタプルに変換して返します。
次は深さ優先探索で解を求める関数 bfs() を作ります。次のリストを見てください。
リスト : 幅優先探索による解法
def bfs(start, goal, ls, w, h):
queue = [(start, -1)]
check = {}
check[start] = True
rc = 0
size = h * w
while rc < len(queue):
b, _ = queue[rc]
if b == goal:
print_moves(rc, queue, w, h)
return
for i in range(len(ls)):
a = reverse_line(b, i, ls)
if a in check: continue
queue.append((a, rc))
check[a] = True
rc += 1
bfs() の引数 start, goal はスタートとゴールの盤面、ls がラインを格納したリスト、w, h が盤面 (w * h 盤) の大きさを表す値です。リスト queue をキューとして使います。要素はタプル (盤面, 1 手前の盤面の添字) です。変数 rc をキューのリードカウントして使います。check は同一局面のチェックで使用する Python の辞書です。3 * 3 盤は線形探索で十分ですが、大きな盤面でも試してみたいので辞書を使っています。
while ループでキューにデータがある間は探索を続けます。queue からデータを取り出して、盤面を変数 b にセットします。b が goal に等しい場合、解を見つけたので関数 print_moves() で手順を表示し、return で探索を終了します。そうでなければ、reverse_line() で番号 i のラインを反転し、その盤面を変数 a にセットします。a が check になければ、新しい盤面です。queue に (a, rc) を追加し、check[a] に True をセットして探索を続けます。
あとはとくに難しいところはありません。詳細はプログラムリストをお読みくださいませ。
それでは実行結果を示します。
>>> bfs((B,W,B,W,B,B,B,B,B), (W,W,W,W,W,W,W,W,W), line3, 3, 3) B W B W B B B B B W B W W B B B B B W B W W W B B B B W B W B W B B B B B W B B W B B B B W W B W W B W B B W W B W W B W W B W W W W W W W W W
↓ ↓ ↓
→■□■ □■□ □■□ →□■□ ■□■ □□■ □□■ □□□
□■■ →□■■ □□■ ■□■ ■□■ □□■ □□■ □□□
■■■ ■■■ ■■■ ■■■ ■■■ →□■■ □□■ □□□
０ １ ２ ３ ４ ５ ６ ７
図 : 裏表パズルの解答
最短手数は 7 手で、これが表を白に揃える最長手数になります。
裏表パズルには偶奇性があります。2 行 2 列盤の裏表パズルを例に考えてみましょう。次の図を見てください。
|
□□ ■■ □□ ■□ □■ ■■ | ■□ □■
□□ □□ ■■ ■□ □■ ■■ | □■ ■□
Ａ Ｂ Ｃ Ｄ Ｅ Ｆ | Ｇ Ｈ
図 : 裏表パズルの偶奇性
ここでは、表にある黒の個数を数えることにします。A の場合、黒の個数は 0 です。ここで白と白の列を裏返しにすると黒と黒になります。この場合、B - E の 4 通りありますが、どれも黒の個数は 2 になります。B - E の状態で、白と白の列を裏返しにすると、表がすべて黒の状態 F になるので、黒の個数は 4 になります。また、B - E で黒と黒の列を裏返しにすると、A の状態に戻るのは自明ですね。
それでは、白と黒の列を裏返しにしてみましょう。B の状態で、白と黒を裏返しにすると、黒の裏（白）が下側の表になり、白の裏（黒）が上側の表になるので、B の状態に変化はありません。これはどの状態の場合でも同じで、白と黒の列を裏返しにしても、状態に変化はありません。したがって、黒の個数は 2 のままです。このように、裏表パズルはどの列を裏返しにしても黒の偶奇性に変化はありません。したがって、黒の個数が奇数の場合、表を白一色にすることはできないのです。
ここで、もうひとつ注意点があります。偶奇性を満たしていても解けない場合があるのです。上図の G と H を見てください。白と黒が交互に配置されていますね。この状態では、どの列を裏返しにしても元のままです。つまり、裏表パズルには変化しないパターンがあるのです。もちろん、この場合も表を白一色にすることはできません。けっきょく、白一色にできるパターンは、それ自身も含めて 6 通りしかありません。盤面を大きくしても、白一色にできるパターンはかなり少ないと思われます。
それでは、3 行 3 列盤を考えてみましょう。下図に示すように、盤面をグループに分けると簡単です。
┌─┬─┬─┐
│０│１│０│ Group 0 には偶奇性が成立する
├─┼─┼─┤
│１│１│１│ Group 1 には偶奇性が成立しない
├─┼─┼─┤
│０│１│０│ 局面の総数 : (2 ^ 5) * 6 = 192 通り
└─┴─┴─┘
図 : 3 行 3 列盤のグループ分け
Group 0 の 4 か所は、2 行 2 列盤と同じ偶奇性が成立することはすぐにわかると思います。したがって、白一色になるパターンは Group 0 では 6 通りしかありません。つまり、Group 0 で黒の個数が奇数、または、白と黒が交互に配置されている状態では、3 行 3 列盤でも白一色にすることはできません。
Group 1 は単独で裏返しにできる場所です。たとえば、両端が黒と白の場合、裏返しにしても両端の状態は変わらないので、真ん中の部分だけを裏返しにすることができます。したがって、Group 1 に偶奇性は成立しません。つまり、Group 0 の状態だけで、解の有無をチェックすることができるわけです。局面の総数は 2 ^ 5 (2 の 5 乗) * 6 = 192 通りになります。
次は 4 行 4 列盤を考えてみましょう。下図を見てください。
┌─┬─┬─┬─┐
│０│１│１│０│
├─┼─┼─┼─┤
│２│３│３│２│ どの Group にも偶奇性が成立
├─┼─┼─┼─┤
│２│３│３│２│ 局面の総数 : 6 ^ 4 = 1296 通り
├─┼─┼─┼─┤
│０│１│１│０│
└─┴─┴─┴─┘
図 : 4 行 4 列盤のグループ分け
3 行 3 列盤と違って、どの Group にも 2 行 2 列盤と同じ偶奇性が成立します。したがって、白一色にできる局面の総数は 6 ^ 4 = 1296 通りになります。これ以外の盤面も次のようにグループ分けすることができます。
[3 行 4 列盤] 0 1 1 0 Group 0, 1 : 偶奇性が成立 2 2 2 2 Group 2 : 不成立 0 1 1 0 総数 : (6 ^ 2) * (2 ^ 4) = 576 [4 行 5 列盤] 0 1 2 1 0 Group 0,1,3,4 : 偶奇性が成立 3 4 2 4 3 Group 2 : 不成立 3 4 2 4 3 総数 : (6 ^ 4) * (2 ^ 4) = 20,736 0 1 2 1 0 [5 行 5 列盤] 0 1 2 1 0 Group 0,1,3,4 : 偶奇性が成立 3 4 2 4 3 Group 2 : 不成立 2 2 2 2 2 総数 : (6 ^ 4) * (2 ^ 9) = 663,552 3 4 2 4 3 0 1 2 1 0
5 行 5 列盤になると、偶奇性が成立する Group が 4 つ、その他の場所が 9 つあるので、局面の総数は (6 ^ 4) * (2 ^ 9) = 663,552 通りになります。5 行 5 列盤の局面は全部で 2 ^ 25 = 33,554,432 通りあるので、白一色にできるパターンは約 2 % しかありません。このように、裏表パズルで白一色にできるパターンはかなり少ないことがわかります。
また、2 行 2 列盤には変化しないパターンがありますが、4 行 4 列盤でもすべての Group が変化しないパターンであれば、どの列を裏返しにしても状態は変化しません。たとえば下図に示すように、盤面を白と黒の市松模様にすると、どの列を裏返しにしても市松模様のままです。これは裏表パズルの面白い特徴だと思います。
■■□□ ■□■□ ■■□□ ■■□□ ■□■□ ■□■□
■■□□ ■■□□ ■□■□ □□■■ □■□■ □□■■
□□■■ □□■■ □■□■ ■■□□ ■□■□ ■■□□
□□■■ □■□■ □□■■ □□■■ □■□■ □■□■
図 : 変化しないパターンの例 (4 * 4 盤)
ところで、3 行 3 列盤や 5 行 5 列盤の市松模様は簡単に解けます。息抜きや気分転換にちょっと考えてみてください。
次は裏表パズルの最長手数の局面を「幅優先探索」で求めてみましょう。プログラムは次のようになります。
リスト : 最長手数の局面を求める
def solver_max(ls, w, h):
start = (W,) * (w * h)
xs = [start]
check = {}
check[start] = True
move = 0
while True:
ys = []
for b in xs:
for i in range(len(ls)):
a = reverse_line(b, i, ls)
if a in check: continue
ys.append(a)
check[a] = True
if not ys: break
xs = ys
move += 1
print("最長手数 =", move, "個数 =", len(xs))
for b in xs[:4]: print_board(b, w, h)
print("状態の総数 =", len(check))
リスト xs は move 手で生成した盤面を格納します。リスト check は同一局面のチェックに使用します。表がすべて白の盤面を生成して xs と check に追加します。あとは while ループで move + 1 手の盤面を生成します。
リスト ys に move + 1 手の盤面を格納します。for ループで xs から盤面を一つずつ取り出し、reverse_line() で新しい盤面 a を生成します。同一局面がなければ、ys と check に a を追加します。for ループを終了したら、ys にデータがあるかチェックします。ys が空リストならば xs が最長手数の盤面になります。break で while ループを脱出して、最長手数と個数、盤面、状態の総数を出力します。盤面は先頭の 4 個だけ表示します。そうでなければ、xs を ys にセットし、move を +1 して探索を続けます。
あとのプログラムは簡単なので説明は割愛させていただきます。詳細はプログラムリストをお読みください。
それでは実際に試してみましょう。
>>> solver_max(line3, 3, 3) 最長手数 = 7 個数 = 8 W B W W B B W W W B B B B B W B W B W W W W B B W B W B W B B B W B B B 状態の総数 = 192
3 行 3 列盤の最長手数は 7 手、全部で 8 通りのパターンがあります。対称解を除くと次の 2 通りになります。
□■□ ■□■ ■■□ □■■ □□□ ■■■ 図 : 最長手数の局面
生成された局面は全部で 192 通りで、偶奇性で計算した結果と一致します。
次は 4 行 4 列盤の結果を示します。
>>> solver_max(line4, 4, 4) 最長手数 = 6 個数 = 224 B W W B W B B W W W W W B B B B W W W W B B B B B W W B W B B W B W W B W W W W W B B W B B B B W W W W B W W B B B B B W B B W 状態の総数 = 1296
□□□□ □□□□ □■■□ ■□□■
□■□■ □□■■ ■■□□ □□□■
□■□■ □□■■ ■■□□ □■■■
□■■□ ■□□■ ■■■■ ■■■■
図 : 最長手数の局面の例 (4 * 4 盤)
最長手数は 6 手、全部で 224 通りのパターンがあります。生成された局面は全部で 1296 通り、これも偶奇性で計算した結果と一致します。bfs() での実行結果は次のようになります。
>>> bfs((W,W,W,W,W,B,W,B,W,B,W,B,W,B,B,W),(W,) * 16, line4, 4, 4) W W W W W B W B W B W B W B B W B W W W B B W B B B W B B B B W B W W W B B B B B B B B B B B W B W W W W W W W B B B B B B B W B W W W W W W W B B B B B W W W W W W W W W W W B B B B W W W W W W W W W W W W W W W W W W W W
ご参考までに 3 行 4 列盤と 4 行 5 列盤の結果を示します。
>>> solver_max(line43, 4, 3) 最長手数 = 6 個数 = 104 B B B W B B B B B W W W B W W W B B B B B B B W W B B B W B B W W W W B W W W B W B B W W B B B 状態の総数 = 576 >>> solver_max(line54, 5, 4) 最長手数 = 10 個数 = 32 B W B W B B B W B B W W W W W W B B B W B W B W B W W B W W B B B B B W B B B W W B W B W B B W B B W W W W W B W W W B W B W B W W W B W W B B B B B B W W W B 状態の総数 = 20736
生成した状態の総数は、どちらの盤面でも偶奇性で計算した結果と一致します。
最後に 5 行 5 列盤の実行結果を示します。
>>> import time >>> s = time.time(); solver_max(line5, 5, 5,); time.time() - s 最長手数 = 13 個数 = 4608 W B B B W B W B W B W W B B B W W W W W W W W W W W B B B W B B B B B W B B W B W B W B W W W W W W W B B B W W W W W W W W B B B B W B W B W W W W W W B B B W W B W B W W B B W B B B B B B W W W W W 状態の総数 = 663552 12.516299486160278 実行環境 : Python 3.8.10, Ubuntu 20.04 LTS (WSL1), Intel Core i5-6200U 2.30GHz
5 行 5 列盤の最長手数は 13 手、全部で 4608 通りのパターンがあります。生成された局面は全部で 663,552 通り、これは偶奇性で計算した結果と一致します。最長手数の局面の例を図に示します。黒の個数が一番少ないパターンからいくつか選んでみました。
□□■□□ □□■□□ □□■□□
□□■□□ □□□□□ □□■□□
■□■■□ ■□■■□ ■■■□□
□□□□□ □□■□□ □□□□□
□□□□□ □□□□□ □□□□□
図 : 最長手数の局面の例 (5 * 5 盤)
実行時間は Python3 で約 13 秒かかりました。PyPy3 を使うと約 8.4 秒になりました。
ご参考までに bfs() の実行結果を示します。
>>> s = time.time(); bfs((W,W,B,W,W,W,W,B,W,W,B,W,B,B,W,W,W,W,W,W,W,W,W,W,W),(W,) * 25, line5, 5, 5); time.time() - s W W B W W W W B W W B W B B W W W W W W W W W W W B B W B B W W B W W B W B B W W W W W W W W W W W B B W B B B B W B B B W B B W W W W W W W W W W W B B W B B B B W B B B W W B W W W W W W W W W W W B B W B B B B W B B W W W B W W W W W W W W W W W B B W B B B B W B B W W W W W W W W W W W W W W W W W B W W B B W B B W W W W W W W W W W W W W W W W W B W W W W B W W W W W W W W W W W W W W W W W B W B W W B W B W W B W W W W B W W W W B W W W W B B B W W B B B W W B B W W W B B W W W B B W W W B B W W W B B B W W B B W W W B B W W W B B W W W B B W W W B B W W W B B W W W B B W W W B B W W W W B W W W W B W W W W B W W W W B W W W W B W W W W W W W W W W W W W W W W W W W W W W W W W W W W 12.507428407669067
実行時間は約 13 秒かかりました。PyPy3 を使うと約 8.5 秒になりました。上記の実行結果とは異なりますが、最短手順の一例を下図に示します。
↓ ↓
→□□■□□ ■■□■■ ■■□■■ ■■□■■ ■■□■■ →■■□■■ □□■□□
□□■□□ →□□■□□ ■■□■■ ■■□■■ ■■□■■ ■■□■■ →■■□■■
■□■■□ ■□■■□ →■□■■□ ■□□■□ □□□■□ □□□□□ □□□□□
□□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□
□□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□ □□□□□
０ １ ２ ３ ４ ５ ６
↓ ↓ ↓ ↓
□□■□□ □■■□□ ■■■□□ →■■■□□ ■■□□□ ■□□□□ □□□□□
□□■□□ □■■□□ →■■■□□ ■■□□□ ■■□□□ ■□□□□ □□□□□
□□□□□ □■□□□ ■■□□□ ■■□□□ ■■□□□ ■□□□□ □□□□□
□□□□□ □■□□□ ■■□□□ ■■□□□ ■■□□□ ■□□□□ □□□□□
□□□□□ □■□□□ ■■□□□ ■■□□□ ■■□□□ ■□□□□ □□□□□
７ ８ ９ 10 11 12 13
図 : 最短 13 手で解く手順
#
# uo.py : 裏表パズル
#
# Copyright (C) 2022 Makoto Hiroi
#
# 定数
B = 0
W = 1
# ライン
# 0 1 2
# 3 4 5
# 6 7 8
line3 = [
[0, 1, 2], [3, 4, 5], [6, 7, 8],
[0, 3, 6], [1, 4, 7], [2, 5, 8]
]
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
line43 = [
[0,1,2,3], [4,5,6,7], [8,9,10,11],
[0,4,8], [1,5,9], [2,6,10], [3,7,11]
]
# 0 1 2 3
# 4 5 6 7
# 8 9 10 11
# 12 13 14 15
line4 = [
[0,1,2,3], [4,5,6,7], [8,9,10,11], [12,13,14,15],
[0,4,8,12], [1,5,9,13], [2,6,10,14], [3,7,11,15]
]
# 0 1 2 3 4
# 5 6 7 8 9
# 10 11 12 13 14
# 15 16 17 18 19
line54 = [
[0,1,2,3,4], [5,6,7,8,9], [10,11,12,13,14], [15,16,17,18,19],
[0,5,10,15], [1,6,11,16], [2,7,12,17], [3,8,13,18], [4,9,14,19]
]
# 0 1 2 3 4
# 5 6 7 8 9
# 10 11 12 13 14
# 15 16 17 18 19
# 20 21 22 23 24
line5 = [
[0,1,2,3,4], [5,6,7,8,9], [10,11,12,13,14],
[15,16,17,18,19], [20,21,22,23,24],
[0,5,10,15,20], [1,6,11,16,21], [2,7,12,17,22],
[3,8,13,18,23], [4,9,14,19,24]
]
# 盤面の表示
def print_board(b, w, h):
s = ['B', 'W']
for i in range(w * h):
print(s[b[i]], end= ' ')
if (i + 1) % w == 0: print()
print()
# 手順の表示
def print_moves(n, table, w, h):
if n > 0:
print_moves(table[n][1], table, w, h)
print_board(table[n][0], w, h)
# ラインの反転
def reverse_line(b, n, ls):
l = ls[n]
i, j = 0, len(l) - 1
a = list(b)
while i <= j:
x = l[i]
y = l[j]
a[x], a[y] = a[y] ^ 1, a[x] ^ 1
i += 1
j -= 1
return tuple(a)
# 幅優先探索
def bfs(start, goal, ls, w, h):
queue = [(start, -1)]
check = {}
check[start] = True
rc = 0
size = h * w
while rc < len(queue):
b, _ = queue[rc]
if b == goal:
print_moves(rc, queue, w, h)
return
for i in range(len(ls)):
a = reverse_line(b, i, ls)
if a in check: continue
queue.append((a, rc))
check[a] = True
rc += 1
# 最長手数の局面
def solver_max(ls, w, h):
start = (W,) * (w * h)
xs = [start]
check = {}
check[start] = True
move = 0
while True:
ys = []
for b in xs:
for i in range(len(ls)):
a = reverse_line(b, i, ls)
if a in check: continue
ys.append(a)
check[a] = True
if not ys: break
xs = ys
move += 1
print("最長手数 =", move, "個数 =", len(xs))
for b in xs[:4]: print_board(b, w, h)
print("状態の総数 =", len(check))