Solving "cubes in cubes" by combinatorial optimization

Cube in cube

Let's solve Puzzle Collection No. 12 "Cube in Cube".

The 54 following wooden parts are packed tightly into a 6x6x6 cubic space. image

Solve with Python

List of candidates

In total, there are 6 * 4 * 5 * 12 = 1440 candidates.

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)

Formulate and solve the partition of a set problem

python3


from pulp import *
from ortoolpy import addbinvars
cc = cands() #All candidates
m = LpProblem() #Mathematical model
v = addbinvars(len(cc)) #Which candidate to choose
for i,c in enumerate(cc.T):
    m += lpDot(c.tolist(), v) == 1
m.solve()

Display of solution

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)

image

Another solution

When I looked it up, it seems that I can do it in two steps. let's do it.

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)

image

that's all

Recommended Posts

Solving "cubes in cubes" by combinatorial optimization
Grouping by combinatorial optimization
○○ Solving problems in the Department of Mathematics by optimization
Solving 4-color problems with combinatorial optimization
Determine recorded programs by combinatorial optimization
Solving game theory with combinatorial optimization
Combinatorial optimization techniques seen in puzzles
Divide into teams by combinatorial optimization
Think about menus by combinatorial optimization
Solving nurse scheduling problems with combinatorial optimization
Horse racing winning method by combinatorial optimization
Python in optimization
Use combinatorial optimization
Let's decide the date course by combinatorial optimization
Solving school district organization problems with combinatorial optimization
Solving the N Queen problem with combinatorial optimization
Solving the N Queens problem with combinatorial optimization
Minimize the number of polishings by combinatorial optimization
Judging the finish of mahjong by combinatorial optimization
Divide into teams by combinatorial optimization (minimize average deviation)
Divide into teams by combinatorial optimization (simulated annealing method)
Let's decide the lecture of PyCon JP 2016 by combinatorial optimization
Let's decide the position of the fire station by combinatorial optimization
Performance optimization in Django 3.xx
Differences in prices by prefecture (2019)
Combinatorial optimization to investigate stars
Grouping games with combinatorial optimization
Combinatorial optimization with quantum annealing
Solve optimization problems in Python
Generate 8 * 8 (64) cubes in Blender Python
Sort by date in python
Solving Knapsack Problems with Google's OR-Tools-Practicing the Basics of Combinatorial Optimization Problems