Descartes et les Mathématiques

Le jeu des « tuiles voisines »

Bulletin de l'APMEP : résolution d'un casse-tête mathématique à l'aide d'un ordinateur

Personne, actuellement, ne nie l'importance qu'ont pris les jeux dans notre société ; et, nous le savons, les professeurs de mathématiques ne sont pas les derniers à s'y intéresser. De plus, les jeux leur fournissent des sujets d'étude motivants, variés et d'un genre sans cesse renouvelé. C'est ce que nous essayons de faire, entre autres, à travers cette rubrique, en proposant des jeux originaux, parfois même inédits. Avons-nous atteint notre but ? L'absence de critique pourrait nous le faire croire ! Aussi n'hésitez pas à nous faire part de vos remarques, de vos souhaits.

Le jeu des « Tuiles Voisines* » que nous présentons maintenant nous a été transmis par Francis GUTMACHER de Paris. Ce jeu, qui nous paraît très original, est plus complexe qu'il ne semble au premier abord. De plus, il semble que ce jeu puisse être traité sur ordinateur. À vous de nous donner la réponse.

Bibliographie : Games and Puzzles for addicts. Roger MILLINGTON. Robbs 1979.

Remarque : Ce texte utilise des flèches obliques trouvées dans les caractères spéciaux de la police « Wingdings »

Le Jeu des « Tuiles Voisines »

Présentation : Le matériel comprend :

figure 1

  • un plateau de jeu sur lequel est dessinée une grille carrée (4 × 4). Chacune des seize cases porte une couleur parmi cinq. La répartition et la disposition des couleurs sont indiquées sur la figure 1.

  • seize pions (ou tuiles) de l'une des cinq couleurs précédentes. La figure 2 donne le nombre de tuiles de chaque couleur. On peut bien sûr remplacer, sur la grille et sur les tuiles, les couleurs par d'autres symboles (dessins, lettres, nombres).

figure 2

But du jeu : ce jeu solitaire consiste à recouvrir totalement la grille de départ à l'aide des seize tuiles selon les règles qui suivent.

Règles du jeu :

figure 3

  • Une tuile ne peut pas être placée sur une case de sa couleur.
(Une tuile rouge ne pourra donc pas être placée dans le coin supérieur droit de la grille).

  • Une tuile ne peut pas être adjacente (par un côté ou un sommet) à une case de sa couleur.
(Si le coup initial est joué sur la case du coin supérieur droit, les tuiles rouges, bleues, vertes et blanches sont interdites ; seule une tuile jaune peut être placée).

  • Une fois qu'une tuile est placée sur une case, la couleur de la case devient celle de la tuile.
(Ainsi, si une tuile jaune a été placée dans le coin supérieur droit, le deuxième coup ne peut être joué sur la case bleue qui lui est adjacente, car seule la couleur jaune pouvait y être placée ; elle devient interdite à cause du premier coup, et la couleur rouge y reste interdite à cause de la deuxième case rouge) (figure 3).

Remarques : Il est important de marquer l'ordre dans lequel les tuiles ont été placées, car la disposition finale, si réussite il y a, ne donne aucun renseignement sur la manière d'y parvenir. Si on joue avec du papier et un crayon, il n'y a aucun problème. Si on veut s'en dispenser, on peut utiliser des pions de loto numérotés de 1 à 15 que l'on place sur les tuiles au fur et à mesure qu'elles sont placées. Ce problème, paraît-il, est possible ; mais nous aimerions bien pouvoir publier dans cette rubrique au moins une solution.

Problèmes ouverts

La répartition des couleurs dans le jeu proposé est la suivante :

  • sur la grille, 4 cases bleues et 3 cases de chacune des autres couleurs ;

  • sur les tuiles, 4 tuiles blanches, et 3 tuiles de chacune des autres couleurs.

1°) Avec la même répartition, existe-t-il d'autres dispositions des couleurs sur la grille de départ permettant une réussite du jeu ?

2°) Avec la même répartition, existe-t-il des dispositions des couleurs rendant impossible la réussite du jeu ?

3°) Avec la même répartition et la même disposition des couleurs sur la grille de départ, une autre répartition des couleurs sur les tuiles permet-elle encore une réussite du jeu ?

4°) Les problèmes précédents peuvent-ils être résolus sur ordinateur ?

Jeu proposé par Jean FROMENTIN dans le bulletin de l'APMEP n^o 327 de février 1981.

« Jeux et Maths »
Les tuiles voisines

in bulletin de l'APMEP n^o 330 de septembre 1981

Toutes les solutions qui nous ont été transmises aboutissent à la même disposition finale des tuiles. Voici par exemple la solution qui nous a été envoyée par Joseph Bartoli, de Martigues :

Pour chaque case, la première ligne indique la couleur initiale de la case, la deuxième ligne indique la couleur qui y a été placée, et le numéro en coin indique l'ordre de placement de la tuile.

Il est bien évident que cet ordre de placement n'est pas unique. En numérotant les cases de 1 à 16 comme sur la figure ci-dessus, Michèle Cumaura, de Tours, montre comment on peut permuter l'ordre de placement des tuiles d'une même couleur :

ce qui donne déjà 2×6×6×6×2 ordres différents.

Dans le même ordre d'idées, Jacques Levéque, d'Angers, fait remarquer « que lorsque deux actions se déroulent successivement en des cases non voisines, l'ordre de ces actions peut être interverti ; ce qui peut être schématisé de la façon suivante en encadrant les éléments qui peuvent permuter entre eux : 16–12 ; 7–15 ; 11–2 ;6–4–14 ; 10–1 ; 13–5–8 ; 9–3 ».

Il fait remarquer que d'autres regroupements de cases non voisines sont possibles et arrive ainsi à un minimum de 792 ordres de placement. Ce sont les même s remarques qu'ont fait Alain Laurenson, de Bar Le Duc, et Dominique Desnoyer, d'Argenton sur Creuse.

Toutes les réponses signalent que la solution est obtenue par permutation des couleurs : B → W → R → V → J.

Mais laissons à un élève de cinquième le soin d'exprimer, à sa manière, comment il est arrivé à une telle constatation (texte transmis par René Bois, d'Orsay) :

"1°) Sur le jeu il y a quatre cases bleues ; j'ai pensé que les quatre pions blancs devaient se poser sur elles, puisque c'étaient les deux seules couleurs qui pouvaient se marier.

2°) En fonction du dessin à réaliser, et du règlement à respecter, j'ai calculé toutes les combinaisons possibles, afin de reproduire une nouvelle figure, tout à fait conforme au règlement.

3°) Le dessin réalisé, je constate que chaque couleur se superpose sur une seule couleur (ex : tous les verts se posent sur les rouges ; tous les jaunes se posent sur les verts, etc.)".

Georges Borion, de Poitiers, montre que c'est la seule permutation possible, pour la grille donnée et avec la répartition des couleurs sur les tuiles indiquées. Gérard Joly, de Phalsbourg et Henri Lemercier de l'IREM de Paris-Nord, font remarquer que les couleurs Rouge, Vert et Jaune ont des rôles semblables, et donc qu'en permutant deux de ces trois couleurs sur la grille initiale on obtient une solution en effectuant la même permutation au niveau des tuiles ; ceci donne donc cinq autres grilles admettant une solution par permutation des couleurs.

Jacques Levéque, d'Angers, qui a traité le problème sur micro-ordinateur, a codé les couleurs par des nombres de la manière suivante :

Il remarque que : « la surface du jeu à un moment quelconque est constituée de 9 carrés ayant à leurs sommets quatre numéros différents ».

Pour placer une tuile, il faut donc le faire dans au moins un de ces neuf carrés. Appelons X le numéro de l'échiquier qui est recouvert et Y le numéro de la tuile que l'on place.

A, B, C, X, Y sont cinq numéros différents, on petit donc déduire la valeur de Y du carré où on le place :

Y = 15 - (A + B + C + X).

C'est ainsi que sont partis Françoise et Patrice Debart, de Caen, pour traiter complètement « à la main » et « sur ordinateur » ce problème. Ils montrent qu'avec la répartition des couleurs sur les tuiles, proposée dans le Bulletin de février, la grille de départ n'admet qu'une disposition finale des tuiles, obtenue par permutation des couleurs. Ils montrent de plus qu'il n'y a que trois autres répartitions des couleurs sur les tuiles qui donnent une solution à la même grille de départ, l'une de ces solutions étant obtenue par permutation des couleurs. Nous verrons tout ceci en détail dans la prochaine rubrique.

Le Jeu des « Tuiles Voisines »

par Françoise et Patrice Debart

in bulletins de l'APMEP n^o 331 / 332 ; déc. 1981 / fév. 1982

Essayer d'étudier le problème en jouant au coup par coup, suivant les règles, conduit vite à un arbre des possibilités énorme, même , comme on le verra plus tard, pour un ordinateur. De plus, la disposition finale des tuiles peut être obtenue de bien des manières. Nous avons donc retenu la démarche suivante :

  • Montrer que si l'état final du carré est connu, il est possible de retrouver le(s) « chemin(s) » qui y mène(nt).

  • Chercher des critères permettant de proposer des états finaux possibles.

  • Simplifier l'étude en basant l'essentiel des résultats sur l'analyse des blocs carrés de 4 cases, inclus dans le carré de 4 × 4.

I. Résultats et conditions préliminaires

1) Notations :

  • les couleurs seront repérées par : W (White = blanc) ; V ; R ; B (Bleu) ; J ; en cas de généralisation par : A ; B ; C ; D ; E ;

  • les blocs : dans le carré 4 ×4, on peut repérer 9 blocs de 4 cases disposées en carré (fig. 1).

figure 1

Deux blocs ayant 2 cases communes (ex. : I et V) seront dits « mitoyens ».

  • les cases sont numérotées de 1 à 16, suivant le schéma de la figure 2. Bien que peu naturelle à première vue, cette numérotation a été retenue, car elle facilite le traitement informatique :

Figure 2

  • les cases du bloc IX sont du type i + 4k, avec k∈[0 ; 1 ; 2 ; 3]

  • les cases des blocs médians sont du type j ; j + 3 ; j + 4 ; j + 5 ;

  • les cases des blocs de coin sont du type j ; j + 1 ; j + 2 ; j + 3 avec k ∈ [1 ; 5 ; 9 ; 13], c'est-à-dire l'ensemble des numéros des cases centrales.

  • Carré. Ce terme sera toujours utilisé pour désigner l'ensemble des 16 cases.

bloc I

Figure 3

  • ordre des coups : lorsque nous parlerons d'ordre des coups sur un bloc, il s'agira d'un ordre partiel par rapport à l'ensemble du jeu ; par exemple, si la solution est obtenue en jouant dans l'ordre les cases 1 ; 8 ; 4 ; 3 ; 6 ; 2 ; 5 (fig. 3), nous dirons que sur le bloc I nous avons l'ordre 1 ; 4 ; 6 ; 5 noté : 1 < 4 < 6 < 5.

2) Résultats et conditions

β) Si l'état initial et l'état final du bloc sont connus, on peut retrouver l'ordre dans lequel les coups ont été joués sur ce bloc.

γ) Donnons simplement un exemple : supposons la situation de la fig. 5.

R₂ Condition nécessaire : pour qu'un carré initial puisse être solution, il faut que dans toute paire de blocs mitoyens, l'ordre partiel induit sur les cases communes par l'ordre sur chacun des blocs soit le même .

Exemples d'utilisation de cette règle :

II. Résolution du problème

Nous donnons un exemple de recherche « à la main » proche de la démarche informatique, pour essayer de mieux faire comprendre celle-ci au lecteur. Nous préciserons plus tard quelles seront les différences. Sans ordinateur, il est bon d'être quelque peu avare de son travail, et nous rajoutons donc un résultat complémentaire, permettant de tenir compte des répartitions des couleurs imposées à l'état final, ce dont on peut, pour généraliser, s'affranchir.

R₃ si une couleur doit figurer 4 fois à l'état final, elle doit figurer une fois et une seule dans chacun des blocs de coin.

Si une couleur doit figurer 3 fois à l'état final, elle manque dans un bloc de coin et un seul.

Compte tenu des règles du jeu, une couleur ne peut figurer qu'une fois par bloc. Les blocs de coin formant une partition du carré, la conclusion est évidente.

Plan du travail :

Le tableau I présente 4 des 24 blocs possibles ;

les flèches indiquent l'ordre des coups.

Tableau I

Étape n^o 2 : Première utilisation de R₂

Ce tableau permet d'éliminer 8 des 24 blocs du tableau I ; par exemple le bloc n^o 1 qui contient dans la colonne de gauche les couleurs [R, J].

Deuxième utilisation de R₂(fig. 10)

Avec un raisonnement analogue, on élimine 3 blocs supplémentaires. Il en reste donc 13 à étudier ; il serait fastidieux de les citer tous. Nous donnerons donc seulement deux exemples un bloc à éliminer, et celui qui mène à la solution.

Étape n^o 3 : Exemple 1.Le bloc n^o 4 (fig. 11)

Le premier cas figure au tableau II ; il est donc impossible. Complétons le bloc I dans le second cas, en utilisant R₁ :

b) On complète le bloc II. Le premier coup est B, le deuxième coup est donc V pour lequel il y a deux possibilités (fig. 12). Pour terminer II dans le cas α, il faut un J, ce qui est impossible. n^o 4 α est donc éliminé.

Dans le cas β, il faut un R ; on obtient :

figure 12

c) On complète le coin. D'après R₁, on doit mettre R ; mais alors le bloc de coin ne contient pas W, ce qui contredit R₃. Le bloc n^o 4 est donc à éliminer.

Exemple 2, le bloc n^o 3

Possibilité 3a

Choix B en bas du bloc II

On termine le bloc II puis le bloc VI de coin : d'après R₃ il faut un W dans ce bloc de coin. C'est donc impossible.

Possibilité 3b

Choix B en bas du bloc II

On termine le bloc II puis le bloc VI de coin.

Choix J à droite du bloc III

Deuxième possibilité pour le bloc IV :

Enfin, on termine les deux coins ce qui nous donne une solution :

Les 11 autres blocs centraux conduisent tous à des impossibilités (si on tient compte bien sûr de la répartition des couleurs sur les tuiles).

Étape n^o 4 : Rappels

On peut résumer ces 9 ordres par le schéma de l'arbre de la figure 13 : on doit mettre un W sur la case 11, puis mettre un B sur la case 10, puis… etc.

Pour certains cas, on ne possède aucun renseignement. Par exemple, 12 doit être joué avant 9 ; 5 aussi ; mais 12 peut indifféremment être joué avant ou après 5.

On peut vérifier que tout jeu respectant cet arbre convient.

Exemple : 11 ; 10 ; 12 ; 5 ; 9 ; 7 ; 4 ; 14 ; 8 ; 1 ; 6 ; 13 ; 3 ; 15 ; 2 ; 16.

III. Pour généraliser

On peut se demander si, avec d'autres répartitions des couleurs sur les tuiles, on peut trouver d'autres répartitions finales, et donc d'autres solutions ; si d'autres configurations initiales permettent de trouver 0, 1 ou plusieurs solutions. C'est lé que l'informatique entre en jeu !…

Bulletin de l'APMEP n^o 332 - février 1982

JEUX ET MATHS

Après la résolution du jeu des Tuiles « é la main » voici une résolution « informatique » qui, comme il se devait, permet de généraliser le problème et de traiter tous les cas voulus.

Il est intéressant de constater que même dans le traitement informatique, un balayage systématique de toutes les possibilités ne mène à rien, sauf si on a le temps ; mais le temps d'utilisation d'ordinateur est cher ! et une bonne réflexion au départ est loin d'être négligeable. Françoise et Patrice Debart en ont fait l'expérience à propos de ce jeu. Ceux qui veulent de plus amples renseignements sur leur recherche peuvent leur écrire directement à P. Debart .

Le jeu des « Tuiles Voisines » (suite)

par Françoise et Patrice Debart

IV. Démarche utilisée

Un premier essai sur Honeywell Bull 61 DPS Basic a été fait en simulant la technique du jeu les cases sont numérotées de 1 à 16, les couleurs de 1 à 5 ;

  • l'ordinateur essaie la couleur de valeur la plus faible possible sur la case n^o 1, puis cherche la case d'indice le plus faible pour jouer le 2^e coup, puis le 3^e ;

  • en cas d'impossibilité, retour à l'embranchement précédent en dernier ressort, on modifie la case de départ, etc.

Très vite, il faut abandonner cette piste victime de « l'explosion combinatoire » : en 3 heures d'ordinateur, et en limitant l'édition au minimum, seuls les jeux dont la case de départ est la case 3 ont été explorés (sans succès, mais c'est normal).
Or il y a 16 cases départ et on voudrait traiter d'autres carrés. Le moral n'y est plus ! Ce programme a mis 15 jours à tourner, et la solution a été trouvée « à la main » 8 jours plus tôt.

Le deuxième essai reprend les résultats de la démarche manuelle en les systématisant (voir le Bulletin n^o 331).

Comme dans l'exemple traité « à la main » :

  • on commence par écrire les blocs superposables au bloc central ;

  • en élimine, en tenant compte une première fois de la règle R₂ ;

  • on essaie de compléter le jeu en tournant autour du bloc central.

Ce qui a été modifié :

  • on ne tient pas compte du nombre de tuiles disponibles dans chaque couleur (règle R₃). On obtiendra donc, si elles existent, toutes les solutions (pour une même grille de départ) ;

  • l'utilisation de la règle R₂ dans le remplissage des blocs médians : les diverses situations pour les ordres compatibles dans le bloc central et dans un bloc médian ont été analysées et fournies à l'ordinateur (il y en a 24) ; ce qui permet d'emblée de ne fabriquer que des blocs médians compatibles avec le bloc central ;

  • la compatibilité entre les ordres de jeu sur les deux cases communes d'un bloc médian et d'un bloc de coin est testée par :

si X₁ et X₂ sont les deux cases communes de B et de B’ ;

si n(X₁) et n(X₂) sont les numéros d'ordre de jeu sur X₁ et X₂ dans B ;

si n’(X₁) et n’(X₂) sont les numéros d'ordre de jeu sur X₁ et X₂ dans B’ ;

les ordres sur B et B’ sont compatibles si (n(X₁) - n(X₂)) (n’(X₁) - n’(X₂)) >0.

En schématisant, le programme contient :
  • une partie P₁ permettant de fabriquer les 24 blocs centraux ;
  • un sous-programme P₂ permettant de fabriquer un bloc médian ;
  • un sous-programme P₃ permettant de compléter un bloc de coin compatible avec les blocs médians mitoyens ;
  • les instructions nécessaires aux retours en arrière et bouclages.

Dans le meilleur des cas, on aura donc la séquence suivante :
  – P₁
  – P₂ pour le bloc I ;   P₂ pour le bloc Il ; P₃ pour le bloc VI
  – P₂ pour le bloc III ; P₃ pour le bloc VII
  – P₂ pour le bloc IV ; P₃ pour le bloc VIII
  – P₃ pour le bloc V.

Remarquons enfin que :
  • pour compléter un bloc médian, il y a tantôt deux possibilités, tantôt une (pour que les ordres soient compatibles) ; deux possibilités quand les deux cases communes se succèdent immédiatement dans le bloc central (donc aussi dans le bloc médian) ; une possibilité dans les autres cas ;
  • pour compléter un bloc de coin, il y a au plus une solution.

Donc, l'étude d'un carré revient à étudier au maximum :

                (24) × (2× 2×2×2)
(bloc central) × (blocs médians)

soit 384 cas, mais beaucoup moins en pratique, puisque la plupart s’arrêtent en cours de route.

L'étude d'un carré prend 5 à 15 minutes.

V. Résolution du problème

Pour la grille proposée dans le Bulletin n^o 327, et traitée « à la main » dans les Bulletins n^o 330 et 331, nous avons sorti 4 solutions dont une seule avait, comme celle trouvée « à la main », la répartition (des couleurs sur les tuiles) souhaitée.

"À la main", la recherche d'un ordre total compatible avec les ordres partiels demandait une quinzaine de minutes. Un programme a donc été rédigé, qui peut sortir à la fois la solution et un ordre de jeu.

Il est à remarquer que seulement deux répartitions des couleurs sur les tuiles donnent une solution par permutation des couleurs (la première et la quatrième).

VI. Généralisation

Pour généraliser, on est amené à se poser la question de la validité du programme fabriqué. Rappelons qu'un ordinateur ne peut prouver une impossibilité ; ne pas trouver de solution, en soi, ne démontre pas qu'il n'y en a pas !

1) Le programme tourne-t-il bien ? (n'oublie-t-il pas de cas ?)

2) Les résultats obtenus comme carrés finaux sont-ils effectivement solutions ? Si un ordre total compatible avec les ordres partiels est sorti, est-il effectivement jouable ?

À l'évidence, un tel carré a au minimum 24 solutions : les carrés composés de 4 blocs V, VI, VII, VIII identiques, superposables au bloc V initial.

La vérification ne fut pas superflue ; un indice mal placé ne permettait pas de les trouver toutes. Après une mise au point finale, 136 solutions ont été trouvées (54 pages de listing). Dans la liste des solutions, et pour chacun des 9 blocs, on trouve un exemplaire des 24 blocs qui lui sont superposables, ce qui prouve que l'ordinateur passe bien par toutes les éventualités de l'analyse initiale.

Pour répondre à la question 2), nous sommes amenés à établir la réciproque de la règle R₂ :

Si un carré final où tous les ordres sur les blocs mitoyens sont compatibles est trouvé, alors ce carré est solution.
C'est-à-dire : il existe un ordre total sur l'ensemble des 16 cases compatible avec les 9 ordres partiels et cet ordre est un ordre de jeu.

La démonstration faite est assez technique, et il serait fastidieux de la citer ici. Mais peut-être en existe-t-il une très simple ?

VII. Des ouvertures pour aller plus loin

Un troisième programme permettant de fabriquer des carrés initiaux a été conçu. Mais même en tenant compte des permutations circulaires des couleurs, des rotations et symétries du carré de base, il faudrait, compte tenu du nombre de cas possibles, une bonne semaine d'ordinateur pour tout sortir, et probablement un autre programme pour l'exploitation.

Nous avons étudié ainsi 75 carrés de base ; le nombre de solutions varie de 0 à 136.

En cherchant des « trucs » pour accélérer et généraliser, nous avons essayé les 56 blocs 3 x 3 possibles (aux symétries et permutations des couleurs prés) ; ils sont tous jouables.

Enfin, il semble bien que les couleurs manquantes dans les blocs du carré initial soient déterminantes pour le nombre de solutions.
Précisons que si, dans deux blocs mitoyens initiaux, on a vu des couleurs manquantes différentes, cela permet d'éliminer (voir la règle R₂) des configurations finales. Si, par contre, les couleurs manquantes sont les mêmes, nous avons retenu moins de conditions.

En d'autres termes, intuitivement, plus le tableau de couleurs manquantes contient de « différences » d'une case à la voisine, moins il y aura de solutions.

C'est d'ailleurs ainsi que nous avons eu l'idée de fabriquer le carré qui a 136 solutions, où les couleurs manquantes des 9 blocs sont les même s. Dans tous les essais effectués, cette hypothèse se vérifie le nombre de solutions croît avec le nombre de couleurs manquantes (de blocs mitoyens) identiques. Mais nous n'avons pas réussi à formaliser ce critère, ni à établir de formule permettant de prévoir le nombre de solutions.

136 solutions

7 solutions

4 solutions

Aucune solution