Hatena::ブログ(Diary)

ザリガニが見ていた...。 このページをアンテナに追加 RSSフィード

2015-01-12

明治ミルクチョコーレートパズルの解をすべて探す

今年の正月明けは、明治ミルクチョコレートパズルの問題に夢中になった...。

このパズルはチョコレートシリーズの中では甘めらしいのだが、各ピースがチョコレートで出来ている訳ではなく、食べられない。甘めというのは難易度のこと。これはABS樹脂で作られたチョコレート風デザインのパズルなのだ。写真で見ると、思わず食べてみたい衝動にかられる。

  • 1ピースは正方形5個の組み合わせで構成される。
  • その組み合わせは全部で12通りある。よって全部で12ピースある。
  • 各ピースにはアルファベットをイメージした名前が付けられている。

  • この12ピースをうまく組み合わせて、6×10(=正方形60個)の箱に収めるのだ。

f:id:zariganitosh:20150110083608p:image:w250

これは紛れもないペントミノ(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行ずつ順に試すことになる。
  • このとき重要になるのがピースの置き方。
  • 例えば、最初のピース形状の配列データをそのまま配置すると、以下のような状態となる。

f:id:zariganitosh:20150110110620p:image:w250

  • しかし、このように配置してしまうと、左上の1ブロックの隙間が永遠に解決できない隙間として残ってしまう...。
  • そこで、形状データを作成する時に保存した、先頭のブロックが何番目から始まるのか?という情報を利用して、以下のように配置している。

f:id:zariganitosh:20150110111135p:image:w250

  • しかし、残念ながら上記の配置では外枠にはみ出ているので、置き方としては失敗である。
  • そのような失敗を「# ピースが飛び出したらそこから先は見ない」下側のでif文判定している。
      • if x - d < 0 or x - d + w > 10 or y + h > 6: continue

  • また、枠からはみ出さなくても、ピース同士が重なってしまう状況も考えられる。

f:id:zariganitosh:20150110112655p:image:w250

  • 上記のような失敗を「# ピースがかぶったらそこから先は見ない」下側のif文で判定している。
      • if (b & p).any(): continue
    • pには、ピース形状の配列が代入されている。
    • bには、ピースを置く部分のboard配列の範囲が切り抜かれた内容が代入されている。
      • b = board[y:y + h, x - d:x - d + w]

  • 以上のチェックをくぐり抜けると、とりあえずピースが置けたことになる。(仮置き状態)

f:id:zariganitosh:20150110125748p:image:w250

  • とりあえずピースが置けた場合は...
    • Pieceオブジェクトに、その時の形状とボード内の位置を記録しておく。
      • pp[i].sel = j
      • pp[i].pos = y * 10 + x - d
    • と同時に、重なりチェック用のboard配列に、形状データを書き込んで次の重なりチェックに備える。
      • b += p

  • 以上の処理をして、次のピースを試す。
  • 次にピースを置く場所は、board配列内の一番小さな値を探して決める。
      • k = board.argmin()
    • 左上から1行ずつ、左から右に検索する。
    • 最小値が複数のある時は、最初に出現する位置となる。
    • kには、左上先頭からn個目という数値nが代入される。(1次元の位置情報)
  • Falseは0とみなされるので、以下の状況では黒枠の位置がその場所になる。

f:id:zariganitosh:20150110132450p:image:w250

  • 上記位置を引数にセットして、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
 +            print
              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)
              print
              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度回転対称な配置もカウントしているためらしい。

f:id:zariganitosh:20150112151422p:image:w450

  • だから、ちょうど4倍の解が出力されてしまうのだ。
  • 対称解は、除外する必要があるらしい。

  • 対称解を除外する正攻法は...
    • 求めた解を保存しておいて、
    • 新たな解を見つけたら、
      • 過去に保存した解と対称でないかチェックする必要がある。
  • しかし、非常に手間と負担のかかる処理となりそう...。

  • そこで、もっと簡単な方法でチェックできないのか調べてみると...

対称解を発生させない検索方法が紹介されていた!

  • フリップあり、90度4回転する(8通りの形状がある)ピースに注目してみると、
  • 例えばFピースは、対称解でも上下対称・左右対称・180度回転対称な形状が現れている。

f:id:zariganitosh:20150112154200p:image:w450

  • 仮に、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から開発すること

sonicdawsonicdaw 2017/07/29 00:27 最近明治ミルクチョコーレートパズルのことを知ってプログラムで解けないか考えていたところこちらにたどり着きました。
詳しい説明とコードをありがとうございます。

参考にさせていただいて、もう少し簡単にピースデータを更新できるようにしてみたソースをアップしました。
https://github.com/sonicdaw/pentomino

sonicdawsonicdaw 2017/07/29 00:27 最近明治ミルクチョコーレートパズルのことを知ってプログラムで解けないか考えていたところこちらにたどり着きました。
詳しい説明とコードをありがとうございます。

参考にさせていただいて、もう少し簡単にピースデータを更新できるようにしてみたソースをアップしました。
https://github.com/sonicdaw/pentomino

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/zariganitosh/20150112/pentomino_programming
リンク元