Résolution d'un cube énigme en bois, la suite
Publié le
Dans l'article précédent, je donnais la résolution de cube énigme en bois. Cette solution, après des mois à essayer, je l'ai trouvée grâce à un petit programme.
En effet, à force de manipuler l'objet, j'ai acquis une bonne représentation mentale de son fonctionnement et des manipulations possibles. À partir de là, et parce que je suis informaticien, j'ai commencé à réfléchir à comment résoudre le cube via un programme.
Avant hier, j'ai eu un petit peu de temps à consacrer au sujet, et j'ai donc écrit rapidement un programme qui m'a permis de reconstruire le cube avec succès.
Je publie le code de ce petit script Python ici. Le principe est simple : à partir d'une description de la structure du cube, le programme fait une recherche en profondeur en utilisant les manipulations possibles et en vérifiant à chaque étape que les contraintes sont respectées.
Les contraintes étant que le cube en entier fait une taille de 3 par 3 par 3 « petits cubes » et que, bien entendu, deux cubes ne peuvent pas être au même emplacement.
# La structure du cube.
# Un F représente un cube « fixe », c'est-à-dire qui transmet sa direction au suivant.
# Un J représente un « joint », c'est-à-dire un qui cube qui permet de pivoter la direction.
cube_chain = "FFJJJFJJFJJJFJFJJJJFJFJFJFF"
def get_possible_directions(direction):
""" En fonction de la direction du cube, indique quels sont les directions
possibles du joint. """
if direction == 'N' or direction == 'S':
return ['E', 'W', 'U', 'D']
if direction == 'E' or direction == 'W':
return ['N', 'S', 'U', 'D']
if direction == 'U' or direction == 'D':
return ['E', 'W', 'N', 'S']
raise Exception("Invalid direction")
def get_position(position, direction):
""" À partir d'une position d'un cube et la direction du cube suivant, renvoie les coordonnées
du cube suivant. """
if direction == 'N':
return position[0], position[1] + 1, position[2]
if direction == 'S':
return position[0], position[1] - 1, position[2]
if direction == 'E':
return position[0] + 1, position[1], position[2]
if direction == 'W':
return position[0] - 1, position[1], position[2]
if direction == 'U':
return position[0], position[1], position[2] + 1
if direction == 'D':
return position[0], position[1], position[2] - 1
raise Exception("Invalid direction")
def is_structure_valid(positions):
""" Vérifie les contraintes du cube. """
# Le cube tient dans un espace de 3 x 3 x 3
x_values = [position[0] for position in positions]
y_values = [position[1] for position in positions]
z_values = [position[2] for position in positions]
x_span = max(x_values) - min(x_values)
y_span = max(y_values) - min(y_values)
z_span = max(z_values) - min(z_values)
in_a_cube = x_span < 3 and y_span < 3 and z_span < 3
if not in_a_cube:
return False
# Il n'y a pas deux cubes au même endroit
unique_positions = set(positions)
return len(unique_positions) == len(positions)
def place_next_cube(cubes, current_direction, positions):
""" Fonction récursive principale de la recherche.
- 'cubes' représente les cubes qu'il reste à placer
- 'current_direction' représente la direction actuel de l'axe du cube
- 'positions' est la liste des coordonnées de cubes déjà placés.
"""
if len(cubes) == 0:
# S'il n'y a plus de cube à placer, on a trouvé la solution.
return True
# Place tout d'abord le cube suivant selon la direction indiquée.
new_position = get_position(positions[-1], current_direction)
positions.append(new_position)
# Si la structure n'est pas valide, enlève le cube et indique que la recherche ici s'arrête.
if not is_structure_valid(positions):
positions.pop()
return False
# pour un cube fixe, appelle récursivement la fonction en gardant la même direction.
# En cas de retour de fonction qui indique que la branche n'est pas valide, retire le cube.
if cubes[0] == 'F':
valid = place_next_cube(cubes[1:], current_direction, positions)
if not valid:
positions.pop()
return valid
# pour un cube de type join, appelle récursivement la fonction pour chacune
# des directions possibles du pivot.
# Si aucune des directions n'est valide, retire le cube.
if cubes[0] == 'J':
possible_directions = get_possible_directions(current_direction)
for direction in possible_directions:
if place_next_cube(cubes[1:], direction, positions):
return True
positions.pop()
return False
# État initial. Le premier cube est en 0,0,0 et le suivant est vers le Nord.
# Cet état est arbitraire, il est possible de change les coordonnées et la direction initiale.
all_positions = [(0, 0, 0)]
# Affiche la solution trouvée
print(place_next_cube(cube_chain[1:], 'N', all_positions))
print(all_positions)
print(len(all_positions))