Résolution de "cubes en cubes" avec optimisation des combinaisons

Cube en cube

Résolvons Puzzle Collection n ° 12 "Cube in Cube".

Les 54 pièces en bois suivantes sont emballées étroitement dans un espace cubique de taille 6x6x6.

Résoudre avec Python

Liste des candidats

Au total, il y a 6 * 4 * 5 * 12 = 1440 candidats.

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)

Formuler et résoudre dans Définir le problème de division

python3

from pulp import *
from ortoolpy import addbinvars
cc = cands() #Tous les candidats
m = LpProblem() #Modèle mathématique
v = addbinvars(len(cc)) #Quel candidat choisir
for i,c in enumerate(cc.T):
    m += lpDot(c.tolist(), v) == 1
m.solve()

Affichage de la 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)

Une autre solution

Quand je l'ai recherché, il semble que je puisse le faire en deux étapes. Faisons le.

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)

c'est tout