明治ミルクチョコーレートパズルの解をすべて探す
今年の正月明けは、明治ミルクチョコレートパズルの問題に夢中になった...。
このパズルはチョコレートシリーズの中では甘めらしいのだが、各ピースがチョコレートで出来ている訳ではなく、食べられない。甘めというのは難易度のこと。これはABS樹脂で作られたチョコレート風デザインのパズルなのだ。写真で見ると、思わず食べてみたい衝動にかられる。
- 1ピースは正方形5個の組み合わせで構成される。
- その組み合わせは全部で12通りある。よって全部で12ピースある。
- 各ピースにはアルファベットをイメージした名前が付けられている。
- この12ピースをうまく組み合わせて、6×10（＝正方形60個）の箱に収めるのだ。
これは紛れもないペントミノ（pentomino）パズルのなのだ！このペントミノパズルをコンピューターに解かせる、という試み。こうゆう試みは大好き。さっそく自分でもやってみよう！
難解
- 思い立ったはいいけど、何をどうやって問題を処理していいのか？さっぱり分からない...。
- パズルを配置してその解を見つける処理というのは、自分の中では相当難易度が高い。
- しかし、今回はブロックの配置もプログラミングする必要がある。
- テトロミノ5ピースに対して、ペントミノ12ピース。その組み合わせも膨大になる。
- どうやって、無駄なく、最適な場所を見つけていくのか？
- どうやって、すべての配置を網羅すべきなのか？
さっぱり分からない...。
拝借
- 分からない時は、素直に先達の知恵に頼ることにする。
- 上記記事に登場するパズルの達人は、たった54行のコードでペントミノパズルを解いてしまっている。
- しかも、正月中の突然の問い合わせにもかかわらず、明快に回答。
- おそらく、アドリブ的なコーディングであり、フルスクラッチ*1。
素晴らしい！（自分もいつかは難問でも自力で考え抜いて、素早くコーディングできる人になりたい）
- 環境に合わせて若干の修正をした。
- 日本語コメントがあるのでエンコーディング宣言が必要だった。
- ピースの形状データを配列として取得するように修正してみた。
+# coding: utf-8 import numpy as np class Piece: def __init__(self, s, t): h = t // 100 # 縦 m = (t // 10) % 10 # 反転する(2)/しない(1) n = t % 10 # 回転数 - a = np.array(1).reshape(h, -1) + a = np.array(map(int, s)).reshape(h, -1) self.pos = -1 self.sel = 0 self.cand = []
- 修正したコードを実行してみると...
# coding: utf-8 import numpy as np class Piece: def __init__(self, s, t): h = t // 100 # 縦 m = (t // 10) % 10 # 反転する(2)/しない(1) n = t % 10 # 回転数 a = np.array(map(int, s)).reshape(h, -1) self.pos = -1 self.sel = 0 self.cand = [] for i in range(m): for j in range(n): self.cand.append((a, a.argmax())) a = np.rot90(a) a = np.fliplr(a) pp = [Piece('010111010', 311), Piece('111101', 214), Piece('110011001', 314), Piece('110011010', 324), Piece('110010011', 322), Piece('111110', 224), Piece('11100011', 224), Piece('11110100', 224), Piece('111010010', 314), Piece('11111000', 224), Piece('111100100', 314), Piece('11111', 112)] def allp(pp): for i, p in enumerate(pp): if p.pos < 0: for j, c in enumerate(p.cand): yield i, j, c[0], c[1] board = np.array([False] * 60).reshape(6, 10) def chk(board, pp, x, y, lvl): for i, j, p, d in allp(pp): h, w = p.shape # ピースが飛び出したらそこから先は見ない if x - d < 0 or x - d + w > 10 or y + h > 6: continue b = board[y:y + h, x - d:x - d + w] # ピースがかぶったらそこから先は見ない if (b & p).any(): continue pp[i].sel = j pp[i].pos = y * 10 + x - d # すべてのピースを置ききったらTrueを返す（recursiveコールの終了） if lvl == 11: return True b += p k = board.argmin() # ここまで成功したら次のピースを試す if chk(board, pp, k % 10, k // 10, lvl + 1): return True # 失敗したら巻き戻して別の手を試す b -= p pp[i].pos = -1 return False chk(board, pp, 0, 0, 0) l = np.zeros((6, 10)) for i, p in enumerate(pp): x, y, z = p.pos % 10, p.pos // 10, p.cand[p.sel][0] l[y:y + z.shape[0], x:x + z.shape[1]] += z * i print('\n'.join(''.join(chr(int(j) + 65) for j in i) for i in l))正月の酔っ払い物理学者が数学者の皮を被った天使に出会うお話 | カメリオ開発者ブログ
- 見事に解が出力された！
$ python pentamino.py
BBBCCDDIII
BGBACCDDIL
GGAAACDJIL
GEEAJJJJKL
GEFFHHHHKL
EEFFFHKKKL
一体どのように解を見つけているのか？コードを追ってみた。
すべてのピース形状をPieceオブジェクトの配列に保存する
- まず前半のコードで、すべてのピース形状をPieceオブジェクトの配列として保存している。
$ python >>> import numpy as np >>> class Piece: ... def __init__(self, s, t): ... h = t // 100 # 縦 ... m = (t // 10) % 10 # 反転する(2)/しない(1) ... n = t % 10 # 回転数 ... a = np.array(map(int, s)).reshape(h, -1) ... self.pos = -1 ... self.sel = 0 ... self.cand = [] ... for i in range(m): ... for j in range(n): ... self.cand.append((a, a.argmax())) ... a = np.rot90(a) ... a = np.fliplr(a) ... >>> pp = [Piece('010111010', 311), ... Piece('111101', 214), ... Piece('110011001', 314), ... Piece('110011010', 324), ... Piece('110010011', 322), ... Piece('111110', 224), ... Piece('11100011', 224), ... Piece('11110100', 224), ... Piece('111010010', 314), ... Piece('11111000', 224), ... Piece('111100100', 314), ... Piece('11111', 112)]
- 試しにPiece('010111010', 311)を実行してみると...
- 以下のようなPieceオブジェクトが生成されるのだ！
- '010111010'は、ピース形状のデータ。
- 311にはそれぞれの桁数ごとに意味があって、3行・反転ポジション1つ・回転ポジション1つ、という意味。
- 例：
- ＋形状は、3行のデータを持つ。反転しても・90度回転しても形状が変化しないので、反転ポジション1つ・回転ポジション1つとなる。（311）
- P形状は、3行のデータを持つ。反転変化あり・0・90・180・270度回転して異なる形状になるので、反転ポジション2つ・回転ポジション4つとなる。（324）
- −形状は、1行のデータを持つ。反転変化なし・0・90度回転のみ異なる形状になるので、反転ポジション1つ・回転ポジション2つとなる。（112）
>>> p = Piece('010111010', 311)
>>> p
<__main__.Piece instance at 0x109bbda28>
>>> p.pos
-1
>>> p.sel
0
>>> p.cand
[(array([[0, 1, 0],
[1, 1, 1],
[0, 1, 0]]), 1)]
- p.candの配列データはピース形状を表現している。（ブロックあり=1・なし=0）
- 配列に続く数値は、ピース形状の先頭が何番目の配列要素から始まるかを表現している。
- 上記の例では＋形状なので、先頭のブロックは2番目の要素から始まっている。
- 配列のインデックスは0、1、2...と続くので、2番目のインデッス値=1が設定されているのだ。
- この数値は、ピースを配置する時に、隙間なく置くための重要な情報となる！
素晴しきnumpy！
ここで...
- このコードをより詳しく理解するには、numpyの挙動を理解する必要があると気付いた。
- Pieceクラスでは('010111010', 311)という引数から2次元配列に変換しているのだけど、
- これはもう、numpy（数値演算ライブラリ）の行列演算能力から絶大な恩恵を受けている。
- さらに、ピースの回転・反転、ピース同士の重なり判定、ボードにピースを並べたり、面倒と思える処理をnumpyは一瞬で解決してくれるのだ。
- 自分はpythonをほとんど使ったことがなかったが、
numpyがあるならpython使いたい！と思わせるレベルの魅力がある。
- コード中に使われているnumpyの技を探ってみた。
行列の組み替え
- np.arrayのreshapeは、配列をお好みの行列に組み替えてくれるのだ。
- reshape(3, 2)なら、3行×2列。
- reshape(2, 3)なら、2行×3列。
- どちらかがマイナスの指定は、プラスの指定に対応した値で組み替えてくれる。
- reshape(3, -1)なら、3行×全要素数÷3列。
>>> import numpy as np
>>> list = map(int, '010111010')
>>> list
[0, 1, 0, 1, 1, 1, 0, 1, 0]
>>> np.array(list).reshape(3, -1)
array([[0, 1, 0],
[1, 1, 1],
[0, 1, 0]])
最大値・最小値の位置を調べる
- argmaxは、配列中の最大値のインデックス値を返す。
- インデックス値は一次元配列に変換された値になる。
>>> a = np.array([1,2,3,4,2,1]).reshape(2, -1)
>>> a
array([[1, 2, 3],
[4, 2, 1]])
>>> a.argmax()
3
- この仕組みを利用して、ピース形状の先頭ブロックの場所を特定しているのだ。
>>> list = map(int, '010111010')
>>> a = np.array(list).reshape(3, -1)
>>> a
array([[0, 1, 0],
[1, 1, 1],
[0, 1, 0]])
>>> a.argmax()
1
- 同様にa.argmin()は、配列中の最小値のインデックス値を返す。
- この仕組みを利用して、boardの中で次にピースを置く位置を素早く見つけているのだ。
>>> a.argmin() 0
行列の回転・反転
- np.rot90(a)は、反時計回りに90度回転する。
>>> a
array([[1, 1, 1],
[1, 1, 0]])
>>> np.rot90(a)
array([[1, 0],
[1, 1],
[1, 1]])
- 180度・270度回転したい時は、回数を指定する。
>>> np.rot90(a, 2)
array([[0, 1, 1],
[1, 1, 1]])
>>> np.rot90(a, 3)
array([[1, 1],
[1, 1],
[0, 1]])
- np.fliplr(a)は、左右方向に反転する。（裏返す）
>>> a
array([[1, 1, 1],
[1, 1, 0]])
>>> np.fliplr(a)
array([[1, 1, 1],
[0, 1, 1]])
- np.flipup(a)は、上下方向に反転する。（裏返す）
>>> a
array([[1, 1, 1],
[1, 1, 0]])
>>> np.flipud(a)
array([[1, 1, 0],
[1, 1, 1]])
配列の任意の範囲を切り出す
- 大きな配列から範囲指定による切り出し。
>>> board = np.array(range(60)).reshape(6, 10)
>>> board
array([[ 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, 25, 26, 27, 28, 29],
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
[50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])
>>> board[1:3, 2:6]
array([[12, 13, 14, 15],
[22, 23, 24, 25]])
- 範囲指定は、配列要素の境界を指定していると考えることにした。
配列の演算
- 配列と数値の演算
>>> board * 10
array([[120, 130, 140, 150],
[220, 230, 240, 250]])
- 配列同士の演算
>>> board = np.array(range(60)).reshape(6, 10)
>>> board
array([[ 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, 25, 26, 27, 28, 29],
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
[50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])
>>> b = board[1:3, 2:6]
>>> b
array([[12, 13, 14, 15],
[22, 23, 24, 25]])
>>> z = np.zeros((2, 4))
>>> z
array([[ 0., 0., 0., 0.],
[ 0., 0., 0., 0.]])
- コピーする演算
- b = b * zは、新たな配列bとしてコピーしてから演算するようだ。
- そのため、取り出し元のboard配列に影響しない。
>>> b = b * z
>>> b
array([[ 0., 0., 0., 0.],
[ 0., 0., 0., 0.]])
>>> board
array([[ 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, 25, 26, 27, 28, 29],
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
[50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])
- 置き換える演算
- b *= zは、演算結果を元の配列bに上書きする。
- よって、取り出し元のboard配列に影響を与える。
>>> b = board[1:3, 2:6]
>>> b
array([[12, 13, 14, 15],
[22, 23, 24, 25]])
>>> b *= z
>>> b
array([[0, 0, 0, 0],
[0, 0, 0, 0]])
>>> board
array([[ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9],
[10, 11, 0, 0, 0, 0, 16, 17, 18, 19],
[20, 21, 0, 0, 0, 0, 26, 27, 28, 29],
[30, 31, 32, 33, 34, 35, 36, 37, 38, 39],
[40, 41, 42, 43, 44, 45, 46, 47, 48, 49],
[50, 51, 52, 53, 54, 55, 56, 57, 58, 59]])
- b = b * zとb *= zになぜこのような違いが生まれるのか、正確なところはわからないが...
- b = b * zのような書き方を利用することで、ピースの衝突判定が簡単にできる！
- また、b *= zのような書き方を利用することで、boardにピースを素早く並べるられる！
素晴しきnumpy！（惚れた）
パズルの解を求める
いよいよ、パズルの解を求める処理が始まる。
>>> def allp(pp): ... for i, p in enumerate(pp): ... if p.pos < 0: ... for j, c in enumerate(p.cand): ... yield i, j, c[0], c[1] ... >>> def chk(board, pp, x, y, lvl): ... for i, j, p, d in allp(pp): ... h, w = p.shape ... # ピースが飛び出したらそこから先は見ない ... if x - d < 0 or x - d + w > 10 or y + h > 6: continue ... b = board[y:y + h, x - d:x - d + w] ... # ピースがかぶったらそこから先は見ない ... if (b & p).any(): continue ... pp[i].sel = j ... pp[i].pos = y * 10 + x - d ... # すべてのピースを置ききったらTrueを返す（recursiveコールの終了） ... if lvl == 11: return True ... b += p ... k = board.argmin() ... # ここまで成功したら次のピースを試す ... if chk(board, pp, k % 10, k // 10, lvl + 1): return True ... # 失敗したら巻き戻して別の手を試す ... b -= p ... pp[i].pos = -1 ... return False ... >>> board = np.array([False] * 60).reshape(6, 10) >>> chk(board, pp, 0, 0, 0) False
- allp(pp)は、すべてのピース形状（反転・回転による変化も含む）を網羅した順序リスト（のようなもの）を返す関数。
- Pieceオブジェクトの配列から、i=ピースNo.（0-11）、j=形状No.（0-7）、c[0]=形状データの配列、c[1]=ピース形状の先頭ブロックの位置、を順に渡してくれるのだ。
- 以上の準備をして、chk(board, pp, x, y, lvl)で一つずつ、すべてのピース形状が置けるかどうかを試すのだ。
- board=ピースが存在するかしないかを記録した6×10の配列。（最初はFalseで満たされた状態）
- pp=Pieceオブジェクトの配列。
- x, y=ピースを置く場所。ボード内の座標。
- lvl=何個目のピースを試しているかという情報。
- ピースを置く位置は、10×6のboard配列の左上から右側に向かって、1行ずつ順に試すことになる。
- このとき重要になるのがピースの置き方。
- 例えば、最初のピース形状＋の配列データをそのまま配置すると、以下のような状態となる。
- しかし、このように配置してしまうと、左上の1ブロックの隙間が永遠に解決できない隙間として残ってしまう...。
- そこで、形状データを作成する時に保存した、先頭のブロックが何番目から始まるのか？という情報を利用して、以下のように配置している。
- しかし、残念ながら上記の配置では外枠にはみ出ているので、置き方としては失敗である。
- そのような失敗を「# ピースが飛び出したらそこから先は見ない」下側のでif文判定している。
-
- if x - d < 0 or x - d + w > 10 or y + h > 6: continue
-
- また、枠からはみ出さなくても、ピース同士が重なってしまう状況も考えられる。
- 上記のような失敗を「# ピースがかぶったらそこから先は見ない」下側のif文で判定している。
-
- if (b & p).any(): continue
- pには、ピース形状の配列が代入されている。
- bには、ピースを置く部分のboard配列の範囲が切り抜かれた内容が代入されている。
- b = board[y:y + h, x - d:x - d + w]
-
- 以上のチェックをくぐり抜けると、とりあえずピースが置けたことになる。（仮置き状態）
- とりあえずピースが置けた場合は...
- Pieceオブジェクトに、その時の形状とボード内の位置を記録しておく。
- pp[i].sel = j
- pp[i].pos = y * 10 + x - d
- と同時に、重なりチェック用のboard配列に、形状データを書き込んで次の重なりチェックに備える。
- b += p
- Pieceオブジェクトに、その時の形状とボード内の位置を記録しておく。
- 以上の処理をして、次のピースを試す。
- 次にピースを置く場所は、board配列内の一番小さな値を探して決める。
-
- k = board.argmin()
- 左上から1行ずつ、左から右に検索する。
- 最小値が複数のある時は、最初に出現する位置となる。
- kには、左上先頭からn個目という数値nが代入される。（1次元の位置情報）
-
- Falseは0とみなされるので、以下の状況では黒枠の位置がその場所になる。
- 上記位置を引数にセットして、chk()関数自身を再帰呼び出しするのだ。
-
- if chk(board, pp, k % 10, k // 10, lvl + 1): return True
- k%10、k//10、によって1次元の位置情報を、2次元の位置情報に変換している。
- lvl（レベルの略？）は、何個目のピースを試しているかという情報。
-
- 以上の再帰呼び出しを繰り返して、すべてのピースが置けた場合は、その時の状態がパズルの解となるのだ！
- すべてのピースが置けた場合はlvlが11となるので、それが再帰呼び出しを終了するきっかけとなる。
-
- if lvl == 11: return True
-
- しかし、lvlが11となる前にすべてのピース形状を試して何も置けなくなるとFalseが返り、それは失敗の合図。
- とりあえず仮置きしたピースを取り除いて、次のピースを試す。
-
- b -= p
- pp[i].pos = -1
- Pieceオブジェクトの位置情報は、使用済みのピースかどうか判定する情報にもなっているので-1に戻すのだ。
- 使用済みのピースかどうかは、allp(pp)関数内で判定している。
- if p.pos < 0:
-
パズルの解を出力する
最後に解を出力する処理。
>>> l = np.zeros((6, 10)) >>> for i, p in enumerate(pp): ... x, y, z = p.pos % 10, p.pos // 10, p.cand[p.sel][0] ... l[y:y + z.shape[0], x:x + z.shape[1]] += z * i ... >>> print('\n'.join(''.join(chr(int(j) + 65) for j in i) for i in l)) BBBCCDDIII BGBACCDDIL GGAAACDJIL GEEAJJJJKL GEFFHHHHKL EEFFFHKKKL
- 現状のパズルの解は、Pieceオブジェクトに保存された一次元の位置情報の座標でしかない。
- 座標情報から、各ピースをAからLの文字で表現し、ボードに詰めた状態に変換しているのだ。
なるほど、ようやくコードの流れを見切った！
すべての解を求めたい
- コードの流れを見切ると、自分流にコードを修正したくなる。
- どうせなら、ペントミノパズルのすべての解を求めてみたくなった。
やってみた。
分かりやすい表現に修正
- まずは、より自分が理解しやすいコードにするため、変数名や関数名のネーミングを分かりやすい名前に変更しておく。
- また、行数、反転する・しない、回転数を3桁にまとめた引数を、3つの引数に分解しておいた。
- さらに、board（10×6）を重なり判定だけに利用するのはもったいないので、ピースの番号を書き込むようにしてみた。
# coding: utf-8 import numpy as np # すべてのピース形状をPieceオブジェクトの配列に保存する class Piece: def __init__(self, s, h,m,n): a = np.array(map(int, s)).reshape(h, -1) self.used = False self.form = [] for i in range(m): for j in range(n): self.form.append((a, a.argmax())) a = np.rot90(a) a = np.fliplr(a) pp = [Piece('010111010', 3,1,1), Piece('111101', 2,1,4), Piece('110011001', 3,1,4), Piece('110011010', 3,2,4), Piece('110010011', 3,2,2), Piece('111110', 2,2,4), Piece('11100011', 2,2,4), Piece('11110100', 2,2,4), Piece('111010010', 3,1,4), Piece('11111000', 2,2,4), Piece('111100100', 3,1,4), Piece('11111', 1,1,2)] # パズルの解を求める def piece_all(pp): for piece_i, piece in enumerate(pp): if not piece.used: for form_j, form in enumerate(piece.form): piece_matrix, piece_origin = form yield piece_i, form_j, piece_matrix, piece_origin def chk(board, pp, x, y, lvl): for i, j, piece_matrix, piece_origin in piece_all(pp): h, w = piece_matrix.shape ox = x - piece_origin # ピースが飛び出したらそこから先は見ない if ox < 0 or ox + w > 10 or y + h > 6: continue board_section = board[y:y + h, ox:ox + w] # ピースがかぶったらそこから先は見ない if (board_section * piece_matrix).any(): continue board_section += piece_matrix * (i + 1) pp[i].used = True # すべてのピースを置ききったらTrueを返す（recursiveコールの終了） if lvl == 11: return True k = board.argmin() # ここまで成功したら次のピースを試す if chk(board, pp, k % 10, k // 10, lvl + 1): return True # 失敗したら巻き戻して別の手を試す board_section -= piece_matrix * (i + 1) pp[i].used = False return False board = np.zeros((6, 10)) chk(board, pp, 0, 0, 0) print board
すべての解を求める
- 現状は、最初の解を見つけると、return Trueの連鎖でパズルを解くことをやめてしまう...。
- すべての解を求めるには、解を見つけた時もパズルをやめずに、次の解を求めて検索する必要がある。
- まず、return Trueの連鎖を断ち切るために、以下のコードを修正した。
- if chk(board, pp, k % 10, k // 10, lvl + 1): return True
+ chk(board, pp, k % 10, k // 10, lvl + 1)
- 次に、解を見つけた時の処理。解を見つけたら...
- 解を出力する。
- そして、pieceを元に戻して、（次の解を見つける準備）
- returnする。
@@ -50,7 +50,11 @@ def chk(board, pp, x, y, lvl):
board_section += piece_matrix * (i + 1)
pp[i].used = True
# すべてのピースを置ききったらTrueを返す（recursiveコールの終了）
- if lvl == 11: return True
+ if lvl == 11:
+ print board
+ board_section -= piece_matrix * (i + 1)
+ pp[i].used = False
+ return True
k = board.argmin()
# ここまで成功したら次のピースを試す
chk(board, pp, k % 10, k // 10, lvl + 1)
@@ -63,4 +67,3 @@ def chk(board, pp, x, y, lvl):
board = np.zeros((6, 10))
chk(board, pp, 0, 0, 0)
-print board
- 何個目の解か分かるようにカウンターも追加してみた。
@@ -39,6 +39,7 @@ def piece_all(pp):
yield piece_i, form_j, piece_matrix, piece_origin
def chk(board, pp, x, y, lvl):
+ global counter
for i, j, piece_matrix, piece_origin in piece_all(pp):
h, w = piece_matrix.shape
ox = x - piece_origin
@@ -51,7 +52,10 @@ def chk(board, pp, x, y, lvl):
pp[i].used = True
# すべてのピースを置ききったらTrueを返す（recursiveコールの終了）
if lvl == 11:
+ counter += 1
+ print 'No', counter
print board
board_section -= piece_matrix * (i + 1)
pp[i].used = False
return True
@@ -65,5 +69,7 @@ def chk(board, pp, x, y, lvl):
+counter = 0
board = np.zeros((6, 10))
chk(board, pp, 0, 0, 0)
+print '解合計', counter
- 以上の修正コードを実行してみると、目論見どおり解を次々と出力し始めた！
$ python pentomino.py
No. 1
[[ 2. 2. 2. 3. 3. 4. 4. 9. 9. 9.]
[ 2. 7. 2. 1. 3. 3. 4. 4. 9. 12.]
[ 7. 7. 1. 1. 1. 3. 4. 10. 9. 12.]
[ 7. 5. 5. 1. 10. 10. 10. 10. 11. 12.]
[ 7. 5. 6. 6. 8. 8. 8. 8. 11. 12.]
[ 5. 5. 6. 6. 6. 8. 11. 11. 11. 12.]]
No. 2
[[ 2. 2. 2. 3. 3. 4. 4. 9. 9. 9.]
[ 2. 8. 2. 1. 3. 3. 4. 4. 9. 12.]
[ 10. 8. 1. 1. 1. 3. 4. 7. 9. 12.]
[ 10. 8. 8. 1. 5. 11. 7. 7. 6. 12.]
[ 10. 8. 5. 5. 5. 11. 7. 6. 6. 12.]
[ 10. 10. 5. 11. 11. 11. 7. 6. 6. 12.]]
No. 3
[[ 2. 2. 2. 3. 3. 4. 4. 9. 9. 9.]
[ 2. 8. 2. 1. 3. 3. 4. 4. 9. 12.]
[ 10. 8. 1. 1. 1. 3. 4. 7. 9. 12.]
[ 10. 8. 8. 1. 5. 11. 6. 7. 7. 12.]
[ 10. 8. 5. 5. 5. 11. 6. 6. 7. 12.]
[ 10. 10. 5. 11. 11. 11. 6. 6. 7. 12.]]
...中略...
- しかし、3時間16分経過してもNo. 335までしか求められない...。時間かかり過ぎ。
高速化を求める
- そこで、高速化を求めて6行×10列のboardを、10行×6列に変更してみた。
- boardサイズを可変できるように、行数と列数を変数に代入しておいた。
- 解を出力する時だけ、90度回転させて本来の6行×10列に変換している。
@@ -40,11 +40,12 @@ def piece_all(pp):
def chk(board, pp, x, y, lvl):
global counter
+ board_h, board_w = board.shape
for i, j, piece_matrix, piece_origin in piece_all(pp):
h, w = piece_matrix.shape
ox = x - piece_origin
# ピースが飛び出したらそこから先は見ない
- if ox < 0 or ox + w > 10 or y + h > 6: continue
+ if ox < 0 or ox + w > board_w or y + h > board_h: continue
board_section = board[y:y + h, ox:ox + w]
# ピースがかぶったらそこから先は見ない
if (board_section * piece_matrix).any(): continue
@@ -54,14 +55,14 @@ def chk(board, pp, x, y, lvl):
if lvl == 11:
counter += 1
print 'No', counter
- print board
+ print np.rot90(board)
board_section -= piece_matrix * (i + 1)
pp[i].used = False
return True
k = board.argmin()
# ここまで成功したら次のピースを試す
- chk(board, pp, k % 10, k // 10, lvl + 1)
+ chk(board, pp, k % board_w, k // board_w, lvl + 1)
# 失敗したら巻き戻して別の手を試す
board_section -= piece_matrix * (i + 1)
pp[i].used = False
@@ -70,6 +71,6 @@ def chk(board, pp, x, y, lvl):
counter = 0
-board = np.zeros((6, 10))
+board = np.zeros((10, 6))
chk(board, pp, 0, 0, 0)
print '解合計', counter
- すると、わずか5分程度でNo. 800の解まで出力された！
劇的な高速化！
- どうやら、左から右、上から下にpieceの置き方を検索する場合、boardの横幅となる列幅が狭いほど高速に検索できるようだ。
- おそらく「# ピースが飛び出したらそこから先は見ない」の条件によって、列数が狭い方が早いうちに失敗を確定できるからと思われる。
- 待つこと50分、とうとうすべての解が出力されたようだ！
$ python pentomino.py
...中略...
No 9354
[[ 2. 2. 2. 10. 10. 10. 10. 7. 7. 3.]
[ 2. 6. 2. 10. 1. 7. 7. 7. 3. 3.]
[ 6. 6. 11. 1. 1. 1. 4. 3. 3. 9.]
[ 6. 6. 11. 5. 1. 4. 4. 9. 9. 9.]
[ 11. 11. 11. 5. 5. 5. 4. 4. 8. 9.]
[ 12. 12. 12. 12. 12. 5. 8. 8. 8. 8.]]
No 9355
[[ 10. 10. 7. 2. 2. 2. 3. 6. 6. 6.]
[ 10. 7. 7. 2. 1. 2. 3. 3. 6. 6.]
[ 10. 7. 11. 1. 1. 1. 4. 3. 3. 9.]
[ 10. 7. 11. 5. 1. 4. 4. 9. 9. 9.]
[ 11. 11. 11. 5. 5. 5. 4. 4. 8. 9.]
[ 12. 12. 12. 12. 12. 5. 8. 8. 8. 8.]]
No 9356
[[ 10. 10. 7. 2. 2. 2. 6. 6. 6. 3.]
[ 10. 7. 7. 2. 1. 2. 6. 6. 3. 3.]
[ 10. 7. 11. 1. 1. 1. 4. 3. 3. 9.]
[ 10. 7. 11. 5. 1. 4. 4. 9. 9. 9.]
[ 11. 11. 11. 5. 5. 5. 4. 4. 8. 9.]
[ 12. 12. 12. 12. 12. 5. 8. 8. 8. 8.]]
解合計 9356
重複を排除する
- すべての解が出力されたと喜んだのも束の間、Webを検索してみると、ペントミノの解は2339通りらしい。
- しかし、上記で出力された解は9356通りもある。
なぜ？
- 実は、9356 = 2339 × 4なのである。
- どうやら、ある一つのオリジナル解に対して、左右対称・上下対称・180度回転対称な配置もカウントしているためらしい。
- だから、ちょうど4倍の解が出力されてしまうのだ。
- 対称解は、除外する必要があるらしい。
- 対称解を除外する正攻法は...
- 求めた解を保存しておいて、
- 新たな解を見つけたら、
- 過去に保存した解と対称でないかチェックする必要がある。
- しかし、非常に手間と負担のかかる処理となりそう...。
- そこで、もっと簡単な方法でチェックできないのか調べてみると...
対称解を発生させない検索方法が紹介されていた！
-
-
- 対称なものはできない探索方法 - karetta.jp（素晴らしい情報に感謝です！）
-
- フリップあり、90度4回転する（8通りの形状がある）ピースに注目してみると、
- 例えばFピースは、対称解でも上下対称・左右対称・180度回転対称な形状が現れている。
- 仮に、Fピースの形状をオリジナルと90度回転のみに制限できれば、対称解は発生しない、という考え方。
-
- F形状に限らず、8通りの形状があるP・N・Y・L形状のどれか一つを制限しても同様の効果があるはず。
-
- Piece('110011010', 3,2,4),
+ Piece('110011010', 3,1,2),
- たったこれだけの修正をして、実行してみると...
$ python pentomino.py
No 2337
[[ 2. 2. 2. 10. 10. 10. 10. 7. 7. 3.]
[ 2. 6. 2. 10. 1. 7. 7. 7. 3. 3.]
[ 6. 6. 11. 1. 1. 1. 4. 3. 3. 9.]
[ 6. 6. 11. 5. 1. 4. 4. 9. 9. 9.]
[ 11. 11. 11. 5. 5. 5. 4. 4. 8. 9.]
[ 12. 12. 12. 12. 12. 5. 8. 8. 8. 8.]]
No 2338
[[ 10. 10. 7. 2. 2. 2. 3. 6. 6. 6.]
[ 10. 7. 7. 2. 1. 2. 3. 3. 6. 6.]
[ 10. 7. 11. 1. 1. 1. 4. 3. 3. 9.]
[ 10. 7. 11. 5. 1. 4. 4. 9. 9. 9.]
[ 11. 11. 11. 5. 5. 5. 4. 4. 8. 9.]
[ 12. 12. 12. 12. 12. 5. 8. 8. 8. 8.]]
No 2339
[[ 10. 10. 7. 2. 2. 2. 6. 6. 6. 3.]
[ 10. 7. 7. 2. 1. 2. 6. 6. 3. 3.]
[ 10. 7. 11. 1. 1. 1. 4. 3. 3. 9.]
[ 10. 7. 11. 5. 1. 4. 4. 9. 9. 9.]
[ 11. 11. 11. 5. 5. 5. 4. 4. 8. 9.]
[ 12. 12. 12. 12. 12. 5. 8. 8. 8. 8.]]
解合計 2339
- 待つこと20分、
見事、2339通りの解になった！
最終コード
- 以下、コメントを修正したここまでのコード。
# coding: utf-8 import numpy as np # すべてのピース形状をPieceオブジェクトの配列に保存する class Piece: def __init__(self, s, h,m,n): a = np.array(map(int, s)).reshape(h, -1) self.used = False self.form = [] for i in range(m): for j in range(n): self.form.append((a, a.argmax())) a = np.rot90(a) a = np.fliplr(a) pp = [Piece('010111010', 3,1,1), Piece('111101', 2,1,4), Piece('110011001', 3,1,4), Piece('110011010', 3,1,2), Piece('110010011', 3,2,2), Piece('111110', 2,2,4), Piece('11100011', 2,2,4), Piece('11110100', 2,2,4), Piece('111010010', 3,1,4), Piece('11111000', 2,2,4), Piece('111100100', 3,1,4), Piece('11111', 1,1,2)] # パズルの解を求める def piece_all(pp): for piece_i, piece in enumerate(pp): if not piece.used: for form_j, form in enumerate(piece.form): piece_matrix, piece_origin = form yield piece_i, form_j, piece_matrix, piece_origin def chk(board, pp, x, y, lvl): global counter board_h, board_w = board.shape for i, j, piece_matrix, piece_origin in piece_all(pp): h, w = piece_matrix.shape ox = x - piece_origin # ピースが飛び出したらそこから先は見ない if ox < 0 or ox + w > board_w or y + h > board_h: continue board_section = board[y:y + h, ox:ox + w] # ピースがかぶったらそこから先は見ない if (board_section * piece_matrix).any(): continue # ピースを置く board_section += piece_matrix * (i + 1) pp[i].used = True # すべてのピースを置ききったらTrueを返す（recursiveコールの終了） if lvl == 11: counter += 1 print 'No', counter print np.rot90(board) print # ピースを戻す board_section -= piece_matrix * (i + 1) pp[i].used = False return True # 次のピースを試す k = board.argmin() chk(board, pp, k % board_w, k // board_w, lvl + 1) # ピースを戻す board_section -= piece_matrix * (i + 1) pp[i].used = False return False counter = 0 board = np.zeros((10, 6)) chk(board, pp, 0, 0, 0) print '解合計', counter
*1:何もない0から開発すること
