Casse-tête des blocs dans la boîte

Un article de Wikipedia.

Sommaire

Casse-tête des blocs dans la boîte

But

Résoudre le casse-tête consistant à mettre entièrement dans un boîte un ensemble de blocs.

Introduction

Le casse-tête consiste à placer dans une boîte de 5 x 5 x 5 un ensemble de 17 blocs.

L'ensemble des 17 blocs est constitué de :

  • 5 cubes de 1 x 1 x 1 (référencé par 1),
  • 6 blocs de 1 x 2 x 4 (référencé par 8),
  • 6 blocs de 2 x 2 x 3 (référencé par 12).

Le volume occupé par les blocs est de 5 x (1 x 1 x 1) + 6 x (1 x 2 x 4) + 6 x (2 x 2 x 3) = 5 x (1) + 6 x (8) + 6 x (12) = 5 + 72 + 48 = 125 et correspond à celui de la boîte (5 x 5 x 5) = 125.

Résultats

La méthode employée pour résoudre ce casse-tête consiste à essayer toutes les possibilités.

L'implémentation utilise les API Palm PalmAPI.pas, la librairie PPlib.pas, la librairie générant des menus Menu.pas ainsi que la base de données CPDBSTD4PP.pas.

La base de données se nomme 'CasseteteCPDB'.


Comme il y a 3 types de blocs (1,8 et 12) et que le logiciel doit successivement définir tous ces types, il y a alors 6 ordres différents pour les définir.

Résultats de la résolution du casse-tête
Ordre Nombre d'opérations Durée des calculs (HH:MM:SS)
(1,8,12) 4'977'945 28:31
(1,12,8) 6'339'911 36:32
(8,1,12) 3'723'323 20:15
(8,12,1) 3'011'511 16:08
(12,1,8) 12'992'565 1:13:49
(12,8,1) 7'022'173 inconnu

Le résultat du dernier ordre (12,8,1) est partiellement connu à cause de la limitation du nombre d'entrée de la base de données (voir Base de données CPDB). La durée des calculs dans ce cas est estimée à 40 minutes par interpolation linéaire (1:13:49 x 7'022'173 / 12'992'565 = 39:53).

Solution

Le résultat est afficher en spécifiant le type de bloc [1,2,4] orienté selon le système d'axes xyz et sa position (1,3,1) dans le même système d'axes.

La solution obtenue pour l'ordre des pièces (8,12,1) (le plus rapide à résoudre) est la suivante : 

    Solution
    --------
    Piece : [1,2,4] en (1,1,1)
    Piece : [2,2,3] en (2,1,1)
    Piece : [2,4,1] en (4,1,1)
    Piece : [3,2,2] en (1,3,1)
    Piece : [4,1,2] en (1,5,1)
    Piece : [1,1,1] en (5,5,1)
    Piece : [2,3,2] en (4,1,2)
    Piece : [1,1,1] en (4,4,2)
    Piece : [1,2,4] en (5,4,2)
    Piece : [2,3,2] en (1,3,3)
    Piece : [1,1,1] en (3,3,3)
    Piece : [2,2,3] en (3,4,3)
    Piece : [4,1,2] en (2,1,4)
    Piece : [1,1,1] en (2,2,4)
    Piece : [3,2,2] en (3,2,4)
    Piece : [1,1,1] en (1,1,5)
    Piece : [2,4,1] en (1,2,5)
    Nombre operations : 3011511
    Duree operations  :0:16:8

Une vue en VRML de la solution : Media:Boite.wrl. Il faut installer l'un des visualiseurs donnés dans les Ressources

Une animation en VRML de la solution Media:Boite2.wrl. Après 10 secondes, les blocs sont placés dans la boîte.

Conclusions

  • En disposant les blocs selon la solution, il s'avère que la disposition des blocs par face est similaire, à l'orientation prêt.
  • Les 5 cubes forment une diagonale de la boîte.
  • Les deux indications précédentes permettent de recréer la solution sans disposer d'une solution écrite.

Ressources

Récupérée de « http://zigloo.ch/index.php/Casse-t%C3%AAte_des_blocs_dans_la_bo%C3%AEte »