何百～何千通りも答えのある箱詰めパズルを解く（レベル１：テトロミノ）

ジグソーパズルではなくて、何も描いていないピースをケースから取り出して、それをきれいにケースに戻す「箱詰めパズル」、ありますよね。たとえば、こういうやつです。

- 脳ブロック
https://bb.tenyo.co.jp/products/index.html

うちの子らはこのブロックを夢中になって解いているのですが、私はこれを解くプログラムをPythonで書いてみました。

# まずはケースを用意します

横の長さ `x` 縦の長さ `y` のケースを用意します。まずは、１０未満のランダムな整数がケースに入るようにします。


```Python
import random
def generate(x, y):
    return [[random.randrange(10) for _ in range(x)] for _ in range(y)]
```

これを図示できるようにしましょう。



```Python
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt

def depict(matrix):
    plt.imshow(matrix, interpolation='nearest', cmap=plt.cm.gist_ncar)
    plt.xticks(np.arange(len(matrix[0])), range(len(matrix[0])), rotation=90)
    plt.yticks(np.arange(len(matrix)), range(len(matrix)))
    plt.tight_layout()
    plt.show()
```

図示します。


```Python
matrix = generate(8, 5)
depict(matrix)
matrix
```

![noblock_puzzle_5_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/c572a8eb-c90b-a254-e495-c0106271376a.png)





    [[6, 1, 6, 5, 2, 0, 3, 5],
     [5, 4, 1, 4, 3, 6, 6, 8],
     [3, 2, 4, 7, 5, 7, 8, 8],
     [7, 6, 7, 2, 8, 7, 5, 4],
     [0, 4, 3, 2, 3, 1, 0, 3]]



これでケースはできました。次からは、この「色」（整数）が「ピース」を表すことにします。

# ピースを置く準備をします

ケースの中で、何もピースを置いていないマスをに整数 `-1` を置きましょう。


```Python
def generate(x, y):
    return [[-1 for _ in range(x)] for _ in range(y)]

matrix = generate(8, 5)
depict(matrix)
matrix
```

![noblock_puzzle_7_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/8f3ddafd-2666-796d-74ca-086594517198.png)






    [[-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1]]



隅に `0` の正方形を置きます。これだけではパズルのピースにはなりませんね。


```Python
x_length = 8
y_length = 5
matrix = generate(x_length, y_length)

piece_id = 0
x = 0
y = 0
matrix[y][x] = piece_id

depict(matrix)
matrix
```

![noblock_puzzle_9_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/10419def-d9b4-c2ca-f55c-5feb888b6eea.png)






    [[0, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1]]



# ピースを置きます

実際のパズルでは、たとえば正方形が４つ連なったような形をしています。これを作ってみましょう。

まず、最初に置いた正方形（またはその集合）の隣の正方形を得るための関数を作ります。


```Python
def get_rand_neighbor(piece, matrix):
    neighbors = []
    for x, y in piece:
        for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            if x - dx < 0 or x - dx >= len(matrix[0]):
                pass
            elif y - dy < 0 or y - dy >= len(matrix):
                pass
            elif matrix[y - dy][x - dx] == -1:
                neighbors.append([x - dx, y - dy])

    return neighbors
```

上のような動作を、指定された回数だけ繰り返して、望みの大きさの「ピース」を作りましょう。


```Python
def get_new_piece(matrix, piece_size):
    piece = []

    for x in range(x_length):
        for y in range(y_length):
            if matrix[y][x] == -1:
                piece.append([x, y])
                break
        if len(piece) > 0:
            break

    for i in range(piece_size - 1):
        neighbors = get_rand_neighbor(piece, matrix)
        random.shuffle(neighbors)
        for x, y in neighbors:
            if [x, y] not in piece:
                piece.append([x, y])
                break
    
    return piece
```

これで準備ができました。さあ、ピースを１つ置いてみます。


```Python
x_length = 8
y_length = 5
piece_size = 4
matrix = generate(x_length, y_length)

piece_id = 0
piece = get_new_piece(matrix, piece_size)
for x, y in piece:
    matrix[y][x] = piece_id

depict(matrix)
matrix
```

![noblock_puzzle_15_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/cc16c44e-36c8-dd48-d258-847cc9849413.png)






    [[0, -1, -1, -1, -1, -1, -1, -1],
     [0, 0, 0, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1],
     [-1, -1, -1, -1, -1, -1, -1, -1]]



それっぽくなりましたね。ピースが占有するマスは `0` 以上の整数が与えられ、ピースに占有されていないマスは `-1` のままになっています。

# 置けるところまで置いてみます

次は、`-1` のままになっているマスに、次々にピースを置いていきましょう。置けるところまで置いてみます。


```Python
x_length = 8
y_length = 5
piece_size = 4
matrix = generate(x_length, y_length)

piece_id = 0
piece = get_new_piece(matrix, piece_size)

while len(piece) == piece_size:
    for x, y in piece:
        matrix[y][x] = piece_id
    depict(matrix)
    
    piece = get_new_piece(matrix, piece_size)
    piece_id += 1

matrix
```

![noblock_puzzle_17_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/7f4c2a96-28d6-e309-eeea-1406f2031fe4.png)

![noblock_puzzle_17_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/587cc369-70c3-9851-b274-236df7d71d40.png)

![noblock_puzzle_17_2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/0c051bc7-7f85-4680-7bca-0cf183753200.png)


![noblock_puzzle_17_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/5f9b3fd9-89d2-8012-d3c5-3c5e898d871a.png)


![noblock_puzzle_17_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/70234c23-a1df-9088-ad19-98482edb0566.png)

![noblock_puzzle_17_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/0d765b84-e8d8-ec59-3b7f-a5066146066d.png)


![noblock_puzzle_17_6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/fb907264-9da7-6d71-b55f-d55fcf435be2.png)

![noblock_puzzle_17_7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/971b5ef8-1de7-a8c1-2bd9-6dd557635448.png)





    [[0, 0, 3, 3, 3, -1, 6, -1],
     [0, 0, 4, 3, 6, 6, 6, -1],
     [1, 1, 4, 4, 4, -1, -1, -1],
     [1, 1, 5, 5, 5, 5, 7, -1],
     [2, 2, 2, 2, 7, 7, 7, -1]]



ピースの形の選び方はランダムに決まるため、運が良ければ最後までたどり着いて完成しますが、普通は、途中で行き詰まって完成せずに終了します。

# 同じ形のピースの数には制限があります

さて、実際のパズルでは、同じ形のピースをいくつも選べたりはしません。同じ形のピースの数には制限があります。そこで、ピースの形を判定して、同じ形のピースの個数を数えながら、制限を超えない範囲でピースを選ぶようにしましょう。


```Python
def shape_key(piece):
    distances = []
    for i in range(len(piece)):
        xy1 = piece[i]
        for j in range(len(piece)):
            if i < j:
                xy2 = piece[j]
                distance = (xy1[0] - xy2[0])**2 + (xy1[1] - xy2[1])**2
                distances.append(distance)
    return "".join(str(sorted(distances)))
```

上記のコードで、同じ形のピースは同じ `key` が割り当てられるようにしました。こうすることで、問題としてはもっと難しくなってしまいました。

# レベル１「テトロミノ」に挑戦！

完成するまでひたすら試行錯誤を繰り返すコードは次のようになります。


```Python
x_length = 8
y_length = 5
piece_size = 4
same_piece_limit = 2
max_trial = 530000
best_score = x_length * y_length
best_matrix = generate(x_length, y_length)

for trial in range(max_trial):
    matrix = generate(x_length, y_length)
    count = {}
    piece_id = 0
    piece = get_new_piece(matrix, piece_size)
    key = shape_key(piece)
    count[key] = 1

    while len(piece) == piece_size:
        for x, y in piece:
            matrix[y][x] = piece_id
        
        piece = get_new_piece(matrix, piece_size)
        key = shape_key(piece)
        if key not in count.keys():
            count[key] = 0
        count[key] += 1
        if count[key] > same_piece_limit:
            break

        piece_id += 1

    score = sum([sum([1 if x == -1 else 0 for x in mat]) for mat in matrix])

    if best_score > score:
        best_score = score
        best_matrix = matrix

    if score == 0:
        print(trial, "th trial")
        break

depict(best_matrix)
best_matrix
```

    1133 th trial


![noblock_puzzle_23_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/e150597b-48d3-79c8-f080-33a93f8f332f.png)






    [[0, 0, 2, 6, 6, 6, 6, 8],
     [0, 2, 2, 3, 3, 7, 8, 8],
     [0, 2, 3, 3, 4, 7, 7, 8],
     [1, 1, 4, 4, 4, 7, 9, 9],
     [1, 1, 5, 5, 5, 5, 9, 9]]



最初に説明した[脳ブロック](https://bb.tenyo.co.jp/products/index.html)のうち、レベル１とされる「テトロミノ」は、これで解けるようになりました。ランダムにピースを選んでいくので、実行するたびに違う解が得られます。

# レベル２「ペントミノ」に挑戦！

同じコードで、レベル２とされる「ペントミノ」を解いてみましょう。与える変数を少し変えるだけで解けるはずです。


```Python
x_length = 10
y_length = 6
piece_size = 5
same_piece_limit = 1
max_trial = 530000
best_score = x_length * y_length
best_matrix = generate(x_length, y_length)

for trial in range(max_trial):
    matrix = generate(x_length, y_length)
    count = {}
    piece_id = 0
    piece = get_new_piece(matrix, piece_size)
    key = shape_key(piece)
    count[key] = 1

    while len(piece) == piece_size:
        for x, y in piece:
            matrix[y][x] = piece_id
        
        piece = get_new_piece(matrix, piece_size)
        key = shape_key(piece)
        if key not in count.keys():
            count[key] = 0
        count[key] += 1
        if count[key] > same_piece_limit:
            break

        piece_id += 1

    score = sum([sum([1 if x == -1 else 0 for x in mat]) for mat in matrix])

    if best_score > score:
        best_score = score
        best_matrix = matrix

    if score == 0:
        print(trial, "th trial")
        break

depict(best_matrix)
best_matrix
```

![noblock_puzzle_25_0.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/211162/eb3aa76f-7301-a450-ffb3-7136fe2a1812.png)





    [[0, 0, 0, 5, 5, 5, 5, 9, 9, -1],
     [0, 0, 3, 3, 3, 8, 5, -1, 9, 9],
     [1, 1, 3, 4, 3, 8, 8, -1, 9, -1],
     [2, 1, 4, 4, 4, 7, 8, 8, -1, -1],
     [2, 1, 1, 4, 7, 7, 7, 7, -1, -1],
     [2, 2, 2, 6, 6, 6, 6, 6, -1, -1]]



...と思ったら、なかなか解けませんね。私も何度も計算し直しましたが、レベル２のペントミノは組み合わせの数が多すぎて、このコードでは正解にたどり着けないようです。レベル２で、これか。おそるべし。

# boxing_puzzle

https://github.com/maskot1977/boxing_puzzle にて、pip install できるコードを公開しています。

# レベル２

続編記事として [何百～何千通りも答えのある箱詰めパズルを解く（レベル２：ペントミノ）](https://qiita.com/maskot1977/items/685c336b104a3ec12c2c) を書きましたので、合わせてお読みください。