キューブの中のキューブ
パズルコレクション12号「キューブの中のキューブ」を解いてみます。
54個の下記の木の部品を、6×6×6のサイズの立方体の空間にすきまなく詰めます。
Pythonで解く
候補の列挙
全部で、6*4*5*12=1440 候補になります。
python3
import numpy as np
from itertools import cycle, product
from more_itertools import take
def rotx(a):
n, b = a.shape[0], np.zeros(a.shape)
for i,j,k in product(range(n),range(n),range(n)):
b[i,j,k] = a[i,n-1-k,j]
return b
def roty(a):
n, b = a.shape[0], np.zeros(a.shape)
for i,j,k in product(range(n),range(n),range(n)):
b[i,j,k] = a[n-1-k,j,i]
return b
def rotz(a):
n, b = a.shape[0], np.zeros(a.shape)
for i,j,k in product(range(n),range(n),range(n)):
b[i,j,k] = a[n-1-j,i,k]
return b
def cands():
cc = []
for i,j,k in product(range(6),range(4),range(5)):
a = np.zeros((6,6,6))
a[i,j,k]=a[i,j+1,k]=a[i,j+1,k+1]=a[i,j+2,k]=1
for f in take(12, cycle([rotx, roty, rotz])):
cc.append(a.flatten())
a = f(a)
return np.array(cc, dtype=int)
集合分割問題に定式化して解く
python3
from pulp import *
from ortoolpy import addbinvars
cc = cands() # 全候補
m = LpProblem() # 数理モデル
v = addbinvars(len(cc)) # どの候補を選ぶか
for i,c in enumerate(cc.T):
m += lpDot(c.tolist(), v) == 1
m.solve()
解の表示
python3
%matplotlib inline
import matplotlib.pyplot as plt
from matplotlib.colors import hex2color, CSS4_COLORS
plt.rcParams['figure.figsize'] = 12, 8
cols = list(CSS4_COLORS.values())
def show(v, n=6):
r = np.zeros((6,6,6), dtype=int)
j = 0
for i, x in enumerate(v):
if value(x):
j += 1
r += cc[i].reshape((6,6,6))*j
for k in range(n):
plt.subplot((n+2)//3,3,k+1)
plt.imshow([[hex2color(cols[i]) for i in j] for j in r[k]])
show(v)
別解
調べてみると、2段ずつできるみたいです。やってみましょう。
python3
m = LpProblem()
v = addbinvars(len(cc))
for i,c in enumerate(cc.T):
m += lpDot(c.tolist(), v) == (1 if i < 72 else 0)
m.solve()
show(v, 2)
以上