René DescartesDescartes 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

Sommaire

Règle du jeu (bulletin de l'APMEP no 327)
Solutions (bulletin de l'APMEP no 330)
Solution « à la main » (bulletin de l'APMEP no 331)
I.  Résultats et conditions préliminaires
II. Résolution du problème

III. Pour généraliser
Solution informatique
(bulletin de l'APMEP no 332)
IV. Démarche utilisée
V.  Résolution du problème
VI. Généralisation
VII. Des ouvertures pour aller plus loin

logo APM 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 :

Bleu

Rouge

Bleu

Rouge

Jaune

Blanc

Vert

Blanc

Vert

Bleu

Rouge

Jaune

Jaune

Blanc

Vert

Bleu

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).

Vert

Vert

Vert

Jaune

Jaune

Jaune

Blanc

Blanc

Bleu

Bleu

Bleu

Rouge

Rouge

Rouge

Blanc

Blanc

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 :

Bleu

Rouge

Bleu

Jaune

Jaune

Blanc

Vert

Blanc

Vert

Bleu

Rouge

Jaune

Jaune

Blanc

Vert

Bleu

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 no 327 de février 1981.

« Jeux et Maths »
Les tuiles voisines

in bulletin de l'APMEP no 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 :

B
W 11

R
V 8

B
W 10

R
V 5

J
B 15

W
R 9

V
J 4

W
R 7

V
J 16

B
W 13

R
V 6

J
B 2

J
B 14

W
R 12

V
J 3

B
W 1

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

Bleu

B

Blanc

W

Rouge

R

Jaune

J

Vert

V

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 :

16

12

15–7

11–2–4

14–6–8

5–3–10

5–13

9

W

B

J

V

R

W

B

J

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 :

bleu

rouge

jaune

blanc

vert

1

2

3

4

5

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 ».

1 2
3 4

2 1
4 5

1 2
5 4

3 4
5 1

4 5
1 2

5 4
2 3

5 1
3 4

1 2
4 5

2 3
5 1

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

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

in bulletins de l'APMEP no 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).

 

I

 
  
 

III

 
  
    

IV

II

    

V

VI

VIII

VII

    
    
    
    

Blocs « médians »

Blocs de « coin »

Bloc « central IX »

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 :

3

4

6

7

2

1

5

8

16

13

9

10

15

14

12

11

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

3

4

6

7

2

1

5

8

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

R1 α) à un bloc initial 

A B
C D

 correspondent au plus 24 états finaux.

β) 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.

B

B

C

D

Fig. 4

α) La première tuile posée sur le bloc de la figure 4, même si ce n'est pas la première du jeu, sera nécessairement un E (couleur manquante au bloc) ; donc 4 places possibles pour E ; 3 places possibles pour la nouvelle couleur manquante ; 2 places possibles pour la troisième couleur ; et une seule possibilité pour la dernière couleur. Certaines de ces possibilités seront bien sûr à éliminer, lorsque l'on tiendra compte, sur des critères établis plus loin, de l'ensemble du jeu.

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

R

V

W

J

 

B

J

V

R

W manque à l'état initial ; donc W est joué en 1er et cache R ; R est alors joué en 2e et cache J ; J est donc joué en 3e et cache V ; V est alors joué en 4e.

Fig. 5

 

R2 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 .

  B

 

X

 
 

X’

 

    B’

Fig. 6

Lorsque cette condition sera vérifiée, nous dirons que les ordres sur les blocs mitoyens sont « compatibles ». L'ordre partiel dans le bloc B de gauche entre X et X’ (fig. 6) doit être le même que dans le bloc B’ de droite. En fait, cette condition est aussi une condition suffisante.

Exemples d'utilisation de cette règle :

  B

A

B

A

D

C

E

    B

fig. 7

1) Supposons l'état initial de la figure 7.

D'après R1, le bloc B peut être recouvert par :

B E
C A

avec l'ordre des coups des couleurs finales :
E ; B ; A ; C.

 
B peut être recouvert par :

E D
A C

avec l'ordre D ; A ; C ; E.

 

On voit que pourtant que les six cases B B’ ne peut être recouvert par :

car il faut dans B jouer E avant A, et dans B’ jouer A avant E.

B E D
C A C

       B’

 

M

 
 

N

 

   B

ni

      B’

 

N

 
 

M

 

   B

2) Une application simple « à la main » est la suivante :

Si la couleur manquante à l'état initial est M dans B et N dans B’ (fig. 8), à l'état final, les deux cases communes ne pourront contenir la paire [M, N] puisque M manque dans B, elle est jouée en 1er, donc avant N dans B ; de même , puisque N manque dans B’, elle est jouée en 1er, donc avant M dans B’ ; ce qui est impossible.

Figure 8

 

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.

R3 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 :

B

R

B

R

J

W

V

W

V

B

R

J

J

W

V

B

État initial

1°) Liste des blocs superposables au bloc central.

2°) En tenant compte de R2, on élimine des blocs.

3°) On essaye de compléter le carré en tournant autour du bloc central en tenant compte au fur et à mesure des règles du jeu et de R ; de R2 ; de R3.

4°) Quand un carré complet est obtenu, on essaye de trouver l'ordre des coups qui y mène.

Étape no 1 : blocs superposables au bloc central

W

V

B

R

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

les flèches indiquent l'ordre des coups.

J

W

   

R

V

J

 

R

W

 

B

R

 

J

W

 

V

V

B

 

 

J

 

W

no 1

no 2

no 3

no 4

Tableau I

Étape no 2 : Première utilisation de R2

 

|

 

|

 

|

 

V

J

J

 

|

 

|

 

|

 

R

J

B

 

|

 

|

 

|

 

R

J

W

 

|

 

|

 

|

 

Figure 9

Dressons le tableau des couleurs manquantes, à l'état initial, dans chacun des neuf blocs de quatre cases. Chaque couleur est indiquée au centre du bloc dans lequel elle manque (fig. 9).

En utilisant le raisonnement expliqué dans le 2e exemple donné pour R2, on établit des incompatibilités (tableau Il).


       

R – V

J – B

  

B – W

    
 

V
|
J

  
   
 

R
|
J

J
|
W

 
   
    
 

R
|
J

J
|
B

 
  
    

R
|
J

signifie que dans les deux cases entourées, la paire [R, J] ne peut figurer (R et J étant les couleurs manquantes des 2 blocs contenant ces 2 cases).

Tableau II

  

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

Deuxième utilisation de R2(fig. 10)

   

J

R

 

W

B

 
   

fig. 10

Exemple : dans le bloc no 2 du tableau I, le B, qui est une couleur manquante de l'état initial du bloc II, devra être joué en 1er, donc avant R ; or, c'est contradictoire avec l'ordre indiqué sur le schéma. Donc, ce bloc no 2 ne convient pas.

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 no 3 : Exemple 1.Le bloc no 4 (fig. 11)

I

    
 

V

B

 
 

J

W

 
    

fig. 11

a) On complète le bloc I qui doit contenir un J (voir fig. 9). Deux places sont possibles :

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

 

J

  
 

V

B

 
 

J

W

 
    

premier cas

  

J

 
 

V

B

 
 

J

W

 
     

second cas

 

W

J

 
 

V

B

 
 

J

W

 
      

bloc II à compléter

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. no 4 α est donc éliminé.

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

 

W

J

 
 

V

B

 
 

J

W

V

    

no 4 α

 

W

J

 
 

V

B

V

 

J

W

 
    

no 4 β

 

W

J

 
 

V

B

V

 

J

W

R

     

coin impossible

figure 12

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

Exemple 2, le bloc no 3

R

 

J

W

 

V

I

    
 

R

J

 
 

W

V

 
     

On complète le bloc I : 1er coup J ; 2e coup V pour lequel il y a deux possibilités : 3a ou 3b.

Possibilité 3a

 

B

V

 
 

R

J

 
 

W

V

 
    

On termine le bloc I avec B et V.

 

B

V

 
 

R

J

B

 

W

V

 
     

On complète le bloc II. Il faut une tuile B. Deux choix possibles :

choix B en haut du bloc II

Ce carré figure au tableau II. Il est donc à éliminer.

Choix B en bas du bloc II

 

B

V

 
 

R

J

 
 

W

V

B

     
 

B

V

 
 

R

J

R

 

W

V

B

     
 

B

V

B

 

R

J

R

 

W

V

B

       

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

Possibilité 3b

 

V

W

 
 

R

J

 
 

W

V

 
    

On termine le bloc I avec V et W.

 

V

W

 
 

R

J

B

 

W

V

 
    

On complète le bloc II. Il faut une tuile B. Deux choix possibles :

choix B en haut du bloc II

Ce carré figure au tableau II. Il est donc à éliminer.

Choix B en bas du bloc II

 

V

W

 
 

R

J

 
 

W

V

B

    
 

V

W

 
 

R

J

R

 

W

V

B

    
 

V

W

V

 

R

J

R

 

W

V

B

    

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

 

V

W

V

 

R

J

R

 

W

V

B

 

J

  

On complète le bloc III. Il faut une tuile J. Deux choix possibles :

choix J à gauche du bloc III
Dans III : J < W < V
dans IX : V < W.

Ces ordres sont incompatibles.

Choix J à droite du bloc III

 

V

W

V

 

R

J

R

 

W

V

B

 

R

J

 
 

V

W

V

 

R

J

R

 

W

V

B

 

R

J

W

On complète le coin.

 

V

W

V

V

R

J

R

B

W

V

B

 

R

J

W

On complète le bloc IV. Deux choix possibles pour placer la tuile Verte :

placer la tuile V en haut du bloc est impossible, car d'après la règle du jeu on ne peut placer deux tuiles Vertes dans le bloc V.

Deuxième possibilité pour le bloc IV :

 

V

W

V

B

R

J

R

J

W

V

B

 

R

J

W

Dans ce bloc au 1er coup : R ; 2e coup : W ; 3e coup : B ; 4e coup : J qui termine le bloc IV.

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

W

V

W

V

B

R

J

R

J

W

V

B

W

R

J

W

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 no 4 : Rappels

B

R

B

R

J

W

V

W

V

B

R

J

J

W

V

B

W

V

W

V

B

R

J

R

J

W

V

B

B

R

J

W

3

4

6

7

2

1

5

8

16

13

9

10

15

14

12

11

État initial

État final

no des cases

Les ordres partiels sur les blocs
sont les suivants :

Bloc I

5 < 4 < 1 < 6

Bloc Il

10 < 5 < 9 < 8

Bloc III

12 < 9 < 14 < 13

Bloc IV

1 < 13 < 2 < 15

Bloc V

4 < 1 < 3 < 2

Bloc VI

5 < 7 < 8 < 6

Bloc VII

11 < 10 < 12 < 9

Bloc VIII

14 < 13 < 15 < 16

Bloc IX

5 < 9 < 1 < 13

  

 11 W

  
  

  
  

10 B

  
 

 

 
 

12 J

 

5 J

 
 

 

9 V

 

7 V

4 V

↑ ↑

 

14 R

8 R

 

1R

 

 

 

 6 W

 

↑ ↑

 

 

 
 

13 W

 

3 W

 

 

 

15 B

 

2 B

  

 

  
 

14 J

   

figure 13

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 no 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 no 1, puis cherche la case d'indice le plus faible pour jouer le 2e coup, puis le 3e ;

  • 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 no 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 R2 ;

  • 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 R3). On obtiendra donc, si elles existent, toutes les solutions (pour une même grille de départ) ;

  • l'utilisation de la règle R2 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 X1 et X2 sont les deux cases communes de B et de B’ ;

si n(X1) et n(X2) sont les numéros d'ordre de jeu sur X1 et X2 dans B ;

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

les ordres sur B et B’ sont compatibles si (n(X1) - n(X2)) (n’(X1) - n’(X2)) >0.

En schématisant, le programme contient :
  • une partie P1 permettant de fabriquer les 24 blocs centraux ;
  • un sous-programme P2 permettant de fabriquer un bloc médian ;
  • un sous-programme P3 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 :
  – P1
  – P2 pour le bloc I ;   P2 pour le bloc Il ; P3 pour le bloc VI
  – P2 pour le bloc III ; P3 pour le bloc VII
  – P2 pour le bloc IV ; P3 pour le bloc VIII
  – P3 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 no 327, et traitée « à la main » dans les Bulletins no 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.

BLEU
BLANC
9

ROUGE
VERT
4

BLEU
BLANC
11

ROUGE
VERT
5

JAUNE
BLEU
14

BLANC
ROUGE
8

VERT
JAUNE
3

BLANC
ROUGE
10

VERT
JAUNE
16

BLEU
BLANC
13

ROUGE
VERT
7

JAUNE
BLEU
2

JAUNE
BLEU
15

BLANC
ROUGE
12

VERT
JAUNE
6

BLEU
BLANC
1

BLEU
ROUGE
5

ROUGE
JAUNE
4

BLEU
ROUGE
6

ROUGE
JAUNE
1

JAUNE
VERT
3

BLANC
BLEU
10

VERT
BLANC
11

BLANC
BLEU
7

VERT
ROUGE
2

BLEU
JAUNE
9

ROUGE
VERT
14

JAUNE
ROUGE
15

JAUNE
VERT
8

BLANC
BLEU
12

VERT
BLANC
13

BLEU
JAUNE
16

BLEU
VERT
1

ROUGE
BLEU
3

BLEU
JAUNE
2

ROUGE
BLEU
4

JAUNE
BLANC
9

BLANC
ROUGE
8

VERT
BLANC
11

BLANC
ROUGE
10

VERT
JAUNE
14

BLEU
VERT
15

ROUGE
JAUNE
7

JAUNE
BLEU
6

JAUNE
ROUGE
13

BLANC
BLEU
16

VERT
ROUGE
12

BLEU
BLANC
5

BLEU
JAUNE
6

ROUGE
BLANC
10

BLEU
JAUNE
1

ROUGE
BLANC
3

JAUNE
VERT
5

BLANC
BLEU
9

VERT
ROUGE
13

BLANC
BLEU
2

VERT
ROUGE
4

BLEU
JAUNE
8

ROUGE
BLANC
12

JAUNE
VERT
15

JAUNE
VERT
7

BLANC
BLEU
11

VERT
ROUGE
14

BLEU
JAUNE
16

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 ?

R

V

R

V

B

W

B

W

R

V

R

V

B

W

B

W

Pour vérifier 1), nous avons utilisé le carré de la figure ci-contre, qui a la particularité de n'être composé que de 4 couleurs, et d'être, à une permutation circulaire près des couleurs, stable par le groupe les isométries du carré.

À 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 R2 :

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 R2) 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.

État initial

R

V

R

V

B

W

B

W

R

V

R

V

B

W

B

W

Couleurs manquantes

 

|

 

|

 

|

 

J

J

J

 

|

 

|

 

|

 

J

J

J

 

|

 

|

 

|

 

J

J

J

 

|

 

|

 

|

 

136 solutions

État initial

V

R

B

R

J

W

V

W

R

B

R

B

V

W

V

J

Couleurs manquantes

 

|

 

|

 

|

 

B

J

J

 

|

 

|

 

|

 

V

J

J

 

|

 

|

 

|

 

R

J

W

 

|

 

|

 

|

 

7 solutions

État initial

B

R

B

R

J

W

V

W

V

B

R

J

J

W

V

B

Couleurs manquantes

 

|

 

|

 

|

 

V

J

J

 

|

 

|

 

|

 

R

J

B

 

|

 

|

 

|

 

R

J

W

 

|

 

|

 

|

 

4 solutions

État initial

B

R

B

W

J

W

V

J

V

B

R

B

J

W

J

V

Couleurs manquantes

 

|

 

|

 

|

 

V

J

R

 

|

 

|

 

|

 

R

J

W

 

|

 

|

 

|

 

R

V

W

 

|

 

|

 

|

 

Aucune solution

Table des matières

Page mobile friendly Mobile friendly

Me contacter

Dans d'autres pages du site

Articles dans les bulletins APMEP

Bibliographie APMEP

 Statistique Orange persoe visite des pages « perso ».

Page no 22, créée le 31/8/2002