Petit jeujeu mathématique deviendra gros casse-tête

Eh bien, la réponse à la question du post précédent est: c'est pas si compliqué que ça... En revanche, ça va être l'occasion de montrer de quelle créativité est capable un solveur, tout mécanique et stupide qu'il est.

La grille "chirac" comportant 36 cases, le score optimal théorique devrait être de 27 cases jaunes, soit neuf coups gagnants (2 cases sacrifiées au début, un heptagone sacrifié à la fin, ça nous fait 36 - 2 - 7 = 27 = 9 x 3). Mais l'absence de pentagone, facile à constater, indique que ce score ne pourra pas être atteint. Il va donc falloir réduire nos ambitions à huit coups gagnants, soit 3 x 8 = 24 cases, avec non plus 2 + 7 cases sacrifiées, mais bien 2 + 10: à la fin de la partie, c'est à priori dix cases qu'il faut sacrifier.

Y a-t-il un décagone sur la figure? Non (les décagones sont rarissimes). Il va donc falloir trouver autre chose.

Voici la solution que j'ai trouvée moi avec mon petit cerveau; comme souvent, c'est une des moins bien cachées: on peut dessiner le long du côté supérieur une enfilade (un couloir) de dix triangles, et la prendre en un seul coup final. Ce qui nous donne par exemple la séquence de coups: 6 32 25 26 30 28 15 23 9 18 11.

Cette solution trouvée par un humain est parfaitement valide, elle mène au score optimal et il n'y a rien à lui reprocher. Mais le solveur a d'autres idées.

On  peut remplacer ce couloir rectiligne et inélégant par un joli couloir biscornu: 6 22 35 28 8 2 31 4 11 15 25.

Au lieu de prendre dix cases en un coup final, on peut en prendre six, puis quatre, ou le contraire: 3 20 32 10 1 24 34 27 23 0 18 6.

Ou encore, et c'est à mon sens le plus ingénieux, on peut repérer deux hexagones mariés (ayant donc deux cases en commun) et les prendre en un seul coup final, ce qui a presque l'aspect d'une résolution "classique": 14 12 6 8 16 26 27 28 32 24 2.

Le solveur, lui, n'est pas soucieux d'élégance et peut aussi trouver des solutions bizarres, hétérodoxes et néanmoins valides: sacrifier deux cases à l'avant-dernier coup avant de prendre un couloir de huit cases en enfilade: 34 22 21 28 7 32 3 30 8 12 19 10.

Bref, ce solveur, tout crétin et mécanique qu'il est, peut se transformer en un très bon professeur, très ingénieux.

Essayez de reconstituer tous seuls une de ces solutions, si vous êtes cap'.

Je propose la séquence : 10, 12 (2 bleus), 16, 4, 2, 33, 34, 27, 21, 20 (8 × 3 jaunes). Cela produit un dessin assez érotique, ce qui n'est pas étonnant pour une grille Chirac.

J'aurais aussi quelques réflexions théoriques, mais quand ce sera au point.

Pieyre a écrit:Je propose la séquence : 10, 12 (2 bleus), 16, 4, 2, 33, 34, 27, 21, 20 (8 × 3 jaunes).

Bien joué.

Cela produit un dessin assez érotique.

C'est du cubisme, alors!

Je poserais bien une question aux matheux, tout particulièrement aux spécialistes des raisonnements par itération.

Combien y a-t-il de grilles Triancey concevables?

Je connais deux éléments de réponse: 1) énormément; 2) pas une infinité. Et j'aimerais bien savoir si "énormément", ça veut dire "des centaines de milliers" ou "des milliards de milliards". Ce dont je suis sûr, c'est que je n'ai encore jamais eu le sentiment de tomber deux fois sur la même grille... sauf évidemment quand j'avais utilisé deux fois le même mot-graine pour engendrer une fabrication (mon algorithme de fabrication est déterministe... vu que c'est un algorithme ).

Il y aurait assurément une infinité de grilles si le nombre de cases triangulaires sur une grille pouvait aller jusqu'à l'infini, mais ce n'est pas le cas avec mes algorithmes de fabrication. Je vous passe les détails, mais fondamentalement, la fabrication d'une grille consiste à saupoudrer un certain nombre de points sur la grille (points qui deviendront les sommets des triangles) et à les déplacer un peu (vers le barycentre des polygones) pour éviter la présence d'angles suraigus et de triangles très allongés. Ensuite on joint les points entre eux de façon que les segments ainsi formés ne se coupent pas, et quand on a fini, voilà, la grille est faite.

Mon algorithme impose une contrainte, qui limite le nombre de ces points: il est impossible d'ajouter un point à la grille si cela le placerait en-deçà d'une distance minimale avec un autre point déjà défini. Ajoutez à cela le déplacement des points vers le barycentre du polygone qu'on peut dessiner autour d'eux en réunissant toutes les cases ayant ce point pour sommet, et vous obtenez la physionomie de mes grilles, où les triangles sont "isogonoïdes" (c'est-à-dire: ressemblent vaguement à des triangles équilatéraux: leurs côtés ne sont pas disproportionnés, leurs angles sont généralement supérieurs à pi/4 -- 45 degrés -- et presque toujours supérieurs à pi/6 -- 30 degrés) et où les polygones engendrés sont très généralement des pentagones, des hexagones et des heptagones, possédant deux à deux un nombre de cases communes égal à deux. Il y a certes des exceptions (qui ne me dérangent pas: elles donnent du piment au jeu), mais ce sont bien des exceptions: elles se présentent très rarement et ne sont pas complètement différentes de la grille orthodoxe lambda (ce qui permet de les résoudre sans changer de logique).

Pour les grilles que je vous présente, la distance minimale entre deux sommets est de 0.165 (pour des grilles de côté 1.0), c'est-à-dire en gros un sixième de la largeur du carré-tore. Cette valeur n'a pas été choisie de façon totalement arbitraire: l'idée était de faire en sorte qu'il faille à peu près parcourir huit cases pour traverser la grille de part en part (de façon qu'un dernier coup joué sur un couloir prenne huit cases et ne soit donc pas optimal par rapport à un dernier coup joué sur un pentagone, un hexagone ou un heptagone).

Quand j'essaye la même logique avec une distance minimale de 0.5 ou 0.33, il est flagrant que je n'obtiens pas une infinité de grilles différentes, mais seulement quelques dizaines. Mais évidemment (enfin, c'est pas très difficile à comprendre), chaque fois qu'on arrive à caser un sommet de plus, le nombre de cases de la grille est majoré de deux. Donc, plus il y a de sommets, plus il y a de cases, plus il y a de grilles différentes envisageables, et ce de façon exponentielle.

Si la distance minimale entre deux points était de 1.0 (la largeur du carré), il n'y aurait que deux grilles envisageables (et même qu'une seule, car ces deux grilles seraient en fait deux fois la même avec des orientations différentes) et elle ne comporterait qu'un sommet sur le tore (répété aux quatre coins de la figure représentée à plat).

Chaque fois que j'ajoute un point-sommet, cela va se traduire ou par la division d'un segment (il y aura deux segments là où il n'y en avait qu'un), ou par la division d'une surface (il y aura trois triangles là où il n'y en avait qu'un); dans les deux cas, le nombre de cases de la grille est majoré de deux.

C'est à peu près tout ce que j'ai compris, et j'espère rencontrer l'esprit brillant qui saura s'appuyer sur tout ça pour évaluer le nombre de grilles possibles avec quatre cases, six, huit, dix, douze, etc., jusqu'à une petite soixantaine (en pratique, il est rarissime qu'on dépasse 48 cases).

Chers lecteurs matheux, à vos itérateurs.

Bon, ben en attendant que les bons mathématiciens se décident à me faire un bon raisonnement par itération, le mauvais mathématicien que je suis va se contenter de vous en présenter un mauvais... mais je pense que ce sera instructif quand même.



Sur le haut de cette figure, vous voyez la seule grille Triancey possible avec deux cases (on pourrait orienter la diagonale différemment, mais ça ne ferait pas une figure différente).

Sur le bas de cette même figure, vous voyez les trois grilles Triancey possibles avec quatre cases.

En augmentant le nombre de cases du minimum (deux cases de plus chaque fois qu'on ajoute un sommet), j'ai multiplié le nombre de grilles par trois.

Supposons (à mon avis c'est archi-faux, mais pas faux n'importe comment: c'est forcément très sous-estimé) que chaque fois que j'ajoute ainsi un sommet dans une grille existante, ça lui donne une descendance de trois grilles. Dans ce cas:

- avec deux cases, j'ai 3 puissance 0 grille.

- avec quatre cases, j'ai 3 puissance 1 grilles.

- avec six cases, j'ai au moins 3 puissance 2 grilles...

Donc quand j'arrive dans la zone de la quarantaine de cases où se trouvent la plupart des grilles produites par mon algorithme, je dois déjà avoir au moins dans les 3 puissance 20 grilles. Or 3 puissance 20, ça représente plus de 3 milliards (si ma table de logarithmes ne débloque pas).

Donc il n'y a pas seulement quelques milliers de grilles Triancey sur lesquelles on peut se triturer les méninges, mais au minimum plusieurs milliards. En fait, il y a même tellement de grilles concevables qu'il y a de quoi occuper jusqu'à leur mort tous les matheux de la planète. Donc, en rendant mon jeu libre de droits, j'inonde l'humanité de bienfaits et je mérite qu'on m'érige une statue.

Très bien. C'est tout ce que je voulais savoir.

Petitagore a écrit:


Sur le haut de cette figure, vous voyez la seule grille Triancey possible avec deux cases (on pourrait orienter la diagonale différemment, mais ça ne ferait pas une figure différente).
Sur le bas de cette même figure, vous voyez les trois grilles Triancey possibles avec quatre cases.

Tu vas surement me répondre que j'ai rien suivi, mais tant qu'à y être, pourquoi ne pas présenter les Carrés avec trois Triangles à l'intérieur aussi. Tu as fait deux. Tu as fait quatre. Pourquoi pas trois alors ?   Bon de ce que je comprends, c'est dû au fait qu'il faut impérativement que les deux cotés opposés du carré englobant soient strictement identiques. Bien bien.

Sinon t'avais pas dit que chaque Triangle avait toujours trois voisin ? Un voisin pour chacun de ses cotés ... J'ai pas bien pigé par quelle magie mystique tu arrives à nous convaincre que les deux triangles de la grille a deux triangles, ont chacun trois voisins distincts (Trois fois l'autre triangle donc). A moins que en fait, il suffit que le voisin soit distinct de soi même, auquel cas ça fonctionne.


Et surtout, et pour finir mes questions, si on numérote de 1 à 3 tes grilles à quatre cases de gauche à droite (et à supposer que mes réponses à mes propres questions au dessus ici posées soient justes), alors je ne vois strictement aucune différence entre la grille 1 (à gauche) et la grille 2 (au milieu). Ces deux grilles semblent identiques.  Du coup ça fait 2 puissance 20 = 1 048 576

(Je suis pas matheux hein, donc je ne fais que poser une question, à partir de ce que je vois)

Chaque fois que j'ajoute un point-sommet, cela va se traduire ou par la division d'un segment (il y aura deux segments là où il n'y en avait qu'un), ou par la division d'une surface (il y aura trois triangles là où il n'y en avait qu'un); dans les deux cas, le nombre de cases de la grille est majoré de deux.

Heu oui, pareil. On compte bien deux façons donc. Et non trois.

Stauk a écrit:Tu vas surement me répondre que j'ai rien suivi

Bien au contraire, je vais me réjouir qu'il y en ait encore un qui suive.  

mais tant qu'à y être, pourquoi ne pas présenter les Carrés avec trois Triangles à l'intérieur aussi. Tu as fait deux. Tu as fait quatre. Pourquoi pas trois alors ?   Bon de ce que je comprends, c'est dû au fait qu'il faut impérativement que les deux cotés opposés du carré englobant soient strictement identiques. Bien bien.

Oui, c'est ça. On en a parlé plus haut.

Sinon t'avais pas dit que chaque Triangle avait toujours trois voisin ? Un voisin pour chacun de ses cotés ... J'ai pas bien pigé par quelle magie mystique tu arrives à nous convaincre que les deux triangles de la grille a deux triangles, ont chacun trois voisins distincts (Trois fois l'autre triangle donc). A moins que en fait, il suffit que le voisin soit distinct de soi même, auquel cas ça fonctionne.

Non, tu as raison, le dessin du haut n'est pas une grille Triancey: pour être une grille Triancey, il faut avoir au moins quatre cases. J'étais bien conscient que c'était abusif, mais 1) c'était pour voir si vous suiviez;   2) pour le raisonnement par itération, c'était quand même bien pratique. Mais en effet, en toute rigueur, j'aurais dû démarrer ma démonstration avec quatre cases et pousser jusqu'à six. Mais 1) j'avais la flemme; 2) c'était pour motiver les contributeurs... à faire le boulot à ma place (l'esprit du web 2.0: quand c'est gratuit, c'est que c'est vous le produit! ).

Et surtout, et pour finir mes questions, si on numérote de 1 à 3 tes grilles à quatre cases de gauche à droite (et à supposer que mes réponses à mes propres questions au dessus ici posées soient justes), alors je ne vois strictement aucune différence entre la grille 1 (à gauche) et la grille 2 (au milieu).

Cornegidouille, tu as raison. Bon. Mais c'est visuellement différent, donc on dira que c'est valide pour compter les grilles visuellement différentes. Non? Tu n'es pas convaincu? T'es bien un matheux.  

Ouais, bon, j'avoue, mon raisonnement est foireux et pas mathématique. Mais il donne quand même une idée, un ordre de grandeur et même de gigantitude. Enfin, je crois.

Du coup ça fait 2 puissance 20 = 1 048 576.

Ah, ça va pas suffire pour qu'on m'érige ma statue. Va falloir que je le démontre mieux.

Petitagore a écrit:

Stauk a écrit:Du coup ça fait 2 puissance 20 = 1 048 576.

Ah, ça va pas suffire pour qu'on m'érige ma statue. Va falloir que je le démontre mieux.

Oui surtout que si ça se trouve c'est beaucoup moins. J'avoue que j'ai du mal à les compter tes bidules là. Ca me donne mal au crâne quand j'essaye ^ ^

Petitagore a écrit:Je poserais bien une question aux matheux, tout particulièrement aux spécialistes des raisonnements par itération.

Combien y a-t-il de grilles Triancey concevables?

Avant de chercher à les compter, il peut être judicieux de définir une règle d'égalité entre deux grilles, car selon comment on la définit, le résultat n'est pas le même !

Première option : « si on déplace légèrement un point sur une grille, alors la nouvelle grille et l'ancienne sont différentes » => Il y a trivialement une infinité de grilles

Deuxième option : Si on associe à une grille un graphe, dont chaque sommet est un des triangle de la grille et les arêtes relient ensemble des sommets dont les triangles associés sont voisins (chaque sommet a donc 3 arêtes). Et qu'on définit deux grilles comme égales si les deux graphes générés ont la même topologie, ce n'est pas forcément évident à voir, mais dans ce cas, tes 3 grilles à 4 triangles sont égales !

Avez-vous d'autres pistes ?

Levans a écrit:Avez-vous d'autres pistes ?

Je suggérerais bien de prendre en compte (entre autres) le nombre de cases autour d'un sommet commun. De ce point de vue-là, mon schéma représente bien, quand même, deux grilles à quatre cases différentes: la figure du milieu (celle de gauche aussi, d'ailleurs) a quatre cases autour de chaque sommet, et celle de droite seulement trois. Donc je pense qu'on ne peut les considérer comme identiques.

Mais c'est vrai que c'est monstrueusement prise de tête, ce bazar.

Levans a écrit: tes 3 grilles à 4 triangles sont égales !

Clairement, elle ne sont pas égales.  Suffit de considérer ce que j'appelle la "cardinalité" des sommets pour s'en convaincre. Ou cardinalité correspond au nombre de segments qui partent du sommet. Bon je trouve ça très mal commode de compter les sommets, alors j'ai pas du tout envie d'essayer ... surtout du fait que le bidule est un donut. Moi les donuts dépliés, j'ai du mal. Je les préfère dans mon estomac.

Petitagore a écrit:Je suggérerais bien de prendre en compte (entre autres) le nombre de cases autour d'un sommet commun.

On peut partir de là, mais ce n'est pas suffisant. Les exemples avec peu de points ne sont pas très parlants, maison peut assez facilement construire des exemple ambigus.

Je pense qu'on pourra néanmoins s'accorder, dans un premier temps, sur cette condition suffisante d'égalité :

Si on peut déformer continuement une grille A en une grille B (en déplaçant les points de manière continue sans changer leurs connexions et sans se faire croiser deux arrêtes à aucun moment de la transformation) alors elles sont égales.

NB : le point formant les 4 coins ne peut évidemment pas bouger, et les points sur des bords doivent y rester

On peut noter que si on se cantonne à cette définition, alors les 3 grilles à 4 triangles sont différentes.

Il serait bon de réussi à mettre des termes mathématiques clairs sur la définition de l'égalité que l'on veut, si on veut traiter le problème rigoureusement.

Stauk a écrit:Clairement, elle ne sont pas égales.

Il s'agissait surtout de montrer que la définition de l'égalité que l'on choisit est très importante, et qu'il est important de se mettre d'accord sur un expression rigoureuse de cette égalité.

Levans a écrit:
NB : le point formant les 4 coins ne peut évidemment pas bouger, et les points sur des bords doivent y rester
On peut noter que si on se cantonne à cette définition, alors les 3 grilles à 4 triangles sont différentes.
Il serait bon de réussi à mettre des termes mathématiques clairs sur la définition de l'égalité que l'on veut, si on veut traiter le problème rigoureusement.

En fait c'est un donut. Le carré qui englobe la grille, n'a que deux arrêtes (au lieu de 4 comme on pourrait le croire sur le dessin).

Stauk a écrit:En fait c'est un donut.

Je sais que suis parfois aussi crétin qu'Homer Simpson, mais le terme un peu sérieux est tore.

J'ai raison, c'est un tore!

Stauk a écrit:En fait c'est un donut. Le carré qui englobe la grille, n'a que deux arrêtes (au lieu de 4 comme on pourrait le croire sur le dessin).

Oui, oui, je n'ai jamais dit le contraire...

Juste que l'on soit d'accord. je pense qu'on s'accorde pour dire que ces deux grilles sont différentes mêmes si elles ont les mêmes nombres de face touchant chaque sommet : (Erratum : il faut lire 9 et non 8 )



Reste à poser des mots mathématiques clairs là dessus

Par exemple :
- Si je prends une grille et la rotate d'un quart de tour, la nouvelle grille est-elle égale à la première ?
- Si je fais une symétrie par rapport à un des 4 axes du carré ?

Levans a écrit:

Stauk a écrit:En fait c'est un donut. Le carré qui englobe la grille, n'a que deux arrêtes (au lieu de 4 comme on pourrait le croire sur le dessin).

Oui, oui, je n'ai jamais dit le contraire...
Juste que l'on soit d'accord. je pense qu'on s'accorde pour dire que ces deux grilles sont différentes mêmes si elles ont les mêmes nombres de face touchant chaque sommet : (Erratum : il faut lire 9 et non 8 )

En fait je sais pas comment tu obtiens 8. (ou 9, ou 13, ou n'importe quelle valeur ...). Techniquement y a qu'un seul sommet en fait, non ? Donc ça serait 13 ? C'est sûr que c'est plus simple à l'intérieur du carré ...

Levans a écrit:
Reste à poser des mots mathématiques clairs là dessus
Par exemple :
- Si je prends une grille et la rotate d'un quart de tour, la nouvelle grille est-elle égale à la première ?
- Si je fais une symétrie par rapport à un des 4 axes du carré ?

Ben ouais. Rotations okay. Symétries axiales okay. Symétries centrales aussi ?

J'ai beaucoup de mal à bien "comprendre" l'effet donut. (tore stu veux). Je dirais que deux grilles sont équivalentes, si d'une part chaque type de triangle est présent en quantité égale dans les deux grilles (deux triangles sont du même type, s'ils ont les même cardinalités à leur sommets (disons rangés par ordre décroissant au niveau des cardinalités pour rendre la comparaison plus aisée) et d'autres part, chaque couple de chemin minimaux (c'est à dire en traversant le moins de frontières possibles) entre deux triangles de type A et B existant sur une grille, existe aussi sur l'autre. (chai pas si chui bien clair). Ou le chemin est la donné des triplets de cardinalité des triangles traversés.

Exemple y a trois triangles 863 sur les schémas proposés.

Un seul 863 est connecté à 653. (appelons le Alphonse).
Pour que Alphonse rejoigne le 863 le plus proche il faut aller : 886 : 863 sur la grille de gauche.
Mais Alphonse : 863 directement sur la grille de droite.

Ergo les deux grilles sont différentes.

Merci de toutes ces réflexions. J'ai beau m'intéresser au sujet depuis un bon moment, je pense que vous partez dans des directions où je me suis peu aventuré, c'est enrichissant.

Une remarque en passant: en général, autour d'un sommet d'une de mes grilles, il y a 5, 6 ou 7 cases (ou segments, c'est pareil); les valeurs comme 4 ou 8 sont beaucoup plus rares, les valeurs 3 et 9 ne se rencontrent presque jamais -- donc des exemples où on les fait apparaître sont un peu particuliers, pas vraiment représentatifs de mon petit jeujeu.

Je dis ça parce que si vous aboutissez à un nombre astronomique de grilles, mais en y incluant une ribambelle de grilles où il serait courant que les sommets voient converger 3 ou 9 segments (ou même davantage), ben ça ne correspondrait pas vraiment à ce que j'obtiens -- et donc le nombre astronomique que vous obtiendriez serait plus un maximum ultra-théorique qu'un minimum donnant un ordre de grandeur de ce qu'on peut obtenir en pratique. Si tout au contraire vous vous limitez à des sommets où ne convergent que 5, 6 ou 7 segments (je préfèrerais), là vous aboutirez à un nombre forcément inférieur à la diversité envisageable, et que je pourrai donc considérer comme un minimum, tant en théorie qu'en pratique. Pour moi ce serait une information plus précieuse, car je cherche à démontrer que la diversité de mes grilles est bel et bien gigantesque en pratique; j'aimerais pouvoir affirmer que le risque que je tombe deux fois sur la même grille avec des mots-graines différents peut être considéré comme tout à fait négligeable. Un maximum théorique m'intéresse nettement moins qu'un minimum pratique.

Mais je ne veux pas vous empêcher de réfléchir: c'est beau la science.

Il y a des grilles faciles, des grilles difficiles... et il y a aussi des grilles vexantes, qui récalcitrent indéfiniment, refusent de se laisser résoudre, alors même qu'elles tolèrent des tonnes de solutions. En voici une qui m'a particulièrement humilié: la grille "decembre".

Elle a l'air extrêmement banale... elle ne l'est pas tant que ça, car elle contient exclusivement des pentagones, des hexagones et des heptagones; aucun quadrilatère, aucun octogone, ça a vraiment l'air d'un cas d'école sur lequel les solutions doivent abonder. Et, de fait, elles abondent...

... sauf que pour des raisons qui m'échappent c'est toujours les solutions que j'envisage qui foirent! Du coup, mon propre solveur se donne la joie de m'humilier en me montrant que j'aurais pu essayer n'importe quoi d'autre que ce que j'ai envisagé, et que ça aurait marché...

Voici un inventaire (certainement très incomplet) des cavexes envisageables. Attention, ne faites pas comme moi, ne vous braquez pas sur le premier: c'est justement le seul qui paraît inutilisable -- et par un fait exprès, c'est justement la première idée qui m'est venue, et à laquelle bien entendu je me suis accroché comme un morbaque parce que parmi mes nombreuses qualités, j'ai celle d'être persévérant... y compris dans l'erreur.  



A titre d'entraînement, vous pouvez essayer de redessiner ces cavexes (tous), puis essayer de les employer (sauf le premier!) pour résoudre la grille.

Je publierai les corrigés demain (s'il plaît à Dieu de me laisser le temps de le faire).

Bon. Je rappelle que nous travaillons sur la grille "decembre", avec les images de cavexes publiées dans le post précédent.

Pour ceux qui ont manqué des épisodes, un cavexe est un ensemble de cases voisines (un coacervat) sur lequel il paraît envisageable de terminer la partie (car en toutes choses il faut considérer la fin): il y a dedans le polygone convexe qui va bien pour le coup final (en l'occurrence un heptagone, que je vous ai coloré en bleu pour que ce soit plus clair), et un certain nombre (trois ou quatre, en général) de triplets de cases susceptibles d'être pris "par trois" et donc coloriables en jaune. Surtout, ce cavexe encercle totalement le tore, l'expérience démontrant qu'en général (mais pas toujours, ce serait trop simple) il suffit de faire très attention à ne pas toucher le cavexe dans les premiers coups de la partie pour aboutir au score optimal visé.

Commençons par dessiner les cavexes; ça ne présente aucune vraie difficulté, mais ça vous entraînera à en imaginer vous-mêmes, vous verrez que ça n'est pas bien malin (du moins sur cette grille).

Premier cavexe de la figure (c'est, je le rappelle, la première idée qui me soit venue et également la plus mauvaise -- mais ça n'empêche pas de le dessiner: 11 12 19 4 18 (bleu), 15 21 14 (jaune).

Cavexe valide 0: 0 34 37 36 2 (bleu), 11 30 18 (jaune).

Cavexe valide 1: 3 4 18 11 12 (bleu), 15 37 29 30 (jaune).

Ah tiens, il y a une erreur dans ce cavexe (voir plus bas); elle est sans conséquence, mais saurez-vous la détecter?

Cavexe valide 2: 37 2 5 3 38 (bleu), 29 31 19 (jaune).

Cavexe valide 3: 34 0 37 35 2 (bleu), 11 9 22 (jaune).

Cavexe valide 4: 11 17 12 4 19 (bleu), 21 1 8 (jaune).

Cavexe valide 5: 7 27 14 13 8 (bleu), 25 28 41 (jaune).

Cavexe valide 6: 2 5 39 38 3 (bleu), 10 16 24 (jaune).

Cavexe valide 7: 29 17 18 16 24 (bleu), 10 37 2 (jaune).

Cavexe valide 8: 11 12 19 3 17 (bleu), 21 6 26 40 (jaune).

Enfantin, non?

Et maintenant les solutions intégrales sur la base de ces cavexes, c'est à peine plus difficile... avec un peu d'habitude :

Avec le cavexe 0: 23 8 15 28 26 13 41 39 25 12 (hors du cavexe), 18 11 30 36 (dans le cavexe).

Remarque: Comme dans la plupart des solutions, le dernier coup, qui prend le polygone convexe final, est indifférent.

Avec le cavexe 1: 5 25 32 33 7 35 14 21 8 (hors du cavexe), 37 12 2 10 17 (dedans)... et cornegidouille, je m'étais gourré de polygone final dans mon schéma du post précédent (d'ailleurs ça m'avait titillé au moment de dessiner le cavexe, comme signalé plus haut); ben vous voyez, c'est pas grave, on s'en sort quand même; comme quoi ça n'est pas si malin que ça...

Avec le cavexe 2: 11 22 16 1 27 34 13 25 33 41 (hors du cavexe), 19 31 29 38 (dedans).

Avec le cavexe 3: 16 38 29 18 32 20 4 33 21 6 (hors du cavexe), 22 9 11 36 (dedans).

Avec le cavexe 4: 6 37 39 40 35 23 28 27 31 15 (hors du cavexe), 8 1 21 4 (dedans).

Avec le cavexe 5: 0 29 35 38 3 17 16 19 32 4 (hors du cavexe), 41 28 25 9 (dedans).

Avec le cavexe 6: euh... Bordel, je retrouve plus la soluce! Encore une idée à la con du solveur... Prenez patience, je vous la retrouverai (mais mes compliments à ceux qui la trouveront seuls).

Avec le cavexe 7: 25 5 32 33 7 35 14 21 12 8 (hors du cavexe), 2 10 37 29 (dedans).

Avec le cavexe 8: 24 2 38 32 23 28 0 15 9 (hors du cavexe), 40 26 6 21 4 (dedans).

Eh ben vous voyez, c'est pas si malin que ça...

Ca y est, j'ai retrouvé la solution de la grille "decembre" avec le cavexe 6... et je l'ai retrouvée tout seul avec ma petite tête, en plus. La voici:

19 14 21 7 31 40 34 28 29 8 (hors du cavexe), 24 16 10 3 (dedans).

C'était pourtant simple.

Comme l'a fait remarquer Levans, on peut associer à toute grille trianceysque un graphe. Il est non planaire (puisqu'il se déploie sur un tore) mais localement planaire. Plus précisément, dans la mesure où sa nature non planaire correspond à un bord de la surface (par exemple les côtés du carré de la représentation plane), on doit pouvoir se restreindre pour nombre de propriétés à étudier le graphe planaire obtenu par coupure selon ce bord. En effet, de même que le bord d'une surface continue est de mesure nulle, la frontière d'une surface discrète contribue, pour certaines propriétés, d'une façon qui tend vers 0 quand la discrétisation devient plus précise.

On sait déjà que le nombre de triangles est le même sur les représentations planaire et torique.
Le nombre de sommets est plus important sur la représentation planaire, mais on sait lesquels il faut identifier pour obtenir le nombre correspondant dans la représentation torique. Et, plus le nombre de sommets intérieurs augmente, plus on peut considérer l'un comme une approximation de l'autre.
Pour le nombre d'arêtes, le cas est assez semblable. Pour un nombre important de triangles, il doit donc être de même ordre sur les deux représentations.

Reste le nombre de grilles planaires, qui doit être en rapport avec ce qu'il serait sur le tore, mais de façon peut-être un peu plus complexe. En effet il s'agit cette fois de juger de la configuration globale de la grille. Le nombre de grilles apparentes (sur le carré correspondant au jeu) est donc là aussi supérieur au nombre grilles réelles, mais, du fait des symétries possibles, on pourrait avoir à diviser le premier nombre par un certain facteur.

Concernant plus généralement le nombre de graphes connexes à n sommets, quelques recherches sommaires me conduisent à penser que ce nombre doit être une exponentielle de n. Mais il ne semble pas y avoir d'estimation précise. Ainsi, on notant p(n) le nombre de graphes planaires connexes à n sommets, je trouve que 1/n × log2 (p(n)) tend vers une certaine constante c (entre 3 et 6 – la valeur n'est pas fixée). Ce qui donnerait p(n) équivalent à 2^(cn) lorsque n tend vers l'infini. Par ailleurs, pour les premiers graphes de cette sorte (en commençant à zéro sommet), on obtiendrait le nombre exact de graphes : 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885...

Maintenant, cela concerne un nombre de graphes plus divers que ceux correspondant aux grilles de Petitagore, comme il l'a lui-même remarqué. C'est-à-dire qu'on obtient toujours une majoration et non une minoration. Dans la mesure où les restrictions imposées aux grilles convenables sont importantes (la distance bornée entre sommets, et surtout le fait que tout triangle doit en en toucher exactement trois autres), il pourrait y avoir une estimation plus précise, peut-être même faisant intervenir des structures mathématiques moins complexes que le cas général. À lire un peu sur le sujet, je ne crois pas qu'on pourra facilement s'en sortir. Mais rien n'est certain. Il faudrait y passer du temps.

Merci, Pieyre, de ces explications, même si elles expriment mieux (en termes mathématiques) la complexité du problème qu'elles ne le résolvent...

A défaut d'une mesure exacte, j'ai envisagé de me contenter d'une estimation par extrapolation. Je m'explique. Avec, disons, douze cases, la variété des grilles est déjà grande, mais pas forcément incommensurable, et avec quatorze non plus. Je peux me contenter de faire apparaître des tonnes de grilles au hasard, les compter, et constater qu'avec 14 cases j'en obtiens... un certain nombre de fois plus qu'avec 12, après quoi yorapuka extrapoler la tendance jusqu'à 30, 40, 50 cases. Ca ne serait pas hyper-rigoureux, mais ça mènerait à un résultat qui ne serait pas archi-faux (et qui serait sans l'ombre d'un doute sous-estimé et non surestimé, donc exploitable pour affirmer l'existence d'une gigantesque variété).

Cela dit, il faudrait en effet (ça a été évoqué plus haut par Levans) que je parvienne à répondre par oui ou par non et sans erreur à la question "telle grille est-elle différente de telle autre", ce qui n'est pas évident, au moins compte tenu des symétries. D'un point de vue algorithmique, il me serait assez facile de faire l'inventaire des nombres de segments partant de chaque sommet, de classer tout ça pour chaque grille, et de conclure avec certitude, chaque fois que j'obtiens deux classements différents, que je suis en présence de deux grilles différentes; évidemment, ça me ferait sous-estimer considérablement la diversité des grilles, mais ça pourrait me permettre d'obtenir un nombre minimal de grilles différentes, et un taux d'accroissement minimal de la complexité chaque fois qu'on ajoute un sommet  -- donc j'aboutirais bien, en extrapolant ça, à une sous-estimation minimale, qui pour moi serait précieuse (y compris si elle était plusieurs milliards de fois inférieure à la quantité réelle).

C'est beaucoup de tintouin pour obtenir un résultat archi-sous-estimé... Mais je soupçonne que ça pourrait fournir des idées pour aboutir à une démarche plus rigoureuse.

En tout cas, là, tout de suite, j'avoue que j'ai un peu la flemme.

Au fait, personne n'a trouvé ce qui foirait il y a trois posts dans ma façon de dessiner mon cavexe 1? Ce n'est pas très difficile à remarquer (et c'est en plus très pédagogique pour la résolution des grilles, raison pour laquelle je vous titille à ce sujet), mais c'est un peu plus difficile à exprimer en termes mathématiques rigoureux... même que je le ferai plus tard parce que là j'ai un train à prendre.

Personne ne répond à ma question sur le cavexe foireux de la grille "decembre"... C'est dommage car ça tend à faire penser que je ne suis pas parvenu à vous faire vraiment comprendre l'intérêt d'un cavexe bien formé pour la résolution d'une grille et j'en suis fort marri.

Bon, ben je vous explique, et pardon si j'ai l'air de me répéter un peu, mais c'est important.

Dessiner un cavexe, c'est fantasmer sur la fin de la résolution d'une grille. Les coups que l'on joue pour dessiner le cavexe sont voués à être rejoués en ordre inverse, à la fin de la résolution d'une grille. Il faut donc se limiter à construire le cavexe avec des coups "réversibles", qui conduiraient à prendre les mêmes groupes de trois cases dans un sens chronologique comme dans l'autre. Et cela implique qu'un bon "coup de cavexe" soit constitué de trois cases ayant toutes deux voisins à l'intérieur du cavexe, le troisième voisin étant à l'extérieur d'icelui.

Pour le dire autrement, il faut dessiner le cavexe comme une accumulation de bosses de trois cases, bombées avec un creux vers l'intérieur du cavexe, et surtout ne comportant jamais une pointe cornue sortant du cavexe avec deux côtés voisins de cases n'appartenant pas à celui-ci.

Ouais, c'est bien compliqué, ça sera plus clair si vous envisagez la chose visuellement. Retournez donc, siouplaît, sur la grille "decembre".

Je dessine le polygone final (un heptagone) en bleu en cliquant par exemple sur 16, 17, 30, 23 et 18. A y est, vous visualisez l'heptagone bleu?

Maintenant, si je clique 37, j'obtiens trois cases jaunes ayant toutes et chacune deux voisins dans le cavexe. Pour la case 36, ce sont les cases 29 et 37. Pour la case 38, ce sont 30 et 37, et pour la case 37, ce sont évidemment 36 et 38. Tous ces numéros désignent des cases faisant partie du cavexe.

Continuons. Si je clique 10, je prends trois cases colorées en jaune. La case 15 a deux voisins dans le cavexe (10 et 16), la case 11 a deux voisins dans le cavexe (10 et 17), et la case 10 a deux voisins dans le cavexe (15 et 11), donc tout va bien.

Terminons. Si je clique 2, je prends là encore trois cases colorées en jaune. La case 1 a deux voisins dans le cavexe (2 et 10), la case 3 a deux voisins dans le cavexe (11 et 2) et la case 2 a elle aussi deux voisins dans le cavexe vu qu'elle en a même trois (37, 1 et 3). Donc mon cavexe est valide, hallelujah.

Et si j'agrandis encore le cavexe (ce qui n'est pas nécessaire, mais permis), je peux cliquer sur 12, et j'obtiens trois nouvelles cases jaunes ayant chacune deux voisins dans le cavexe; pour 4, ce sont les cases 3 et 12; pour 19, ce sont les cases 18 et 12, et pour 12, ce sont les cases 4 et 19. Tout baigne.

Mais ça, c'est la solution -- valide -- que j'aurais dû vous indiquer. Or je vous en ai indiqué une autre, qui, elle, est erronée.

Je vous ai dit (par erreur) de colorer en bleu un autre heptagone que l'heptagone final, par 3, 4, 18, 11, 12. Jusque là, ça a l'air d'aller.

Puis je vous ai dit de cliquer 15. C'est valide, ça prend trois cases jaunes ayant toutes et chacune deux voisins dans le cavexe: 10 qui a pour voisins 15 et 11, 16 qui a pour voisins 15 et 17, et 15 qui a pour voisins 10 et 16. Jusque là, ça va donc encore.

Mais ensuite, je me suis trompé. Là, je vous ai dit de cliquer sur 37, ce qui certes prend trois cases jaunes (37, 1 et 2), mais il y a un mais. La case 1 a bien deux voisins dans le cavexe (10 et 2), 2 a bien deux voisins dans le cavexe (1 et 3), mais 37 n'a qu'un voisin (la case 2) dans le cavexe, contre deux voisins hors du cavexe (36 et 38).

Et là, c'est raté. Si on rejoue cette séquence à l'envers, 36 et 38, qui sont hors du cavexe et donc censées être déjà prises à ce stade du récit, auront forcément déjà coloré la case 37. Donc nous sommes en présence d'un cavexe mal pensé.

Je sais, dit comme ça, ça a pas l'air simple... mais en fait, il suffit de se rendre compte que la case 37 a l'air d'une corne isolée sortant du cavexe, au lieu d'appartenir à une bosse de trois cases s'ajoutant à un cavexe qui garde un sympathique aspect gonflé et rondouillard. Visuellement, ça se voit au premier coup d'oeil, et l'abondant baratin logique que je viens de vous débiter est complètement superflu pour un joueur entraîné qui a appris à reconnaître la forme rondouillarde d'un cavexe en formation, et la forme cornue et diabolique d'un cavexe foireux.

Le diable est dans les détails... et dans les cornes du cavexe.

Bon. M'inspirant des travaux et des schémas de Levans (merci à lui), je poursuis sur mon idée de noter de façon concise mais relativement complète les propriétés d'une grille, de façon à pouvoir affirmer sans risque d'erreur que deux grilles sont différentes, en dépit des symétries et des bizarreries d'affichage qu'entraîne la nature torique du bazar.



Voici une grille de 18 cases et donc 9 sommets (sur un tore, les cases sont bougrement plus faciles à compter que les sommets). Sauf erreur ou omission, un de ces sommets (en bas à droite) est au centre d'un quadrilatère, deux sont au centre d'un pentagone, quatre sont au centre d'un hexagone et deux d'un octogone (1 + 2 + 4 + 2 = 9, le compte est bon).

On pourrait noter ça de façon concise:
9
4 : 1
5 : 2
6 : 4
8 : 2

avec bien sûr un classement rigoureux du nombre de cases autour d'un sommet (ici, en ordre croissant).

Et de façon encore plus concise (pour faciliter les traitements informatiques, par exemple avec le programme sort d'Unix pour ceux qui connaissent): 9;4:1;5:2;6:4;8:2. C'est pas super-lisible pour un humain, mais un ordinateur s'en sort très bien, arrive sans problème à classer des inventaires de descriptifs de ce type et du coup, quand deux grilles auront des descriptifs différents, on pourra assurer sans l'ombre d'un doute qu'elles sont différentes.

L'inverse n'est pas vrai, mais c'est un début.

Je poste déjà ça, et je reviens ensuite avec un perfectionnement.

Dans la notation que je viens de définir, plusieurs grilles très différentes peuvent avoir le même descriptif. Avec neuf sommets, ça permettrait déjà de faire un peu le tri, mais quand on va atteindre la vingtaine ce sera nettement insuffisant. Je propose donc un perfectionnement (une chinoiserie, même, car ça devient assez complexe -- mais toujours gérable par un programme comme le sort d'Unix): noter non seulement le nombre de cases autour de chaque sommet, mais aussi le nombre de cases autour des sommets à la périphérie du polygone convexe ayant le sommet pour centre.

Ouh la, que ce que je dis est compliqué. Reprenez la figure du post précédent, regardez le quadrilatère en bas à droite. Autour du sommet central marqué du chiffre 4, il y a deux sommets marqués du chiffre 6 et deux du chiffre 8. Je propose qu'au lieu de noter juste 4, on détaille un peu: 4 (6 : 2; 8 : 2).

Je sais, ça ne lève pas toutes les confusions. Sur l'exemple dont je vous parle, si on fait le tour des sommets du périmètre, on lit dans l'ordre 6 - 8 - 6 - 8, mais ça pourrait aussi être 6 - 6 - 8 - 8 et dans ce cas on aurait de toute évidence deux quadrilatères différents. Je pense quand même que si on applique ce mode de notation pour l'ensemble de la grille, jusqu'à une vingtaine de cases il sera vraiment bien rare que deux grilles différentes aient exactement parfaitement le même descriptif -- donc compter les descriptifs différents permettra de se faire une idée très légèrement sous-estimée (je préfère ça que le contraire) de la diversité des grilles.

Bon, maintenant, je dois admettre que la notation ne sera pas super-concise ni super-lisible, puisqu'elle donnera quelque chose du genre (l'exemple est réel et correspond à la figure du post précédent -- sauf erreur ou omission):

neuf sommets: 9;
sommets de quadrilatères: 4(6:2;8:2):1;
sommets de pentagones: 5(5:1;6:3;8:1):2;
sommets d'hexagones:6(4:1;5:1;6:1;8:3):1;6(5:2;6:2;8:2):3;
sommets d'octogones: 8(4:1;5:1;6:5;8:1):2.

Surtout n'hésitez pas à me signaler une erreur...

Et donc, à l'usage du sort d'Unix, ça deviendrait un truc super-simple d'un point de vue informatique (non, je blague pas, c'est simple et à lire et à écrire... quand le boulot est fait par un programme informatique):

9;4(6:2;8:2):1;5(5:1;6:3;8:1):2;6(4:1;5:1;6:1;8:3):1;6(5:2;6:2;8:2):3;8(4:1;5:1;6:5;8:1):2

Sans qu'il soit tout à fait exclu que deux grilles différentes aient le même descriptif, je pense qu'on peut dire raisonnablement que jusqu'à une vingtaine de sommets ça ne sera quand même pas très fréquent en proportion. Un descriptif permettra donc d'identifier une grille avec un peu le même taux d'erreur qu'un ADN permet d'identifier un criminel.

Des objections? Des questions? D'autres idées?

Quelqu'un a suivi?

(ton désespéré) Au moins la démarche générale?

Je pense que c'est une voie où il sera plus facile de trouver une minoration en effet (même si une description théorique précise du graphe torique correspondrait peut-être à un cas déjà traité dans la littérature).

J'avais pensé à une façon un peu différente, mais en m'inspirant aussi d'une description des grilles. J'envisageai de partir d'une grille régulière de triangles reliés par six angles, c'est-à-dire correspondant à un pavage par des hexagones dans la représentation duale, que j'adopte par la suite pour exprimer les choses plus facilement.

À partir de ce pavage hexagonal, qui correspond déjà à une grille possible, on peut se demander de combien de façon le transformer pour obtenir d'autres grilles, et cela en modifiant juste quelques hexagones.

Par exemple, si l'on transforme un hexagone en pentagone, cela peut se répercuter juste sur un autre hexagone relié au premier par un côté, qui deviendra lui-même un pentagone, le reste de la structure restant inchangée. Combien de grille peuvent comporter un tel double pentagone ? Eh bien une seule, par translation ou rotation de la grille sur le tore. Mais, si l'on introduit un autre double pentagone un peu plus loin, on aura déjà toute une série de grilles : il suffit de compter de combien de façons deux doubles pentagones peuvent être diversement éloignés et diversement orientés l'un par rapport à l'autre.

De même on peut transformer un hexagone en carré, avec deux hexagones voisins qui deviennent des pentagones, et établir un comptage du nombre de grilles possible en disposant deux figures de ce genre sur le pavage.

Et puis on peut associer les deux motifs : double pentagone et carré + double pentagone, pour en obtenir d'autres.

Il s'agirait d'établir une liste des modifications locales du pavage hexagonal qui pourrait être combinées de sorte que le nombre de leurs dispositions serait facile à établir.

Maintenant, pour une grille d'une vingtaine de triangles, je ne pense pas que l'on pourra dépasser l'ordre de la centaine. Ou alors il faudrait faire intervenir de nombreux assemblages de polygones, ce qui pourrait être fastidieux.

C'est pas bête du tout, ça, Pieyre...

Mais immédiatement je me demande à quoi pourrait ressembler un assemblage d'hexagones représenté sur un schéma carré (ne coupant évidemment pas une case triangulaire de part et d'autre des contours du carré, sinon ça ne ressemblerait plus à mes grilles). Ca n'est sûrement pas impossible (quitte à déformer pas mal les hexagones à proximité des bords et des coins du carré), mais je n'arrive pas à me le figurer -- or le faire m'aiderait à réfléchir.

Donc... j'y réfléchis!

Dans ton maillage par des triangles, il était nécessaire, pour des raisons pratiques, et heureusement possible, qu'ils entrent sans être coupés dans le schéma carré. Mais, dans la représentation duale, les polygones de Voronoï ne peuvent pas respecter la même contrainte.

Peut-être pourrais-tu dessiner cette représentation duale sur tes grilles. Il suffit de relier les centres de gravité de tous les triangles qui se touchent par un côté (et tenir compte des triangles ayant un côté sur l'un des bords du carré, en traçant un segment horizontal ou vertical vers le bord). Je crois que cela peut aider à se représenter la structure d'une grille. Déjà il y a moitié moins de polygones que de triangles, et puis leur diversité de forme permet sans doute de se représenter mieux en quoi deux grilles sont ou non équivalentes.

Bon, je ne sais pas si ça fera beaucoup avancer le schmilblick, mais je suis parvenu à dessiner un réseau hexagonal sur la représentation carrée d'un tore. Bel effort (c'était prise de tête, ce truc...).



Et maintenant que j'arrive à le concevoir, je n'aurais pas forcément beaucoup de difficultés à en faire une grille clicable, histoire de l'étudier plus commodément. Je vous tiendrai au courant si j'y arrive.

Tes hexagones sont disposés de façon oblique. Il y a aussi une configuration tu aurais deux hexagones de côtés égaux au même niveau vertical.
Enfin, quand je dis oblique, c'est par rapport à l'horizontale. Par rapport à la verticale, ils sont alignés.

On peut obtenir une telle configuration en traçant un réseau de triangles équilatéraux et en appliquant dessus une grille carrée passant par des sommets.

Mais je suis vraiment une nouille, moi! Il y a une représentation beaucoup plus facile à comprendre:



... mais on n'a pas tout perdu, car ceci nous fournit un merveilleux exemple du fait que deux représentations graphiquement très différentes peuvent servir à décrire un seul et unique assemblage de polygones sur un tore. Je suis bien content d'avoir trouvé cet exemple, tiens.

Soit dit en passant, selon la logique que j'ai expliquée plus haut, cette grille serait notée 12;6(6:6):12 -- et ce dans les deux cas, bien évidemment.

Ce qui serait nettement plus clair, n'est-il pas vrai?

Pieyre a écrit:On peut obtenir une telle configuration en traçant un réseau de triangles équilatéraux et en appliquant dessus une grille carrée passant par des sommets.

Je serais preneur d'un petit dessin.

Voici ! tu m'excuseras de la mauvaise qualité, mais j'ai préféré faire ça avec mes petites mains.

Oui, c'est concevable, mais ça oblige à répartir certaines cases de part et d'autre du tore -- ce qui empêche de considérer ta figure comme une grille Triancey orthodoxe.

Par ailleurs, ta figure a une superficie de vingt cases (sauf erreur de ma part, le réseau hexagonal exige que le nombre de cases soit un multiple de six). Il faudrait abaisser le trait inférieur d'un demi-triangle équilatéral pour passer à une superficie de vingt-quatre cases et faire en sorte que les motifs se correspondent bien en haut et en bas. Mais on comprend l'idée.

N'empêche, pour les raisonnements que tu te proposais d'effectuer, je pense que ma deuxième figure, hyper-régulière, est très facile à exploiter et à comprendre.

Moi aussi j'ai eu tendance à ne pas compter tous les triangles. Mais regarde bien : il y en a 24, et la grille est orthodoxe.

Par ailleurs, je ne prétendais pas imposer un modèle, mais indiquer une méthode simple pour obtenir une grille régulière. Et je reconnais que ta grille a l'avantage de présenter des triangles identiques, notamment de même aire, ce qui évite de se poser la question que tu as soulevée des triangles trop petits pour être acceptables.

Pendant que j'y suis, à ce sujet, j'ai l'impression que dans ta version commerciale, les triangles ne sont pas de même aire, justement. C'est-à-dire qu'y placer les pièces triangulaires bicolores, forcément des triangles équilatéraux, pourrait les recouvrir plus ou moins. N'y aurait-il pas une transformation simple de la grille, qui consisterait à déplacer juste un peu les sommets, de sorte que tous les triangles soient de même aire ?

... Je comprends un peu tardivement la référence à la superficie. Bon, alors j'ajoute que si la superficie est bien de 20 triangles équilatéraux, il me semble que cela importe peu. Il y a en a bien 24 en tout, certains entiers et certains demi-entiers. Mais c'est juste une question de découpage.
Ce qui est vrai c'est que, sur le tore, le fait de couper les triangles en deux fait que le maillage n'est pas régulier. Alors que le tien l'est. C'est d'ailleurs intéressant. La figure de référence, c'est le tore. On ne peut pas conserver toutes les propriétés de son maillage régulier sur le carré; aussi il faut choisir d'en sacrifier au moins une. J'ai sacrifié la régularité de certains triangles du bord; tu as sacrifié l'équilatéralité.

... J'ajoute encore une chose (j'ai l'esprit de l'escalier). Et si tu envisageais dans ta version commerciale une grille hexagonale ? C'est tout de même plus en rapport avec le triangle que ne l'est le carré... Alors il pourrait y avoir ou bien deux joueurs, ou bien quatre, ou bien six. Pour six, il suffirait de disposer de dés cubiques à six couleurs à la place des triangles bicolores. Pour quatre il est moins évident de trouver une pièce acceptable, dans la mesure où le tétraèdre ne peut reposer sur sa pointe pour montrer la couleur du joueur... Mais on doit pouvoir trouver une solution.

Pieyre a écrit:Moi aussi j'ai eu tendance à ne pas compter tous les triangles. Mais regarde bien : il y en a 24, et la grille est orthodoxe.

Ah, OK. Mais alors elle n'est pas intégralement composée de triangles équilatéraux -- je croyais que c'était ça l'idée.

Pendant que j'y suis, à ce sujet, j'ai l'impression que dans ta version commerciale, les triangles ne sont pas de même aire, justement.

En effet. En théorie, la disproportion maximale est de 1 à 3: la plus petite case peut être presque trois fois plus petite que la plus grande (en pratique, ça ne va guère au-delà de deux)... tout simplement parce qu'au-delà, il serait possible de rajouter un sommet au milieu d'un gros triangle pour le transformer en trois petits.

C'est-à-dire qu'y placer les pièces triangulaires bicolores, forcément des triangles équilatéraux, pourrait les recouvrir plus ou moins. N'y aurait-il pas une transformation simple de la grille, qui consisterait à déplacer juste un peu les sommets, de sorte que tous les triangles soient de même aire ?

Ah, la passion égalitariste du peuple français...  

Je n'ai pas creusé à fond la question, mais je pense que ce serait assez délicat: chaque case appartient à trois polygones, donc on est en présence d'un joli sac de noeuds... En tout cas, toute modification des aires des cases aurait forcément, aussi, une influence sur la disproportion entre les longueurs des côtés (en théorie, le côté le plus long est deux fois plus long que le plus petit), sans préjudice de la disproportion entre les angles des triangles (en théorie, le plus obtus peut être quatre fois plus large que le plus aigu -- en pratique, c'est beaucoup moins).

Je peux me tromper, mais je crois qu'essayer d'unifier les aires, ou tout au moins de diminuer les disproportions entre elles, ce serait se donner beaucoup de mal pour aboutir à quelque chose que des râleurs trouveraient toujours moyen de critiquer ... car le seul moyen d'avoir des choses vraiment égales, c'est l'emploi systématique du triangle équilatéral, avec donc toujours six cases autour de chaque sommet -- or l'intérêt du jeu, c'est précisément l'irrégularité et l'asymétrie, la présence de penta-hexa-heptagones, avec l'imprévisibilité qui va avec.

J'ai donc fait l'impasse sur le problème, constaté que ça n'empêchait pas du tout les gens de jouer (au pire, les pions débordent parfois un peu des cases, la belle affaire), et je me suis remémoré la sagesse de ma regrettée grand-mère pour qui le mieux était le plus souvent l'ennemi du bien. J'admets que c'est une philosophie de sale feignasse... mais bon, je suis partisan du moindre effort et j'assume!

Pieyre a écrit:J'ajoute encore une chose (j'ai l'esprit de l'escalier). Et si tu envisageais dans ta version commerciale une grille hexagonale ? C'est tout de même plus en rapport avec le triangle que ne l'est le carré... Alors il pourrait y avoir ou bien deux joueurs, ou bien quatre, ou bien six. Pour six, il suffirait de disposer de dés cubiques à six couleurs à la place des triangles bicolores. Pour quatre il est moins évident de trouver une pièce acceptable, dans la mesure où le tétraèdre ne peut reposer sur sa pointe pour montrer la couleur du joueur... Mais on doit pouvoir trouver une solution.

Merci pour l'idée.

En pratique, j'ai déjà une certaine difficulté à convaincre ne serait-ce qu'UN adversaire de jouer... ce qui fait que je ne me suis pas senti très motivé pour travailler sur une version qui me forcerait à en convaincre trois ou cinq simultanément. J'envisagerai ça... disons dès que la version à deux joueurs aura remporté le succès planétaire qu'elle mérite! (en toute modestie)

J'avoue, c'est une façon élégante de me défiler.

Au fait, la version "commerciale" (à deux joueurs: ce n'est pas le casse-tête dont il est question sur ce fil) ne se joue pas sur un carré, mais sur un rectangle; et pas sur un tore, mais sur un cylindre. En pratique, j'ai constaté que les joueurs trouvaient ça beaucoup moins abstrait, notamment les enfants.

Je suis à peu près sûr qu'on peut obtenir une grille équivalente à une grille donnée qui soit composée de triangles de même aire. Je propose en pratique la méthode suivante : on détermine le triangle d'aire maximale et, parmi les triangles qui ont un côté commun avec lui, celui qui est d'aire minimale; alors on déplace les deux sommets de leur côté commun jusqu'à les rendre égaux; et l'on itère. Je pense que cela doit converger.

... Quant à ma proposition de grille hexagonale, j'ai oublié un cas : celui de trois joueurs. Et puis qu'il y ait 3, 4 ou 6 joueurs (ou même 5 après tout), on peut toujours utiliser un dé à six couleurs, certaines couleurs ne correspondant pas forcément à un joueur effectif.

Pieyre a écrit:Je suis à peu près sûr qu'on peut obtenir une grille équivalente à une grille donnée qui soit composée de triangles de même aire. Je propose en pratique la méthode suivante : on détermine le triangle d'aire maximale et, parmi les triangles qui ont un côté commun avec lui, celui qui est d'aire minimale; alors on déplace les deux sommets de leur côté commun jusqu'à les rendre égaux; et l'on itère. Je pense que cela doit converger.

Mais cela n'aura pas qu'une influence sur ces deux cases que l'on cherche à équilibrer, mais aussi sur les autres cases ayant les points déplacés pour sommets...



Si je cherche à réduire la disproportion entre les aires 4 et 5 en déplaçant les deux points noirs, ça ne va pas affecter que 4 et 5, mais aussi 0, 1, 2, 3, 7, 8, 9 et 10... Est-on sûr que cette modification ira forcément dans le sens d'un équilibrage de toutes les surfaces? Je ne dis pas que c'est faux, mais ça ne me paraît pas démontré non plus.

Mon algorithme de constitution de grilles se contente, lui, de déplacer les deux points noirs (ainsi que le sommet commun aux cases 3, 5, 6 et 8 ) vers le barycentre du polygone qui entoure chacun d'entre eux. Ca équilibre un peu et c'est déjà pas mal... Tu es sûr de pouvoir faire mieux?

Comme ça, j'aurais pensé à déplacer les deux sommets noirs vers la gauche (enfin la normale au segment orientée vers la case de plus grande aire), de façon diminuer la disproportion entre les cases 4 et 5 (les deux ensemble, pour ne pas rendre plus aigus les angles de la case 5). Mais il faudrait en effet tenir compte des cases voisines que tu mentionnes. Alors on pourrait alterner ce déplacement avec un rapprochement de ces deux sommets noirs (dans d'autres cas ce pourrait être un éloignement).

Par ailleurs ton critère des barycentres me plaît bien, parce qu'il correspond à une formule et non à un ajustement progressif comme ce que j'envisage. Je n'ai peut-être pas bien compris mais ne serait-il pas possible de l'itérer dans la perspective de faire converger la répartition des aires ?

Sinon, je pense que le problème a déjà été traité quelque part. J'ai juste trouvé une thèse, Développement de modèles graphiques probabilistes pour analyser et remailler les maillages triangulaires 2-variétés. Elle concerne les maillages surfaciques, de façon plus générale que la question que l'on envisage sur la représentation carrée. On doit donc pouvoir trouver des méthodes plus simples. En plus il est question de remaillage et pas seulement de déplacement des sommets. Mais certaines méthodes me paraissent aller dans le sens de ce dont on discute (voir p. 30 notamment).

Toutes ces considérations théoriques sont fascinantes, et je ne renonce pas du tout à les creuser dans les jours qui viennent... Mais bon, permettez-moi de revenir quand même un peu à mon jeujeu.

J'ai entamé ce fil il y a un peu moins de deux semaines, ce qui a été amplement suffisant pour me permettre d'étudier la résolution des 34 grilles que j'ai mises à votre disposition. Je vous en redonne la liste, en vous indiquant ce que j'estime être leur degré de difficulté. C'est évalué au doigt mouillé, en fonction du mal que je me suis donné, moi-je, pour les résoudre. Comme soit dit sans vouloir vous vexer vous êtes tous débutants dans ce jeu, je pense que de votre point de vue toutes les grilles peuvent être jugées difficiles, raison pour laquelle je me propose d'en étudier en détail quelques-unes dans les jours qui viennent, par ordre de difficulté croissant.

Bon, déjà, voici l'inventaire brut de fonderie, on verra après comment s'y attaquer.

Les douze mois de l'année
janvier - Très facile (nous l'avons déjà étudiée)
février - Difficile
mars - Difficulté moyenne
avril - Difficulté moyenne
mai - Facile
juin - Difficulté moyenne
juillet - Particulier
aout - Difficulté moyenne
septembre - "Cinq ou huit"
octobre - Facile
novembre - Difficulté moyenne
decembre - Difficile (nous l'avons déjà étudiée, et avons vu que la difficulté peut venir du fait qu'on peut se braquer sur une hypothèse de résolution irréalisable)

Blanche-Neige et les sept nains
blancheneige - Difficile
atchoum - Facile
dormeur - Difficile
grincheux - Difficulté moyenne
joyeux - Difficulté moyenne
prof - "Cinq ou huit"
simplet - Difficulté moyenne
timide - Difficulté moyenne

Les présidents de la Cinquième République
degaulle - Difficulté moyenne
pompidou - Difficulté moyenne
giscard - "Cinq ou huit"
mitterrand - Difficulté moyenne
chirac - Particulier (nous l'avons déjà étudiée)
sarkozy - Difficulté moyenne
hollande - Difficulté moyenne

Les sept jours de la semaine
lundi - Facile
mardi - Difficulté moyenne
mercredi - Difficulté moyenne
jeudi - "Cinq ou huit"
vendredi - Difficulté moyenne
samedi - "Cinq ou huit"
dimanche - "Cinq ou huit"

Il faudra que je vous explique ce que j'entends par "cinq ou huit" -- dans l'immédiat, ne vous attaquez pas à ces grilles, dont la difficulté est un peu spécifique (c'est à la fois plus simple et plus compliqué).

Bon. Commençons par les grilles faciles... J'ai noté que la grille "mai" était facile, ça doit être vrai:



Voyons voir... Ah oui, en effet, elle est facile et même très facile, mais elle n'a pas grand mérite à ça parce que c'est une grille insoluble.

Entendons-nous. A strictement parler, il n'y a pas de grille Triancey insoluble, il y a toujours un optimum pour toutes les grilles quelles qu'elles soient. Mais certaines ne peuvent pas être résolues de façon classique, en sacrifiant deux cases au départ et à la fin un polygone convexe qui sera un pentagone, un hexagone ou un heptagone. Eh bien, sur la grille que je vous présente aujourd'hui, on ne peut pas atteindre un tel optimum. En revanche, on peut tout de suite comprendre pourquoi.

Et c'est très simple. La grille a 40 cases. Donc, si j'en sacrifie deux au départ, il en restera 38, et 38 est un multiple de 3 majoré de deux, donc le polygone final devrait en théorie être lui-même un multiple de 3 majoré de deux, donc idéalement un pentagone.

Y a-t-il des pentagones sur cette grille? Oui-da: en haut à gauche, il y en a un qui a une tête de carré (9, 1, 12, 10, 11), en bas il y en a un joli (26, 20, 29, 27, 28), et il y en a encore un réparti de part et d'autre des bords gauche et droit (15 et 19 à gauche, 18, 23 et 24 à droite). Sauf erreur de ma part, c'est tout... et ça n'est pas assez.

Car, nous l'avons déjà vu, l'avant-dernier coup d'une partie à score optimal "classique" doit être joué sur un pentagone. Je rappelle pourquoi: l'avant-dernier coup doit être joué sur un polygone marié au polygone final, sur les grilles Triancey les polygones mariés le sont presque toujours en ayant deux cases en commun, or pour que l'avant-dernier coup soit gagnant, il faudrait qu'il prenne trois cases simultanément à l'exclusion des deux cases appartenant aussi au polygone final, trois jaunes + deux partagées avec le polygone final = 5, donc l'avant-dernier coup doit être joué sur un pentagone. Toujours, toujours, toujours.

Enfin, sauf exception, comme sur la grille "mai" qui nous occupe, quand il faut se résoudre à un score optimal moins bon que le score optimal "classique".

Y a-t-il sur notre grille "mai" deux pentagones mariés sur lesquels nous pourrions jouer l'avant-dernier et le dernier coup? Nenni-da. Il faut donc revoir nos ambitions à la baisse, et terminer non pas sur un pentagone, mais sur un ensemble de huit cases. Et comme vous le voyez, on peut s'en rendre compte sans même avoir eu besoin de cliquer la moindre case, suffit d'ouvrir ses yeux et de compter.

Et terminer sur huit cases, c'est souvent très facile et ça l'est effectivement sur cette grille. Même qu'il y a au moins trois façons également élégantes de le faire.

Saurez-vous en trouver une?

Bon, allons-y, résolvons cette grille "mai".

Moyen le plus simple et de très loin: prendre un couloir... et pas n'importe lequel: un couloir de huit cases. Il y en a un beau qui crève les yeux dans la colonne de gauche. Et ça peut nous donner, par exemple: 1 20 11 4 13 27 28 37 21 24 38 14... et le dernier, coup, comme très souvent, est indifférent: quoi qu'on fasse ensuite, on prendra le couloir de huit cases.

Moyen assez classique également envisageable: terminer sur un octogone. Où y a-t-il un octogone dans cette grille? Sauf erreur de ma part, il n'y en a qu'un: l'ensemble des cases 15, 10, 11, 16, 19, 25, 26 et 20. On peut classiquement s'en servir pour dessiner un cavexe pas trop dodu... Par exemple, vous pouvez le photographier mentalement après avoir cliqué sur les cases 15, 16, 26, 25, 10 (bleu), 1, 33 (jaune): voici un cavexe très facile à photographier mentalement, vu qu'il est coincé contre le bord gauche.

Alors y a plus qu'à, allons-y: 2 5 35 27 37 21 17 24 38 14 (hors du cavexe), puis 33 1 10 (dedans).

Moyen le plus élégant à mon sens: terminer sur les deux quadrilatères... ce qui suppose déjà qu'on les ait repérés: 1, 2, 3, 12 d'une part, 6, 7, 37, 38 d'autre part. A vrai dire, j'ai essayé et pas réussi, mais mon solveur, lui, y arrive très bien: 29 23 30 19 26 10 34 4 39 11 13 9 37 2. Enfoirée d'intelligence artificielle, quel talent elle a.

Moyen moche juste pour faire le kakou et montrer ma virtuosité: terminer sur un hexagone marié à un quadrilatère (6 + 4, moins 2 cases en commun = 8 ). On doit pouvoir le faire en dessinant un cavexe ainsi: 6 7 37 35 4 (bleu), 14 31 23 22 (jaune)... et voilà un joli cavexe facile à photographier mentalement car coincé contre le côté droit. Appliquons cette belle stratégie, et ça nous fait par exemple: 28 11 20 25 15 1 2 32 (hors du cavexe), 22 23 31 14 35 37 (dedans).

Quand on vous dit que ça n'est pas bien malin, en fait...

Esprit de l'escalier... Quand nous avons parlé de la possibilité d'inscrire un réseau hexagonal sur un tore carré, nous avons cru pouvoir affirmer qu'il y avait plusieurs façons de décrire le même réseau. Eh bien, c'était aller un peu vite en besogne...



... car ces deux réseaux, s'ils sont effectivement tous deux constitués exclusivement d'hexagones, sont quand même différents. A gauche, nous avons, réparti autour des quatre coins, un hexagone constitué des cases 0,4,7,3,23,20 -- qui n'existe pas à droite; et à droite, nous avons, réparti autour des quatre coins, un hexagone constitué des cases 20,15,11,7,12,16, qui n'existe pas à gauche. Les autres cases ont pourtant l'air d'être disposées rigoureusement de la même façon les unes par rapport aux autres et autour des sommets.

En fait, à gauche, le réseau hexagonal est inscrit parallèlement à un axe du tore, alors qu'à droite, il est torsadé.

C'est prise de tête, hein?

Oui, c'est prise de tête pour se représenter tout ça sur le tore.
Si tu tournes le réseau de gauche de 90°, tu obtiens des hexagones orientés dans l'autre sens, mais avec le même parallélisme. Si tu tournes celui de droite de 90°, tu obtiens la torsade inverse (enfin si ma tête n'est pas trop prise).

Notre problème du jour sera la grille "octobre" (pardon de hurler, mais avec les images cette ligne passait inaperçue).



Je l'ai déclarée facile dans mon inventaire... or en la refaisant je la trouve, somme toute, assez rétive et récalcitrante, la coquine. Je l'ai peut-être déclarée telle parce qu'il y a un cavexe concis et facile à photographier mentalement qui me saute aux yeux... mais sans mon entraînement je doute que vous partagiez cette impression.

Allez, procédons avec ordre et méthode. C'est une grille de 38 cases, donc je dois terminer sur un hexagone (38 - 2 cases sacrifiées au début = 36, qui est un multiple de 3, donc le polygone final doit être un multiple de 3). Comme nous savons que l'avant-dernier coup doit être joué sur un pentagone (reportez-vous aux épisodes précédents), nous cherchons donc sur cette figure un hexagone marié à un pentagone. Et justement (mais ça, c'est l'entraînement), je repère du premier coup d'oeil un hexagone bigame, marié à deux pentagones, que demande le peuple:



Et à partir de là faudrait vraiment être une moule pour ne pas voir qu'on peut construire un joli cavexe très facile à photographier mentalement car coincé contre le côté gauche. Vous pouvez le reconstituer vous-mêmes par la séquence de coups 8,17,9,15 (bleu), puis 1,22,28,33 (jaune).



Jusque là, comme dirait mon oncle (un fameux bricoleur), c'est vraiment de la tarte. En théorie, y a plus qu'à. Eh bien, essayez... Mais je vous préviens, le petit quadrilatère 31, 35, 37, 36, en bas à droite, va un peu vous casser les pieds... ou orienter votre réflexion, c'est selon.

De même qu'on reconnaît les bons joueurs d'échecs à leur façon de jouer les pions, on reconnaît les bons joueurs de Triancey "partrois" à leur façon de se débarrasser des quadrilatères.

Amusez-vous bien, solution en fin d'après-midi (mais d'ici là, je vous invite évidemment à mettre vous-mêmes fin au suspense -- ou à me montrer que vous pouvez imaginer des solutions encore nettement plus simples).

Bon. Nous parlons donc de la résolution de la grille "octobre". Voici la solution que j'ai trouvée à partir du cavexe suggéré dans le post précédent:

34 27 35 7 19 4 13 18 (hors du cavexe), 33 28 22 1 9 (dedans).

En voici une variante, issue, elle, du brillant cerveau artificiel de mon solveur:

19 18 25 14 36 4 35 31 (hors du cavexe), 33 32 2 23 8 (dedans).

Lequel solveur m'a d'ailleurs fait observer que d'autres cavexes étaient envisageables:



avec les séquences de coups suivantes:

cavexe0: 19 37 27 7 21 8 13 24 12 23 34 33 (11).
cavexe1: 25 11 23 16 20 31 32 36 29 3 2 6 (13).
cavexe2: 19 5 12 11 25 35 22 7 37 28 32 2 (9).

Ce sont des solutions informatiques, pas forcément faciles à trouver pour un cerveau humain. Cela dit, vous pouvez quand même vous inspirer des méthodes employées pour se débarrasser dès le début de partie de ce sale pervers de quadrilatère, tout en bas à droite, qui a dû prendre un malin plaisir à faire foirer tous vos efforts.

A demain!

Juste une petite proposition technique : ne crois-tu pas qu'il serait utile, quand on vient de cliquer sur une case et qu'on veut revenir en arrière, de pouvoir cliquer à nouveau sur cette case (visible grâce à la mise en évidence de son pourtour) plutôt que de déplacer le curseur jusqu'au bouton adéquat ? Mine de rien, quand on essaie systématiquement toutes les cases libres, cela ferait gagner du temps et surtout on ne risquerait pas d'oublier où l'on en était.

Pieyre a écrit:Juste une petite proposition technique : ne crois-tu pas qu'il serait utile, quand on vient de cliquer sur une case et qu'on veut revenir en arrière, de pouvoir cliquer à nouveau sur cette case (visible grâce à la mise en évidence de son pourtour) plutôt que de déplacer le curseur jusqu'au bouton adéquat ? Mine de rien, quand on essaie systématiquement toutes les cases libres, cela ferait gagner du temps et surtout on ne risquerait pas d'oublier où l'on en était.

Je ne te garantis pas que je vais le faire tout de suite, mais je vais y réfléchir. J'ai un peu peur que ça perturbe ceux qui n'auront pas lu le mode d'emploi -- et qui constituent toujours une forte proportion des utilisateurs! Mais ça pourrait en effet être intéressant, particulièrement pour les utilisateurs de tablettes et de smartphones, avec des écrans si petits que la grille et les touches de magnétoscope n'y tiennent pas simultanément.

Cela dit -- ce n'est pas pour me défiler --, je pense que ce n'est pas une bonne idée d'"essayer systématiquement toutes les cases libres": pour devenir bon à ce jeu (et à ses variantes), il est capital d'apprendre à anticiper, et à éliminer d'emblée un paquet de stratégies qu'on peut sans même les tester identifier comme vouées à l'échec. Il se trouve que cette façon de penser (éliminer ce qui ne peut que foirer pour tomber directement sur ce qui marche) correspond à mon tempérament (j'aime bien mon jeu!), mais je pense que dans l'absolu c'est préférable: c'est un jeu où la stratégie doit primer sur la tactique, et c'est notamment pour ça que j'insiste lourdement sur la nécessité de fantasmer un cavexe avant d'attaquer vraiment la partie.

Mais bien sûr, pour en arriver à réfléchir en termes stratégiques plutôt que tactiques, il faut déjà avoir acquis une bonne maîtrise de la tactique. Est-ce que l'interface que tu préconises y aiderait? Je vais y réfléchir.

Oui, tu as raison : ce n'est pas une bonne idée d'essayer les configurations de façon systématique. Mais il faut pardonner à un simple néophyte. Je ne me suis appliqué vraiment qu'à une seule de tes grilles; j'ai commencé en raisonnant, et puis à la fin j'ai essayé tout, ou quasiment, en traçant même à la main un arbre des configurations déjà explorées; et cela a marché plus rapidement que de me poser des questions relatives à la meilleure stratégie.