Un article de Wikipedia.

Version du 24 mai 2008 à 11:11

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.

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

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

• Casse-tête des blocs dans la boîte Media:Cassetete_pas.PDB
• Source Cassetete.pas
• Visualiseurs VRML :
  • Divers visualiseurs http://cic.nist.gov/vrml/vbdetect.html
  • Un visualiseur gratuit pour Windows, Linux, Sun et Mac de chez Orbisnap : http://www.orbisnap.com/
    • Merci Orbisnap pour le visualiseur.