箱詰めパズル ― 12種類のペントミノを詰める#
この章で学ぶこと#
12種類のペントミノを、決まった形の箱にすき間なく詰めます。CP-SAT を使うと、必要な制約は add_exactly_one() だけで解けます。
12種類のペントミノを文字の2次元配列で表す
回転・反転したときの「置ける場所」をすべて列挙する
「各ピースは1か所」「各マスは1ピース」の2種類の
exactly_oneで解く
from ortools.sat.python import cp_model
import numpy as np
from matplotlib import pyplot as plt
from matplotlib.cm import tab20
from matplotlib.collections import PatchCollection
12種類のペントミノ#
ペントミノは、正方形を5つ辺でつないだ形（位数5のポリオミノ）です。回転や裏返しで同じになるものをまとめると、ちょうど12種類になります。
* がブロック、空白が何もない場所です。
pentominos = dict(
F=[" **",
"** ",
" * "],
P=["***",
"** "],
I=["*****"],
N=["** ",
" ***"],
L=["****",
" *"],
T=["***",
" * ",
" * "],
U=["* *",
"***"],
V=["* ",
"* ",
"***"],
W=["* ",
"** ",
" **"],
X=[" * ",
"***",
" * "],
Y=[" * ",
"****"],
Z=["** ",
" * ",
" **"],
)
def as_array(block):
"""文字のリストを、NumPy の2次元配列にする"""
return np.array([list(row) for row in block])
def plot_pentominos(pentominos):
"""12種類を並べて描く"""
fig, ax = plt.subplots()
ax.set_aspect('equal')
rectangles = []
for i, (name, block) in enumerate(pentominos.items()):
r, c = np.where(block == '*')
dx, dy = i % 4 * 6, i // 4 * 4
for x, y in zip(c + dx, r + dy):
rectangles.append(plt.Rectangle((x, y), 1, 1, facecolor=tab20.colors[i],
edgecolor="white"))
collection = PatchCollection(rectangles, match_original=True)
ax.add_collection(collection)
ax.autoscale_view()
ax.axis('off')
pentominos_arr = {key: as_array(val) for key, val in pentominos.items()}
plot_pentominos(pentominos_arr)
pentominos_arr['W'] は、* と空白からなる2次元配列です。
pentominos_arr['W']
array([['*', ' ', ' '],
['*', '*', ' '],
[' ', '*', '*']], dtype='<U1')
箱（ボード）#
箱も2次元配列で表します。1 はピースを置けるマス、0 は最初から空いているマスです。
12個のペントミノは 12 × 5 = 60 マスなので、箱の面積も 60 マスになるようにします。
board1 = np.ones((8, 8), dtype=np.uint8) # 64 - 4 = 60 マス（中央が空いている）
board1[3:5, 3:5] = 0
board2 = np.ones((3, 20), dtype=np.uint8)
board3 = np.ones((4, 15), dtype=np.uint8)
board4 = np.ones((5, 12), dtype=np.uint8)
board5 = np.ones((6, 10), dtype=np.uint8)
boards = [board1, board2, board3, board4, board5]
print(board1)
[[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 0 1 1 1]
[1 1 1 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]]
置ける場所を列挙する#
ピースは回転4通り × 左右反転2通り = 8通りの向きを取れます。それぞれを箱のすべての位置に置いてみて、置ける場所を集めます。
pentomino[:, ::step]…step=-1で左右反転np.rot90(tile, r)… 90°回転をr回置いたマスがすべて
1なら配置可能（箱からはみ出すとIndexErrorになるので、その場合は飛ばす）
同じ形が重複して出てくるので、set に入れてから sorted() でリストにします。
from itertools import product
from collections import defaultdict, namedtuple
Location = namedtuple('Location', 'pentomino cells')
def get_all_locations(pentominos, board):
"""12種類のピースが置ける場所を、すべて列挙する"""
ymax, xmax = board.shape
locations = set()
for i, pentomino in enumerate(pentominos):
for step in (1, -1): # 左右反転
flipped = pentomino[:, ::step]
for r in range(4): # 90°回転 × 4
tile = np.rot90(flipped, r)
locy, locx = np.where(tile == "*")
for y, x in product(range(ymax), range(xmax)):
locy2 = locy + y
locx2 = locx + x
try:
if np.all(board[locy2, locx2] == 1):
cells = tuple(sorted(zip(locy2.tolist(), locx2.tolist())))
locations.add(Location(i, cells))
except IndexError:
pass # 箱からはみ出した
return sorted(locations)
locations = get_all_locations(pentominos_arr.values(), boards[0])
print(len(locations), "通りの置き方")
for loc in locations[:5]:
print(loc)
1568 通りの置き方
Location(pentomino=0, cells=((0, 0), (0, 1), (1, 1), (1, 2), (2, 1)))
Location(pentomino=0, cells=((0, 0), (1, 0), (1, 1), (1, 2), (2, 1)))
Location(pentomino=0, cells=((0, 1), (0, 2), (1, 0), (1, 1), (2, 1)))
Location(pentomino=0, cells=((0, 1), (0, 2), (1, 2), (1, 3), (2, 2)))
Location(pentomino=0, cells=((0, 1), (1, 0), (1, 1), (1, 2), (2, 0)))
解く#
locations の各要素にブール変数 flag を1つずつ作り、True ならその場所に置くことにします。
制約は add_exactly_one() だけで、次の2種類です。
各ピースにつき1か所 … 同じピースを2か所に置かない
各マスにつき1ピース … 1つのマスを2つのピースで埋めない（＝すべてのマスが埋まる）
pentomino_locations は「ピース → その置ける場所の番号」、cell_locations は「マス → そのマスを含む置き方の番号」の辞書です。
def solve_board(board):
"""箱を12個のペントミノで詰める"""
locations = get_all_locations(pentominos_arr.values(), board)
pentomino_locations = defaultdict(list) # ピース → 置ける場所の番号
cell_locations = defaultdict(list) # マス → そのマスを含む置き方の番号
for idx, (tile_id, cells) in enumerate(locations):
pentomino_locations[tile_id].append(idx)
for cell in cells:
cell_locations[cell].append(idx)
model = cp_model.CpModel()
flags = np.array([model.new_bool_var(f"b{i}") for i in range(len(locations))])
# 各ピースは1か所、各マスは1ピース
for d in (pentomino_locations, cell_locations):
for index in d.values():
model.add_exactly_one(flags[index].tolist())
solver = cp_model.CpSolver()
if solver.solve(model) not in (cp_model.OPTIMAL, cp_model.FEASIBLE):
raise ValueError("解が見つかりませんでした")
return [locations[i].cells for i, flag in enumerate(flags) if solver.value(flag)]
def plot_solution(solution):
"""解いた配置を描く"""
h, w = np.array(solution).reshape(-1, 2).max(axis=0) + 1
fig, ax = plt.subplots(figsize=(w * 0.25, h * 0.25))
ax.set_aspect('equal')
rectangles = []
for i, block in enumerate(solution):
for y, x in block:
rectangles.append(plt.Rectangle((x, y), 1, 1, facecolor=tab20.colors[i],
edgecolor='white'))
collection = PatchCollection(rectangles, match_original=True)
ax.add_collection(collection)
ax.autoscale_view()
ax.invert_yaxis()
ax.axis('off')
return fig
5種類の箱を、順番に解いて描きます。
for board in boards:
solution = solve_board(board)
plot_solution(solution)
検算#
解いた配置が本当に条件を満たしているか、確かめます。
def check_solution(board, solution):
"""各ピースが5マスで、重なりもすき間もないか"""
filled = {}
for i, block in enumerate(solution):
if len(block) != 5:
return False, "マスが5つでないピースがあります"
for y, x in block:
if (y, x) in filled:
return False, f"マス {(y, x)} が重なっています"
filled[y, x] = i
target = {(y, x) for y, x in zip(*np.where(board == 1))}
if set(filled) != target:
return False, "埋まっていないマスがあります"
return True, f"{len(solution)} ピースで全部埋まりました"
for board in boards:
print(check_solution(board, solve_board(board)))
(True, '12 ピースで全部埋まりました')
(True, '12 ピースで全部埋まりました')
(True, '12 ピースで全部埋まりました')
(True, '12 ピースで全部埋まりました')
(True, '12 ピースで全部埋まりました')
まとめ#
ペントミノの配置は「置ける場所の列挙」と「
add_exactly_oneによる選択」だけで解ける回転と反転は
np.rot90()とpentomino[:, ::-1]で作る（8通り）重複した置き方は
setでまとめてからリストにする制約は2種類だけ。ピース側とマス側の両方に
exactly_oneを置くと、すき間も重なりもなくなる