前回は「何百～何千通りも答えのある箱詰めパズルを解く」ということで、レベル１のテトロミノを解くプログラムをPythonで実装しましたが、レベル２のペントミノを解くことはできませんでした。今回は、改めてペントミノに挑戦します！

私の自宅にあるのは、こういうやつです。

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

前回の復習も兼ねて

横 x 縦 y のケースを初期化するコードは次のようになります。前回は -1 で初期化しましたが、今回は事情があって（後ほど説明します）、 0 で初期化するように変更しました。

def generate(x, y): # 0 で初期化するよう変更
    return [[0 for _ in range(x)] for _ in range(y)]

同様に、新しいピースを得る次の関数でも、「ピースで埋められていないマス」を意味する -1 の部分を 0 に置き換えました。

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

    for x in range(x_length):
        for y in range(y_length):
            if matrix[y][x] == 0: ### 変更箇所
                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

同様に、隣接するマスを得る次の関数でも、「ピースで埋められていないマス」を意味する -1 の部分を 0 に置き換えました。

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] == 0: ### 変更箇所
                neighbors.append([x - dx, y - dy])

    return neighbors

パズルを図示する関数は、そのままです。

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

同一構造を判定する関数の改良

今回の重要な変更点は、ピースの同一構造を判定する次の関数です。

テトロミノは解けるのにペントミノはどうして解けないのかな〜〜〜？？

と思っていろいろ試行錯誤していましたが、改良前のこの関数ではテトロミノのピースが全て区別できるのに対し、ペントミノのピースの中に区別できないものがあるということが分かりました。

そりゃペントミノ解けんわな...

ということで、改良済みの関数はこちらです。

def shape_key(piece):
    distances = []
    adjacents = {} ### 今回新たに加えた特徴量
    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)

                ### 以下、今回新たに加えた特徴量
                if distance == 1:
                    if i not in adjacents.keys():
                        adjacents[i] = []
                    adjacents[i].append(j)
                    if j not in adjacents.keys():
                        adjacents[j] = []
                    adjacents[j].append(i)

    #return "".join(str(sorted(distances))) 前回の返り値

    ### 今回の返り値
    return (
        "".join(str(sorted(distances))) + "_" 
        + "".join(str(sorted([len(adjacents[k]) for k in adjacents.keys()]))))

テトロミノ（レベル１）を解きます

ペントミノ（レベル２）を解く前に、テトロミノ（レベル１）が解けることを確認します。変更箇所がもう１つあることに注意。ランダムに試行錯誤を繰り返すので、実行するたびに出力結果は変わります。

import random
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 = 1 ### 変更箇所
    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 n == 0 else 0 for n in mat]) for mat in matrix])

    if best_score >= score:
        best_score = score
        best_matrix = matrix
        #depict(best_matrix)

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

depict(best_matrix)
best_matrix

71 th trial

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

ペントミノ（レベル２）を解きます

変数の値を変更すれば、ペントミノ（レベル２）を解けるはずです。やってみましょう。

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 = 1 ###
    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 n == 0 else 0 for n in mat]) for mat in matrix])

    if best_score >= score:
        best_score = score
        best_matrix = matrix
        #depict(best_matrix)

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

depict(best_matrix)
best_matrix

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

うーむ、、、ペントミノ（レベル２）のピースは全て区別できるようになったはずだけど、530000回繰り返してもまだ解けないとは...。ほっほっほ、初めてですよ...ここまで私をコケにしたおバカさん達は…

探索方法を変更

上記の方法では、ランダムな探索を繰り返していました。このため、同じ場所の探索を何度も繰り返している可能性があります。

そこで、次のような改良を加えることで、いくつか無駄な探索を減らす努力をしてみました。

グラフ理論でいう「順位優先探索」を行なうことで、同じ場所の探索を二度と繰り返さないようにした。
グラフ理論でいう「連結成分」という概念を用いて、ピースに埋められていないマスの連結成分が２つ以上になるピースの置き方をした時は、それ以上の探索を打ち切ることにした。
これまでに置いたピースの集合と、ピースを置いていないマスの境界線を「表面」とし、新しく置くピースがその表面と大きく接するとき、そのピースを優先するようにした。
全ピースの半分だけケースに収める計算ならすぐできるので、半分だけ収める計算を行い、その「半分だけ解いたパズル」の組み合わせの中から条件を満たす組み合わせを発見する方針に変更した。

次に置けるピースを全列挙する

次に置けるピースを全列挙する関数がこちらになります。これを用いて順位優先探索することになります。

import copy

def get_new_pieces(matrix):
    piece = []

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

    result_pieces = []
    waiting = []
    waiting.append(piece)
    while len(waiting) > 0:
        piece = waiting.pop()
        neighbors = get_rand_neighbor(piece, matrix)
        for x, y in neighbors:
            if [x, y] not in piece:
                new_piece = copy.deepcopy(piece)
                new_piece.append([x, y])
                if len(new_piece) == piece_size:
                    new_piece = sorted(new_piece)
                    if new_piece not in result_pieces:
                        result_pieces.append(new_piece)
                else:
                    waiting.append(new_piece)

    return sorted(result_pieces)

ピースを置いてない場所の連結成分

ピースに埋められていないマスの連結成分を得る関数はこちらです。

def get_connected_subgraphs(matrix):
    neigh = {}
    for y in range(len(matrix)):
        for x in range(len(matrix[y])):
            if matrix[y][x] == 0:
                neigh[",".join([str(x), str(y)])] = []
                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] == 0:
                        neigh[",".join([str(x), str(y)])].append([x - dx, y - dy])

    connected_subgraphs = []
    found = []
    for k, v in neigh.items():
        if k in found:
            continue
        connected_subgraph = [k]
        waiting = list(v)
        found.append(k)
        while len(waiting):
            x, y = waiting.pop()
            n = ",".join([str(x), str(y)])
            if n in found:
                continue
            connected_subgraph.append(n)
            found.append(n)
            if n in neigh.keys():
                waiting += neigh[n]
        connected_subgraphs.append(connected_subgraph)

    return connected_subgraphs

「表面」の大きさを決める関数

新しいピースを置いた時、既存のピースの集合と接する「表面」の大きさを interface とし、これを順位優先探索に用いることにしました。（surface も計算しますが、これは結局使いません）

def get_face(piece, matrix): 
    interface = 0
    surface = 0
    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] == 0:
                surface += 1
            else:
                interface += 1
    return interface, surface

半分だけパズルを解く

今回の探索方針変更の大きなところです。全ピースを最後までケースに置こうとする方針では、テトロミノ（レベル１）は解けますがペントミノ（レベル２）は解けませんでした。そこで、最後まで埋めようとせず、全ピースの半分だけケースに置くことを繰り返し、その「半分だけ解いたパズル」を組み合わせて、いい組み合わせを探すことをします。

そのうち「半分だけ解いたパズル」を作る関数がこちらです。

また、基本的には「順位優先探索」ですが、ある低い確率で順位をランダムにする処理を加えています。

import random
def half_puzzle(x_length, y_length, piece_size, same_piece_limit):
    best_score = x_length * y_length
    best_matrix = generate(x_length, y_length)
    n_depict = 0
    n_pieces = int(x_length * y_length / piece_size)
    waiting = []
    piece_id = 1
    matrix = generate(x_length, y_length)
    for new_piece in get_new_pieces(matrix):
        pieces2count = {}
        key = shape_key(new_piece)
        pieces2count[key] = 1
        new_matrix = copy.deepcopy(matrix)
        for x, y in new_piece:
            new_matrix[y][x] = piece_id
        pieces = [new_piece]
        waiting.append([0, piece_id + 1, pieces, new_matrix, pieces2count])

    trial = 0
    random.shuffle(waiting)
    while len(waiting) > 0:
        trial += 1
        if trial > 530000:
            break

        delta, piece_id, pieces, matrix, pieces2count = waiting.pop()
        score = sum([sum([1 if x == 0 else 0 for x in mat]) for mat in matrix])
        if len(get_connected_subgraphs(matrix)) > 1:
            continue

        if best_score >= score:
            best_score = score
            best_matrix = matrix

        if score == (x_length * y_length) / 2:
            yield(best_matrix)
            continue

        new_pieces = get_new_pieces(matrix)
        for new_piece in new_pieces:
            new_pieces2count = copy.deepcopy(pieces2count)
            key = shape_key(new_piece)
            if key not in new_pieces2count.keys():
                new_pieces2count[key] = 0
            new_pieces2count[key] += 1
            if new_pieces2count[key] > same_piece_limit:
                continue

            new_pieces = copy.deepcopy(pieces)
            new_pieces.append(new_piece)
            new_matrix = copy.deepcopy(matrix)
            for x, y in new_piece:
                new_matrix[y][x] = piece_id

            face = get_face(new_piece, matrix)

            if len(get_connected_subgraphs(matrix)) > 1:
                continue
            waiting.append([face[0], piece_id + 1, new_pieces, new_matrix, new_pieces2count])

        if random.random() < 0.05:
            random.shuffle(waiting)
        elif random.random() < 0.95:
            waiting = sorted(waiting)            
    return matrix

同じ形のピースが指定個数以下かどうか確認する

同じ形のピースが指定個数以下かどうか確認する関数です。同じ目的のために作ったディクショナリーとして pieces2count を前回使ったので、無駄といえば無駄かもしれません。改良の余地があるところです。

今回この関数を作った理由は、「半分だけ収める計算を行い、その組み合わせの中から条件を満たす組み合わせを発見する方針」に変更したため、半分解いた答えを２つガッチンコした combined_matrix に対して同じ形のピースが指定個数以下かどうか確認したかったからです。

def same_piece_within_limit(matrix, same_piece_limit):
    id2piece = {}
    for y in range(len(matrix)):
        for x in range(len(matrix[y])):
            if matrix[y][x] not in id2piece.keys():
                id2piece[matrix[y][x]] = []
            id2piece[matrix[y][x]].append([x, y])

    key2count = {}
    for id, piece in id2piece.items():
        key = shape_key(piece)
        if key not in key2count.keys():
            key2count[key] = 0
        key2count[key] += 1
        if key2count[key] > same_piece_limit:
            return False

    return True

テトロミノ（レベル１）を解きます

以上の関数を用意したら、テトロミノ（レベル１）が解けるか確認です。

-1 ではなく 0 で初期化するように変更しましたが、それは half_puzzle から出てきた「半分だけ解いたパズル」を組み合わせたとき、ぴったりハマったかどうか判定するときに生きてきます。

実行するたびに違う答えが出てくるはずです。

x_length, y_length, piece_size, same_piece_limit = 8, 5, 4, 2

index = 0
matrix_history = []
keta = int(x_length * y_length / piece_size)
for matrix in half_puzzle(x_length, y_length, piece_size, same_piece_limit):
    for prev_matrix in matrix_history:
        matrix3 = np.flipud(np.fliplr(np.array(matrix)))

        if (prev_matrix + matrix3).min().min() > 0:
            matrix3 += keta
            matrix3 = np.where(matrix3 == keta, 0, matrix3)
            combined_matrix = prev_matrix + matrix3
            if same_piece_within_limit(combined_matrix, same_piece_limit):
                depict(combined_matrix)
                index += 1

    matrix_history.append(matrix)
    if index > 5:
        break

ペントミノ（レベル２）を解きます。

いよいよ、ペントミノ（レベル２）に挑戦です！

様々な計算効率化を実装したので、今度こそ！

x_length, y_length, piece_size, same_piece_limit = 10, 6, 5, 1

index = 0
matrix_history = []
keta = int(x_length * y_length / piece_size)
for matrix in half_puzzle(x_length, y_length, piece_size, same_piece_limit):
    for prev_matrix in matrix_history:
        matrix3 = np.flipud(np.fliplr(np.array(matrix)))

        if (prev_matrix + matrix3).min().min() > 0:
            matrix3 += keta
            matrix3 = np.where(matrix3 == keta, 0, matrix3)
            combined_matrix = prev_matrix + matrix3
            if same_piece_within_limit(combined_matrix, same_piece_limit):
                depict(combined_matrix)
                index += 1

    matrix_history.append(matrix)
    if index > 5:
        break