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. image

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)

image

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)

image

c'est tout

Recommended Posts

Résolution de "cubes en cubes" avec optimisation des combinaisons
Optimisation du regroupement par combinaison
○○ Résolution de problèmes dans le département de mathématiques avec optimisation
Résolvez le problème des 4 couleurs grâce à l'optimisation des combinaisons
Déterminer le programme enregistré par optimisation de combinaison
Résolution de la théorie des jeux avec l'optimisation des combinaisons
Techniques d'optimisation combinées vues dans les puzzles
Divisez en équipes par optimisation de combinaison
Penser les menus par l'optimisation des combinaisons
Résolution des problèmes de planification des infirmières grâce à l'optimisation des combinaisons
Méthode gagnante des courses de chevaux par optimisation des combinaisons
Python en optimisation
Utiliser l'optimisation des combinaisons
Décidons le cours de date par optimisation de combinaison
Résolution des problèmes d'organisation des districts scolaires grâce à l'optimisation des combinaisons
Résolution du problème N Queen avec l'optimisation continue / combinée
Résolution du problème N Queen avec l'optimisation des combinaisons
Minimisez le nombre de polissages en optimisant la combinaison
Juger la finition du mahjong par l'optimisation des combinaisons
Diviser en équipes par optimisation de combinaison (minimiser l'écart moyen)
Diviser en équipes par optimisation de combinaison (méthode de cuisson)
Décidons la conférence de PyCon JP 2016 par optimisation de combinaison
Décidons la position du service d'incendie par optimisation combinée
Optimisation des performances dans Django 3.xx
Différences de prix par préfecture (2019)
Enquête Star avec optimisation des combinaisons
Jeux de regroupement avec optimisation des combinaisons
Optimisation combinée avec recuit quantique
Résoudre les problèmes d'optimisation avec Python
Générez 8 * 8 (64) cubes avec Blender Python
Trier par date en python
Résolution des problèmes de sac à dos avec les outils OR de Google - Pratiquer les bases des problèmes d'optimisation combinée