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

Un article de Wikipedia.

(Différences entre les versions)
(Résultats)
(Résultats)
Ligne 29 : Ligne 29 :
| (8,1,12) || 3'723'323 || 20:15
| (8,1,12) || 3'723'323 || 20:15
|- align="center"
|- align="center"
-
| (8,12,1) || 12'992'565 || 1:13:49
+
| (8,12,1) || 3'011'511 || 16:08
|- align="center"
|- align="center"
-
| (12,1,8) || 3'011'511 || 16:08
+
| (12,1,8) || 12'992'565 || 1:13:49
|- align="center"
|- align="center"
| (12,8,1) || 7'022'173 || inconnu
| (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#Conclusions|Base de données CPDB]]). La durée des calculs est estimée à plus de 36 minutes et moins d'une heure.
+
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#Conclusions|Base de données CPDB]]). La durée des calculs dans ce cas est estimée à plus de 36 minutes et moins d'une heure.
 +
 
 +
=== 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.
 +
 
 +
 
 +
<pre>
 +
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
 +
</pre>
== Conclusions ==
== Conclusions ==

Version du 22 mars 2008 à 10:07

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.

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 à plus de 36 minutes et moins d'une heure.

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.


    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

Conclusions

Ressources