cube de Conway

Imaginez une boîte cubique dont chaque arête mesure cinq petites unités. Il faut y faire entrer 18 blocs rectangulaires, sans trou ni chevauchement. On peut tourner chaque bloc, mais ni le déformer ni le découper.

Le volume total est exactement le bon : les pièces occupent ensemble 125 petits cubes, autant que la boîte. Cela ne donne pourtant pas la solution. Les blocs longs, larges ou épais ne se placent pas n'importe où ; une orientation choisie trop tôt peut laisser un vide qu'aucune pièce restante ne peut remplir.

Le cube de Conway est un problème de pavage d'une boîte cubique 5 × 5 × 5 par 18 pavés droits à dimensions entières. Les pièces sont treize pavés 1 × 2 × 4, un cube 2 × 2 × 2, un pavé 1 × 2 × 2 et trois baguettes 1 × 1 × 3. Une dimension égale à 1 représente l'arête d'un petit cube unité. L'ordre des trois dimensions ne fixe pas une orientation : un pavé 1 × 2 × 4 peut être tourné dans la boîte.

Dans la modélisation discrète employée ici, chaque pièce reste parallèle aux trois directions de la boîte. Une solution place toutes les pièces entièrement à l'intérieur, sans recouvrement de leurs intérieurs et sans volume vide. La somme des volumes vaut bien celui de la boîte : Cette égalité est nécessaire, mais elle ne prouve pas qu'un pavage existe : les formes et les orientations doivent aussi être compatibles localement.

Le mot « cube » désigne donc à la fois la boîte finale et, par usage, le casse-tête complet. Les pièces, elles, ne sont pas toutes cubiques : la majorité sont des pavés allongés.

La boîte cible comporte cinq unités dans chacune des trois directions, soit 125 cellules unitaires. Les treize pavés 1 × 2 × 4 forment l'essentiel du volume : chacun couvre huit cellules et l'ensemble en couvre 104. Le cube 2 × 2 × 2 apporte huit cellules, le pavé 1 × 2 × 2 en apporte quatre et les trois baguettes 1 × 1 × 3 en apportent neuf.

La figure d'inventaire représente un exemplaire de chaque forme et indique sa multiplicité ; elle ne donne pas un assemblage solution. Les dimensions des pièces déterminent leurs orientations possibles. Leur multiplicité détermine ensuite combien de fois chaque empreinte doit apparaître. Ensemble, dimensions et multiplicité suffisent à définir le problème de placement, indépendamment de la couleur, du matériau ou de l'échelle physique du jeu.

Avant de chercher un arrangement, vérifions que l'inventaire peut au moins remplir la boîte. Les données sont les dimensions 5 × 5 × 5 de la boîte et les quatre types de pièces, avec leurs multiplicités 13, 1, 1 et 3.

1. La boîte contient 5 × 5 × 5 = 125 cellules unitaires.
2. Les treize grands pavés occupent 13 × 8 = 104 cellules.
3. Les trois autres types occupent respectivement 8, 4 et 3 × 3 = 9 cellules.
4. Le total des pièces est donc 104 + 8 + 4 + 9 = 125 cellules.

Le contrôle consiste à soustraire : 125 − 125 = 0. Il n'y a ni volume manquant ni volume excédentaire. Le test éliminerait immédiatement un inventaire incorrect, mais son résultat nul ne construit pas le cube : il faut encore trouver des positions sans recouvrement qui occupent chaque cellule.

Avec un jeu matériel, on commence par compter les quatre types de pièces et contrôler leur volume total. Ce contrôle est préférable à un essai immédiat lorsqu'une pièce peut manquer ou avoir été intervertie avec une autre.

Pendant la recherche, on observe les vides produits après chaque placement. Un espace résiduel dont la largeur ou la profondeur est incompatible avec toutes les pièces restantes signale qu'il vaut mieux revenir au dernier choix plutôt que poursuivre au hasard.

Pour une étude systématique, on peut numéroter les 125 cellules et enregistrer quelles cellules chaque orientation occupe. Cette représentation discrète est préférable au seul dessin lorsque l'objectif est d'énumérer les placements ou d'automatiser une recherche avec retour sur trace.

Cube de Conway et polycube. Un polycube est une forme constituée de cubes unitaires assemblés face contre face. Le cube de Conway est un problème complet de pavage, avec une boîte 5 × 5 × 5 et un inventaire imposé de 18 pièces. Une pièce seule peut être décrite comme un polycube sans être le puzzle entier.

Pavage et empilement libre. Un pavage doit couvrir exactement la boîte, sans trou ni recouvrement. Un empilement peut être stable tout en laissant des espaces vides ; le bilan de volume ou l'observation d'une cellule inoccupée tranche entre les deux situations.

Cube géométrique et puzzle portant un nom. Un cube ordinaire est défini par ses six faces carrées. Le cube de Conway est un problème particulier, défini aussi par une boîte de côté 5 et par la liste imposée de ses pièces.

Le bon volume ne suffit pas. Le total 125 est seulement une condition nécessaire. Le symptôme du piège est un raisonnement qui conclut à l'existence d'un assemblage dès que les volumes coïncident. Il faut encore exhiber un placement complet ou établir son existence par une recherche exhaustive correcte.

Tourner n'est pas déformer. Dans la modélisation sur cellules adoptée ici, une rotation échange les directions occupées par les longueurs 1, 2 et 4, mais conserve ces trois dimensions. Si un bloc semble entrer seulement après raccourcissement, flexion ou passage à travers une autre pièce, le placement n'est pas admissible.

Une vue en perspective peut masquer une collision. Deux pièces dessinées peuvent sembler disjointes alors qu'elles occupent une même cellule en profondeur. Pour contrôler un candidat, il faut examiner les cinq couches de 5 × 5 cellules, puis vérifier que chacune des 125 cellules est occupée exactement une fois.

Les symétries créent des descriptions redondantes. Deux assemblages obtenus l'un de l'autre par rotation ou réflexion de la boîte peuvent être comptés comme identiques ou distincts selon la convention choisie. Toute énumération de solutions doit annoncer cette convention avant de donner un nombre.

Le cube de Conway conduit naturellement au problème de couverture exacte : chaque placement possible d'une pièce représente un ensemble de cellules, et une solution choisit des placements qui couvrent chaque cellule une seule fois. Cette formulation relie le casse-tête à la combinatoire et aux algorithmes de recherche avec retour sur trace.

Une étude plus avancée peut aussi comparer les solutions en tenant compte des symétries de la boîte. Il faut alors décider si deux placements transformés par une rotation ou une réflexion constituent la même solution, puis appliquer cette convention à toute l'énumération.