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

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

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

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

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

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

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

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

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()

図示します。

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

[[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 を置きましょう。

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

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

[[-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 の正方形を置きます。これだけではパズルのピースにはなりませんね。

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

[[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]]

ピースを置きます

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

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

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

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

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

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

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

[[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 のままになっているマスに、次々にピースを置いていきましょう。置けるところまで置いてみます。

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

[[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]]

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

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

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

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 が割り当てられるようにしました。こうすることで、問題としてはもっと難しくなってしまいました。

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

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

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

[[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]]

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

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

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

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

[[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 できるコードを公開しています。

レベル２

続編記事として 何百～何千通りも答えのある箱詰めパズルを解く（レベル２：ペントミノ） を書きましたので、合わせてお読みください。