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

Bonjour, ça va? Le problème du jour sera la grille "juillet".



Je doute que vous vous en souveniez, mais dans l'inventaire commenté des grilles disponibles que j'ai publié il y a bientôt deux mois (mon Dieu, comme le temps passe), cette grille "juillet" était notée comme particulière. Aha. Et qu'est-ce qu'elle a-t-elle donc de particulier, la coquine?

Moi, ce que je remarque d'emblée sur une grille pareille (je ne sais pas l'effet que ça vous fait à vous), c'est qu'elle comporte en plein milieu une ligne horizontale presque parfaite (au-dessus des cases 24, 26, 27) alors qu'il est rarissime de rencontrer de tels alignements ailleurs que sur les bords. Eh bien, la particularité... ça n'est pas ça, car ça, c'est une particularité qui n'a aucune incidence sur la façon de résoudre la grille, donc en fait on s'en fout complètement, c'est un pur hasard sans signification et sans conséquence. Ce qu'il faut remarquer, c'est... autre chose.

Quoi donc?

Eh bien non, je ne vous le dirai pas. Il y a de cela fort longtemps, quand j'essayais de devenir un bon joueur d'échecs (je vous rassure, j'ai totalement échoué), je me suis tapé la lecture d'un bouquin d'un nommé Alexandre Koblentz (ça s'appelait "l'Entraînement aux échecs - la Route du succès"), qui était entraîneur de l'équipe soviétique d'échecs, excusez du peu. Vous êtes trop jeunots pour vous en souvenir, mais il n'y avait guère qu'un domaine sportif où les Soviétiques excellaient sans avoir recours au dopage, et c'était le jeu d'échecs, ils en étaient très fiers et le mettaient particulièrement en valeur ("Il n'y a pas beaucoup d'occasions de démontrer que le communisme a du bon", raillait le champion d'échecs et dissident soviétique Victor Kortchnoï). Ah, ouais, quand les Popov jouaient aux échecs, personne ne rigolait, un moujik derrière un échiquier, ça vous faisait penser la même chose que Bruce Lee quand il empoignait son nunchaku: "Putain, je suis foutu, j'ai aucune chance".

Eh bien, dans son bouquin, Koblentz publiait classiquement des tas de grilles d'échecs, mais il ne les accompagnait jamais des mentions traditionnelles "les blancs jouent et font mat en trois coups" ou "les blancs jouent et font nulle", et il affirmait que c'était à la base du succès des Popov: "Quand vous jouez aux échecs, vous n'avez pas à côté de vous un Père Noël qui vous indique ce qu'il faut faire." C'était très matérialiste dialectique et athée, mais ça me paraissait plein de sens. Ça ne m'a absolument pas aidé à cesser d'être le joueur d'échecs archi-nul que je suis toujours, mais j'ai quand même retenu la leçon et je ne vous dirai pas ce qu'il faut faire sur la grille du jour, na. Faudra que vous le trouviez tout seuls. Je ne vous donne qu'un indice: si vous ne remarquez rien de particulier sur cette grille, ben ça veut dire que vous n'y atteindrez pas l'optimum. Et l'air de rien, vous dire ça, c'est déjà vous aider beaucoup!

Bon, résolvons cette grille "juillet" de façon classique. C'est exactement ce qu'il faut faire... sauf que.

La grille comporte 42 cases. Donc, si on en sacrifie deux (bleues) au départ pour initier la série de coups gagnants (jaunes), il va en rester quarante, qui est égal à un multiple de trois majoré de un. Par conséquent, après la série illimitée de coups gagnants (jaunes), il faudra achever la prise complète de la grille sur un polygone convexe dont le nombre de cases sera lui-même égal à un multiple de trois majoré de un, autrement dit un heptagone.

Et juste avant ce dernier coup (qui prendra le polygone convexe en bleu), il faudra prendre trois cases (en jaune, donc) dans un pentagone marié à ce polygone final (en application du fameux théorème de l'avant-dernier coup).

Rien de plus classique, n'est-ce pas?

Où peut-on trouver sur cette grille un heptagone marié à un pentagone? Par exemple là... Allez, pour le même prix, je vous dessine carrément tout le cavexe:



Bien bien bien, nous avons une stratégie à notre disposition, il va seulement falloir ne pas se laisser empistrouiller par les deux quadrilatères 18, 19, 20, 25 d'une part, 29, 30, 35, 36 d'autre part.

Allons-y gaiement: 19 2 (en bleu), 17 0 26 (et un quadrilatère de zigouillé, un!), 15 29 36 (et un autre quadrilatère de zigouillé, ouf), 32 41 (en jaune), et zou, nous avons dessiné l'inverse du cavexe que nous visons:



Yapuka terminer comme prévu sur le cavexe visé: 31, 37, 4, 12.



Bon, ben c'est parfait, plus orthodoxe tu meurs: deux cases bleues sacrifiées au début, un polygone convexe sacrifié au dernier coup, tout le reste en cases jaunes, c'est-il pas un bel optimum de cases jaunes, ça madame?

Eh bien non! On peut faire mieux!

Je vous avais bien dit que si l'on ne remarquait rien de particulier sur cette grille on n'y atteindrait pas l'optimum...

Qu'aurait-il fallu remarquer?

L'intégralité du raisonnement publié dans le post précédent était valide, sauf une conclusion hâtive, qui aurait quand même été valable sur l'immense majorité des grilles -- raison pour laquelle on a généralement tendance à ne pas s'interroger sur elle.

Le "polygone convexe dont le nombre de cases est égal à un multiple de trois majoré de un", et sur lequel on va jouer le dernier coup (perdant) de la partie, est très généralement un heptagone (il va de soi que ce que je dis là est valide sur une grille à 42 cases, ou 36, ou 48, mais pas sur autre chose, ne me faites pas dire ce que je n'ai pas dit, on n'atteint pas systématiquement le score optimal en terminant sur un heptagone, ça dépend du nombre de cases; si ça ne vous paraît pas évident, révisez les pages précédentes). Très généralement, mais dans quelques cas rares et particuliers, comme sur cette grille "juillet" qui nous occupait hier, il peut parfois être avantageusement remplacé par un quadrilatère.

7 = 2 * 3 + 1, certes, mais 4 = 1 * 3 + 1...

Ben ouais, ça tombe sous le sens... Enfin, pas tant que ça, en fait. Par exemple, sur la grille qui nous occupe, il y a deux quadrilatères, et un seul des deux (18, 19, 20, 25) peut être employé pour jouer le dernier coup d'une partie à score optimal, et cela aussi tombe sous le sens: parce que lui seul est marié à un pentagone, indispensable en vertu du théorème de l'avant-dernier coup dont je ne soulignerai jamais assez l'importance.

Et en plus, ce n'est pas tout: pour atteindre un score optimal en terminant sur un quadrilatère, il faut non seulement un quadrilatère (toutes les grilles n'en comportent pas, loin de là), un quadrilatère marié à un pentagone (et c'est assez rare; regardez avec quoi est marié le quadrilatère 29, 30, 35, 36 de la même grille: un octogone, un hexagone et deux heptagones), mais en plus, en amont de ce couple quadrilatère-pentagone déjà fort rare, il faut encore pouvoir jouer un coup gagnant, ce qui n'est guère possible que si le pentagone dont nous venons de parler est lui-même marié à un autre pentagone. Et avant cet antépénultième coup gagnant, il faudra encore trouver un troisième coup gagnant, ce qui n'est pas nécessairement évident non plus. Bref, un score optimal s'achevant sur un quadrilatère exige la réunion de plein plein de conditions toutes rares... Autant dire que ça n'arrive pratiquement jamais -- raison pour laquelle je n'en ai pratiquement jamais évoqué la possibilité dans les premières pages de ce fil, ça vous aurait embrouillés (mais maintenant vous êtes de grands garçons, et je peux vous dire des choses que je n'aurais pas dites aux élèves de sixième).

Ben sur la grille "juillet", par exception, toutes ces conditions invraisemblables sont réunies, et ça mène donc à la construction d'un cavexe... relativement évident une fois qu'on sait qu'il est là:



Eeeh ben oui, ce n'était même pas caché: le quadrilatère 18, 19, 20, 25 est marié au pentagone 10, 11, 19, 20, 21, lui-même marié au pentagone 4, 5, 10, 11, 12, lui-même marié à un troisième pentagone (à cheval sur les bords inférieur et supérieur et qui pour cette raison ne se voit pas beaucoup) 37, 38, 3, 4, 5. Et une fois qu'on a repéré toutes ces circonstances vraiment très très très particulières, ben faudrait vraiment être une moule pour n'avoir pas idée d'achever le cavexe par les cases 26, 30 et 36. Et voilà, comme disent les Anglais.

Bon, OK, c'était possible, mais fallait vraiment le voir, c'était vraiment la seule et unique possibilité d'obtenir le score optimal sur cette grille, allez-vous me dire? Que nenni, vous n'aurez même pas cette circonstance atténuante: ce cavexe est remarquablement concis, vertical et filiforme, mais ce n'est pas le seul exploitable, et mon solveur (qui adore humilier les simples mortels) en a repéré pas moins de quatre un peu plus massifs et nonobstant tout à fait exploitables:



Donc, non non non, pas d'excuse, la solution d'hier, qui s'achevait sur un heptagone, ne peut pas prétendre qu'elle est quand même "pas si mal que ça": vu qu'elle ne représentait pas l'optimum, elle ne pouvait absolument pas prétendre être une solution "honorable", elle était erronée et elle vaut la note de zéro tout rond, nyark nyark nyark.

Solutions complètes un peu plus tard (voire nettement plus tard).

Et voici donc des solutions pour la grille "juillet", l'une des rares grilles sur lesquelles le score optimal est égal au nombre de cases diminué de seulement six cases: deux pour initier la série de coups gagnants, et un simple quadrilatère au dernier coup de la partie.

Solutions complètes:

Ça se tire, les aminches! Il n'y a plus que cinq grilles de mon inventaire que je n'aie pas encore traitées, et parmi elles, il n'y en a plus qu'une que j'aie classée comme de "difficulté moyenne". Eh bien, nous allons nous en occuper aujourd'hui.

Or donc, le problème du jour sera la grille "vendredi".



Je viens de la résoudre en deux coups de cuiller à pot, a priori ça n'a pas l'air bien malin. Bon courage.

Je traîne pour vous donner les solutions de la grille "vendredi", mais c'est parce qu'elles sont très nombreuses, trop même, avec des cavexes parfois très inutilement massifs, et que plutôt que de vous en faire un inventaire exhaustif j'essaye au moins de m'assurer que je n'en ai raté aucune qui soit vraiment élégante. Perfectionnisme quand tu nous tiens...

Vu que c'est une grille de 42 cases, ça veut dire qu'il faut terminer sur un heptagone marié à un pentagone (j'ai la flemme de vous le réexpliquer ce coup-ci, cherchez dans les épisodes précédents), or les cinq heptagones de cette grille remplissent cette condition, vous pouvez vérifier. Rien d'étonnant, dans ces conditions, que les solutions abondent et qu'il ne leur soit pas nécessaire d'être concises ni élégantes.

Je suis décidément à la bourre, et je ne viendrai pas à bout de la grille "vendredi" aujourd'hui, tellement les solutions valides y abondent. Voici quand même, pour vous faire patienter, une petite collection de cavexes valides et intéressants, tous exploitables pour aboutir à une solution optimale (deux cases isolées bleues, onze coups gagnants jaunes, un heptagone final bleu):



Je vous les ai classés en cinq rangées, chaque rangée étant consacrée à un heptagone particulier. Pour chacun d'entre eux, je vous ai mis au moins un cavexe horizontal et un cavexe vertical, et j'ai parfois ajouté des variantes qui m'ont paru intéressantes.

Et l'air de rien, tout ça, c'était énormément de travail... donc je n'ai pas trop scrupule à être à la bourre.

Solutions complètes demain. S'il plaît à Dieu.

Je me casse le tronc à essayer de faire un tour complet des solutions possibles sur chaque grille étudiée -- pour deux raisons. La première, c'est que je me conforme à la méthode d'un copain généralement de très bon conseil:

René Descartes a écrit:faire partout des dénombrements si entiers et des revues si générales, que [l'on puisse être] assuré de ne rien omettre.

... et la seconde, c'est de vous inciter à la persévérance. Quand vous avez repéré un polygone final ayant le nombre de cases qui va bien, et marié à un pentagone comme il se doit pour atteindre le score optimal théorique, il reste à élaborer un cavexe rondouillard sur cette base. C'est rarement facile et ce n'est pas toujours possible, hélas, c'est pourquoi je crois important de ressasser aux débutants que même si ça n'est pas toujours possible c'est quand même possible dans de très nombreux cas (dans la plupart, à vrai dire), raison pour laquelle il faut s'acharner beaucoup de peur de se décourager trop tôt. Je sais, c'est prêchi-précha, ce que je vous dis là, c'est ma mentalité de vieux cureton qui ressort, mais les vieux curetons ne disent pas que des conneries et j'en ai connu qui m'ont vraiment aidé à construire mon âme comme j'essaie de vous aider à construire la vôtre, parfaitement (quoi, vous n'aviez pas encore compris que ce fil était un long prêche pour les quatre règles de la raison du père Descartes? c'était pourtant bien mal caché...).

Par ailleurs, une erreur de débutant (que j'ai commise bien des fois, évidemment) est de se dire "pisque ça n'a pas l'air facile avec ce polygone final-ci, je vais le laisser tomber et essayer avec ce polygone final-là". Ce n'est pas forcément une bonne stratégie de papillonner ainsi, ça dépend des grilles. Disons pour vous donner une idée que n'importe lequel des treize cavexes que je vous ai montrés hier pouvait être trouvé en environ cinq minutes; si vous consacrez une minute trente à chacun d'entre eux dans l'espoir d'en rencontrer un facile, vous travaillerez 13 * 1,5 = une vingtaine de minutes sans obtenir de résultat, alors qu'en vous acharnant sur une seule idée vous auriez trouvé une solution (pas forcément élégante) en quatre fois moins de temps. C'est une des choses que l'on apprend en jouant à ce jeu: à jauger au doigt mouillé combien de temps il faut s'acharner sur une idée médiocre, mais valide, avant de se mettre en quête d'une meilleure, laquelle, même si elle existe, n'est pas forcément plus facile à trouver. C'est tout un art, et comme tous les arts, il demande de la pratique, de l'entraînement et de la persévérance et il va arrêter de nous faire chier le vieux cureton?

Bref. Je reviens aux cavexes publiés hier soir. Ils sont de qualité inégale. Le 1a, le 3a et surtout le 4a sont vraiment concis et par là-même élégants, ce sont mes préférés. Le 3a bis est assez quelconque, mais je l'ai trouvé (avec mes années d'entraînement) au bout de seulement quelques dizaines de secondes d'acharnement et vous verrez que vous finirez par en être capables vous aussi, petits scarabées. Et ne méprisez pas le 2b ni même le 1b_bis: même s'ils sont très massifs, obèses, "gorditos" comme on dirait en Bolivie, ils présentent le gros avantage d'être bien carrés et donc très faciles à photographier mentalement, donc ils représentent une autre forme d'élégance. Quant aux autres, ben ma foi ils ont l'énorme mérite d'exister (comme mon 3a bis), et je pense que vous pouvez accepter comme philosophie de l'existence que la meilleure solution est la première qui marche (philosophie inspirée du petit monde linuxien, où l'on discute à n'en plus finir des mérites comparés de quantité d'outils complètement interchangeables et disposant pourtant chacun de petites chapelles de fanatiques qui ne voudraient en essayer un autre sous aucun prétexte).

J'arrête là mon prêche, même que c'est pas dommage. C'est égal, méditez tout ceci en votre coeur, mes bien-aimés, je vous assure que ça pourra vous servir dans des contextes très différents.

Solutions complètes (et abondantes):

A part ça, bonne fête du Travail.

Le problème du jour sera la grille "blancheneige".



Je tue tout de suite le suspense: cette grille, que je vous ai classée à bon droit comme "difficile", aurait aussi pu être désignée comme "particulière", tout comme la grille "juillet" que nous avons vue il y a rien de temps et pour la même raison: l'optimum y est atteint en terminant sur un quadrilatère (marié avec un pentagone, évidemment, en vertu du théorème de l'avant-dernier coup, reportez-vous aux épisodes précédents).

C'est la même chose, sauf que c'est plus dur. Ou pas, d'ailleurs...

Ce qui est sûr, c'est que sur la grille "juillet", nous avions trouvé pas moins de cinq cavexes inversibles. Eh bien, sur la grille "blancheneige" qui nous occupe aujourd'hui, vous n'aurez pas cet embarras du choix, car elle entre dans la catégorie ra-ris-sime des grilles qui n'admettent qu'un seul cavexe inversible.

Lequel, bien évidemment, ne saute pas aux yeux, perdu qu'il est au milieu des milliers de milliards de solutions envisageables. Allez, je vais être honnête: moi, je ne l'ai pas vu, j'ai crié grâce... et c'est seulement en regardant travailler mon solveur que je me suis rendu compte que cette solution existe et est unique.

Mais ça, ça ne démontre pas que c'est difficile, ça démontre seulement que je suis un âne bâté.

Aussi, je vous dis comme tous les bons pédagogues: "Faites ce que je dis, ne faites pas ce que je fais." Vous, ne baissez pas les bras. Demandez-vous, avec rigueur et méthode: où que c'est-il que je peux jouer le dernier coup? et l'avant-dernier? et l'antépénultième? et celui d'avant? et celui d'encore avant? Dans l'immense majorité des cas, sur la grille "blancheneige", la réponse à chacune de ces questions est unique ou presque (il suffit de très peu raisonner pour éliminer les hypothèses foireuses).

Donc si vous raisonnez ri-gou-reu-se-ment vous devriez tomber directement sur la solution miraculeuse qui va bien, qui atteint l'optimum, qui est élégante et efficace... La démarche intellectuelle est beaucoup plus proche de l'enquête de police minutieuse et méthodique que de l'intuition géniale. Ne vous prenez pas pour Sherlock Holmes, drafaillez afec méthôde et distzipline... comme l'inspecteur Derrick, allez: observez les indices, interrogez les témoins, relevez les contradictions... et vous y arriverez tout droit. Cette grille n'est difficile que si on la croit telle, comme j'ai eu la sottise de le faire. Croyez que le résultat est à votre portée et vous l'atteindrez. Bêtement, c'est-à-dire de la seule façon intelligente qui soit à votre disposition en l'occurrence.

Bon, allez, entamons la résolution de cette fameuse grille "blancheneige" avec ordre, méthode et discipline... et avec plein d'images sous spoiler pour vous faire honte de n'avoir pas trouvé la solution tous seuls tellement elle était visible... non, pas comme le nez au milieu de la figure, mais vraiment pas plus difficile à repérer que Mars et Jupiter dans un ciel étoilé: avec un minimum de connaissances, on y arrive sans peine (vous dit Petitagore qui n'y est pas arrivé tout seul... mais ma nullité n'excuse nullement la vôtre, bande de petits salopards!).

Primo, sur quel polygone faut-il terminer la résolution de cette grille? Je vous l'ai déjà dit dans le post précédent, mais maintenant je l'explique (une énième fois...). Cette grille a 42 cases. Comme au départ il faudra que j'en sacrifie deux, ce qui est presque universellement le cas, il m'en restera 40, or 40 = 13 * 3 + 1, un multiple de trois majoré de un, donc le nombre de cases du polygone final devra être... la même chose: un multiple de trois majoré de un. Donc il devra avoir sept cases (= 2 * 3 + 1) ou, mieux, quatre cases (= 1 * 3 + 1), ce devra être un heptagone ou, mieux, un quadrilatère.

Il est rare qu'on puisse atteindre le score optimal en terminant sur un quadrilatère; rare, mais pas exclu. Déjà, y a-t-il un quadrilatère sur cette grille? Mais ouvrez vos yeux, pétard!

Vous auriez dû le voir...:

Il y a deux quadrilatères sur cette grille, mais un seul nous intéresse. Lequel?

Agnan?

-- Çui qu'il est marié avec un pentagone, m'sieur.

Pourquoi?

-- A cause du théorème du dernier coup, m'sieur.

A cause du théorème de l'avant-dernier coup, bougre d'âne! Mais putain, vous allez finir par me l'apprendre, ce putain de théorème de mes couilles, sacré nom de Dieu de bordel de pute à queue!

Bon, on avance. Et où qu'il est-il, le quadrilatère marié sur un pentagone?

Hein?

-- Y en a pas, m'sieur.

Non mais c'est pas vrai, mais quelle bande de nullards...

Et ça, c'est une photo du yéti?:

Ah ben ouais, fallait faire l'effort de réfléchir. Pauvres chéris, vraiment je vous persécute.

Et en amont de ce quadrilatère marié à un pentagone, est-ce qu'on peut prendre trois cases?

Je ne vous le demanderais pas si la réponse n'était pas oui, alors trouvez-moi où, pétard!

Eh ben ouais, évidemment...:

Bon, jusque là j'ai vraiment été d'une indulgence extrême, mais je vous jure que si vous ne me dites pas tous et immédiatement quel coup on peut jouer en amont de ce coacervat, je demande votre exclusion définitive du cours de Triancey partrois, et j'exigerai de voir vos parents individuellement pour qu'ils sachent bien quelle bande de fumistes et de nullards vous êtes.

Alors, vous me le trouvez, ce coup gagnant qu'on peut jouer en amont, bordel?

Ah, quand même!:

Bon, là, j'admets, il y a une difficulté, oh la la que c'est difficile, en amont de ce coacervat vous avez le choix entre deux coups gagnants, tout ça, oui. Deux coups possibles. Vous allez évidemment commencer par le mauvais qui ne vous mènera à rien (si vous cliquez sur 23 pour prendre 23, 24 et 32, eh bien vous ne pourrez pas jouer un coup gagnant en amont de ça) et donc vous aurez peut-être seuls l'idée géniale, après avoir échoué sur la première possibilité, de tester la seconde... Prenez votre temps, j'ai que ça à foutre...

Ils y sont arrivés, c'est inespéré!:

Peste, vous m'impressionnez. En moins d'une demi-heure, vous avez réussi à repérer les quatre seuls coups gagnants qu'on pouvait jouer en amont du quadrilatère final. Ah, bel effort, chapeau. Donc des champions comme vous vont peut-être réussir à me trouver en moins d'une heure le coup pas complètement intuitif qu'il faudrait jouer maintenant pour achever le cavexe? Je serai indulgent, c'est pas tout à fait rigoureusement complètement évident, mais je vous assure que c'est quand même à la portée du concierge du collège, même quand il rentre bourré à cinq heures du mat, donc vous allez peut-être y arriver aussi. Mais surtout, prenez votre temps.

Aaaaaa y est, ils ont trouvé!:

Je vous ai un peu houspillés, soit, et même je veux bien admettre qu'il était pas tout à fait évident, ce cavexe, vu que l'espèce de faux tenon constitué par les cases 5 et 13 empêche de lui conférer ce sympathique aspect rondouillard qu'ont habituellement les cavexes inversibles. C'est vrai.

Mais pétard rendez vous compte que le raisonnement vous y menait TOUT DROIT! Tout droit! Vous pouviez pas le rater, c'était un éléphant dans un couloir!

-- Mais vous nous avez dit que vous-mêmes vous ne l'aviez pas vu, m'sieur.

Ta gueule, Agnan. Ce n'est pas fini! Maintenant il faut me trouver une solution complète sur la base de ce cavexe qui nous a demandé tant d'efforts. Donc, au boulot!

Au risque de vous embrouiller, je crois qu'avant de publier les solutions il est intéressant que je vous montre un autre cavexe même s'il n'est pas orthodoxe:



Le cavexe que nous avons élaboré dans le post précédent était inversible mais pas rondouillard (il y avait un faux ensemble tenon-mortaise, les cases 5 et 13 faisant office de tenon, les cases 4, 11 et 12 de mortaise)... eh bien, celui que je vous montre ci-dessus rétablit l'équilibre: car lui, il a beau être rondouillard... il n'est pas inversible.

C'est très curieux, je n'avais encore jamais réfléchi à ce genre de configurations et je me demande s'il serait facile d'en trouver d'autres exemples. Mais j'ai constaté que le solveur passait très souvent par ce cavexe, qu'il atteint le score optimal avec lui aussi facilement qu'avec le précédent, et en plus celui-ci a un aspect rondouillard de très bon aloi.

Cela dit, il n'est pas orthodoxe: pour le construire, il va falloir employer un coup non inversible (par exemple: 29, 20, 21 -- trois coups bleus prenant quatre cases --, 41, 28, 25, 39, 18 -- non inversible --, 22), et si vous l'employez pour aboutir au score optimal, vous devrez symétriquement y jouer un coup comportant un tenon. C'est un de ces cas où mon solveur me laisse pantois par l'élégance des astuces qu'il imagine.

Je vous recommande d'y réfléchir un peu avant de donner votre langue au chat.

Solutions complètes:

Et maintenant, nous allons plancher sur la grille "samedi". Je ne vous dis pas que ce sera le problème "du jour"... car des circonstances familiales totalement indépendantes de mes gamberges triangulo-toriques risquent de m'accaparer un peu dans les jours qui viennent, donc il est possible que ce fil prenne un peu de retard (voyez-y une occasion de réviser les pages précédentes!). Toujours est-il que la grille "samedi", la voici:



Elle a 46 cases, 46 = 2 + 44 (deux cases bleues sacrifiées au début), et 44, c'est un multiple de trois majoré de deux, donc il faut jouer le dernier coup (perdant et donc bleu) sur un polygone convexe dont le nombre de cases sera lui-même un multiple de 3 majoré de deux, c'est-à-dire un pentagone (5 = 1 * 3 + 2) ou, au pis-aller, un octogone (8 = 2 * 3 + 2).

Bref, nous sommes en présence d'une grille "cinq ou huit", espèce maudite ou bénie capable du meilleur (les problèmes élégants) comme du pire (les problèmes aussi ennuyeux qu'inélégants) dont je vous ai déjà pas mal parlé, par exemple dans ce post-ci.

Je tue le suspense: ici, c'est bien sur un pentagone qu'il faut terminer, et ce n'est même pas épouvantablement difficile -- donc ce serait bête de vous décourager tout de suite.

Je reviendrai sur ce fil pour vous donner de petits coups de main avant de vous balancer les solutions complètes... mais je ne vous promets pas d'avoir le temps de le faire aujourd'hui.

Désolé, les copains, je n'ai pas eu beaucoup de temps à consacrer à la grille "samedi", mais elle ne m'a pas paru mériter des réflexions bouleversantes. Pour l'essentiel, sa résolution peut employer seulement deux cavexes inversibles pas horriblement massifs...



... lesquels ne sont ni impossibles à imaginer, ni très évidents (enfin, les cinq derniers coups de la partie, donc les cinq premiers à identifier pour dessiner un cavexe, sont assez évidents, mais pas la suite).

Désolé, je n'ai pas le temps de détailler. Voici les solutions.

Solutions complètes:

Ce fil va probablement s'interrompre quelques jours. A bientôt!

Bonjour les gars et les filles... Ça se tire, vraiment ça se tire, si je ne m'abuse il ne reste que deux grilles sur la série de trente-quatre à partir de laquelle j'ai décidé il y a deux mois de construire tous mes exemples pédagogiques. Quand nous aurons fini tout ça, j'essaierai d'accoucher d'une table des matières et d'un index, et puis surtout je tâcherai de transformer la douzaine de pages de ce fil en une monographie libre de diffusion en PDF (très probablement mise en page avec LaTeX, pour ceux qui connaissent). Mais nous n'en sommes pas encore tout à fait là, et le problème du jour sera la grille "dormeur", de la série "Blanche-Neige et les sept nains".



M'étonne pas que je l'aie répertoriée parmi les grilles difficiles et que je vous l'aie gardée pour la fin. Déjà, c'est une grille à trois quadrilatères (1, 2, 3, 11 contre le bord supérieur; 23, 24, 30, 11, aux environs du centre; et le troisième que vous n'aviez pas vu, bande d'amateurs: 5, 6, 39, 40, réparti sur les bords inférieur et supérieur du tore). Trois quadrilatères, c'est beaucoup, et d'autant plus que, comme la pratique devrait vous l'avoir déjà enseigné, les quadrilatères ont une tendance prononcée à faire foirer tous les efforts des joueurs les plus persévérants. Comme si ça ne suffisait pas, cette grille bizarroïde comporte un ennéagone (et non un nonagone, comme disent les ignorants à qui on n'a jamais enseigné qu'il ne fallait pas mélanger les racines grecques et latines): 2, 3, 13, 4 et 5 contre le bord supérieur du tore, 36 à 39 contre le bord inférieur.

Eh bien, elle a beau être très mal foutue, cette grille (au point que mon solveur la résoud généralement en employant des cavexes "à mortaise", voire des stratégies dissidentes et peu orthodoxes, je vous montrerai), elle est quand même susceptible d'au moins quatre résolutions archi-classiques et académiques, à base de cavexes rondouillards et inversibles de très bon aloi. C'est une grille pour super-pros et je l'ai résolue tout seul, nananère, mais ça m'a quand même pris des dizaines de minutes après des années d'apprentissage, donc si vous en faites autant vous aurez le droit de vous prendre pour des kadors.

Et si vous n'êtes pas assez fanfarons pour vous en croire capables, je rends hommage à votre modestie mais je vous incite quand même à essayer: c'est -- entre autres -- en se cassant les dents sur les grilles très difficiles qu'on apprend à vaincre comme qui rigole les grilles moins difficiles. Bon courage.

Quelques indices pour continuer avec la grille "dormeur".

C'est une grille de 42 cases, donc on peut présumer que le score optimal y est atteint en terminant sur un heptagone: avec deux cases sacrifiées au début comme c'est généralement indispensable, il en reste 40, qui est un multiple de 3 majoré de 1, donc le dernier coup (perdant et bleu) doit être joué sur un polygone convexe dont le nombre de cases est lui aussi un multiple de 3 majoré de 1, donc un heptagone. A vrai dire, on peut être brièvement tenté d'essayer de terminer sur un quadrilatère (4 aussi est un multiple de 3 majoré de 1), d'autant qu'il y a sur cette grille deux quadrilatères mariés chacun à un pentagone et laissant donc l'espoir de jouer à proximité d'eux, dans ce pentagone, un avant-dernier coup gagnant. C'est bien pensé... mais en l'occurrence ça marche pas.

Je ne sais pas si vous avez essayé de dessiner sur cette grille un cavexe rondouillard et inversible avec un joli heptagone dedans, mais c'est vraiment pas de la tarte. Pour abréger vos souffrances, voici ceux que mon solveur a identifiés comme possibles:



A vrai dire, le deuxième, qui ressemble furieusement au premier en un peu moins concis, n'a pas été trouvé par mon solveur mais par votre serviteur -- et il en a bavé pour y arriver, votre serviteur, vous pouvez me croire.

Il est fort possible que ces quatre cavexes soient à peu près les seuls envisageables sur cette grille, mais ils ne constituent quand même pas des passages obligés pour atteindre le score optimal de onze coups gagnants (jaunes). Outre les incompréhensibles cavexes "à mortaise" dont mon solveur s'est fait la spécialité... il reste la possibilité de réfléchir aux stratégies hérétiques évoquées par le sympathique lecteur Jean-Pierre Liégeois de Carpentras dans ce post vieux de plus d'un mois (comme le temps passe). A l'époque, j'avais dénoncé ces stratégies hérétiques comme inutilement compliquées... eh bien, par exception, sur cette grille-ci, elles mènent réellement à des solutions plus faciles à trouver.

Mais je ne vous en dis pas plus, il faut quand même que vous bossiez un peu.

Et voici les solutions pour la grille "dormeur".

Commençons par les solutions orthodoxes:

On pourrait en rester là. Mais mon solveur me rend assez de services pour que je ne censure pas sa créativité, et l'honnêteté me force à signaler qu'au lieu de terminer de façon classique et orthodoxe sur un heptagone, il choisit le plus souvent (me demandez pas pourquoi) de terminer sur un pentagone en sacrifiant deux nouvelles cases en cours de route... C'est bizarre, mais ça mène bien au même score optimal: au lieu de sacrifier deux cases au début et un heptagone à la fin (2 + 7 = 9), il sacrifie deux cases au début, deux cases en cours de route et un pentagone à la fin, et atteint donc le même score optimal (2 + 2 + 5 = 9 aussi). C'est quand même, à mon sens, nettement moins élégant: on atteint le même nombre de coups gagnants et donc le même score optimal, mais on ne réalise pas une série ininterrompue de coups gagnants -- performance qui, à mon avis, comble davantage d'aise les esprits mathématiques bienveillants qui gouvernent le monde et veillent sur nous. Mais ce n'est que mon opinion de dévot de la logique, je suis bien incapable de vous démontrer que les dits esprits sont du même avis que moi sur cette question.

Berk les vilaines solutions hérétiques:

Bon, ben si on renonce à l'exigence d'une série ininterrompue de coups gagnants, pourquoi ne pas essayer aussi de terminer sur un hexagone en ayant sacrifié trois cases en amont (2 + 1 + 6 = 9, toujours 9...). C'est ce que j'ai fait et, honnêtement, j'y suis arrivé comme qui rigole, alors que l'élaboration de ma solution orthodoxe m'avait demandé je ne sais combien de dizaines de minutes d'essais infructueux. En plus, ça n'est pas désagréable à l'oeil:



Si vous êtes un taliban du Triancey "partrois", vous condamnerez au bûcher toutes les solutions ne comportant pas une série ininterrompue de coups gagnants. Si au contraire vous estimez que peu importe que le chat soit noir ou blanc du moment qu'il atteint le score optimal, ben vous admettrez ces solutions et il faudra peut-être recaler cette grille de la catégorie "difficile" à "difficulté moyenne"... Je vous laisse choisir et je me bornerai à vous interdire formellement la crémation des hérétiques: je suis parfois partisan de l'orthodoxie, mais jamais du bûcher.

Solution hérétique à ne pas montrer aux talibans:

Le problème du jour sera la grille "dimanche", avec laquelle, croyez-le si vous-voulez, nous achèverons de traiter la liste des 34 grilles que j'ai mises à votre disposition à titre pédagogique. Mon Dieu, mon Dieu, que de chemin parcouru.



Je vous avais classé cette grille dans la catégorie "cinq ou huit", mais c'était à l'époque où vous étiez des débutants, et au niveau où désormais vous vous trouvez presque tous (tousse, tousse), vous pouvez considérer que c'est une grille très facile. Y a pas de piège, appliquez la méthode et crac boum vous en viendrez à bout.

Solutions... plus tard, probablement pas avant demain.

Non, elle n'était vraiment pas bien compliquée, cette grille "dimanche".

Bon, finissons-en avec la routine (ça commence sérieusement à me gonfler de répéter toujours la même chose, pas vous?).

Cette grille comporte 40 cases, j'en sacrifie deux (bleues) au début, il en reste 38, et 38 étant un multiple de 3 majoré de deux, il faut jouer le dernier coup sur un polygone convexe dont le nombre de cases soit lui aussi un multiple de 3 majoré de deux, c'est-à-dire un pentagone (ça pourrait aussi être un octogone, mais ce serait moins bon puisque ça ferait trois cases jaunes de moins). Par ailleurs, le théorème de l'avant-dernier coup impose que l'avant-dernier coup d'une partie à score optimal (ou du moins à score optimal "classique") soit joué sur un pentagone marié (par deux cases) avec le polygone convexe final.

Donc nous cherchons sur cette grille deux pentagones mariés. Ouf. C'est rasoir, la routine, non? C'est nécessaire d'en passer par là, mais peut-être moins de le répéter sempiternellement...

Bon. Où y a-t-il deux pentagones mariés sur cette grille? En fait, il n'y en a pas deux, mais trois: le pentagone 19, 20, 26, 27, 28 est marié à droite par les cases 20 et 28 au pentagone 20, 21, 22, 28, 29, mais aussi à sa gauche par les cases 26 et 27 à un troisième pentagone coupé en deux de part et d'autre des deux bords verticaux du tore, le pentagone 31, 39, 26, 27, 32.

Eh bien, entamons notre cavexe par ces trois pentagones, et il est clair qu'il n'y a plus qu'à ajouter les cases 23, 30 et 24 pour achever le cavexe:



Honnêtement, c'était fastoche pour nous, qui sommes certes d'humbles mortels mais qui avons des yeux pour voir. Mon solveur, lui, n'a pas d'yeux, et c'est à tâtons dans les sombres recoins de la mémoire vive de mon ordinateur qu'il a dû chercher à dessiner d'autres cavexes valides. Il en a quand même trouvé six, dont pas un n'est aussi élégant que le premier:



Tous sont utilisables pour aboutir à un score optimal, bien entendu.

Donc, à vous de vous en inspirer pour aboutir vous-mêmes au score optimal. Je publierai des solutions complètes... un peu plus tard, cet après-midi ou ce soir.

Bon. Eh bien, voici comme promis les solutions de la grille "dimanche".

Solutions complètes:

Et voilà... Nous sommes venus à bout des trente-quatre grilles que j'avais préparées dès le départ. Nous avons défini ce qu'était un optimum, un cavexe, un optimum classique, nous avons démontré les quatre théorèmes (premier coup, deuxième coup, troisième coup, avant-dernier coup), nous avons résolu des grilles s'achevant sur un pentagone, un hexagone, un heptagone, un quadrilatère, un octogone, un couloir, un n'importe-quoi un peu bizarre... Nous avons vu des grilles où les solutions élégantes abondent, d'autres où il n'y a aucune solution élégante. Nous avons vu qu'il y a des grilles difficiles qui admettent pourtant plusieurs solutions, et des grilles qui n'admettent guère qu'une solution perdue parmi des milliers de milliards de combinaisons et qui sont quand même assez faciles avec un peu de méthode...

Et ça nous a servi à quoi, tout ça?

Franchement, je ne le sais pas, mais j'ai quand même l'absolue conviction que la réponse n'est pas "à rien".

Je ne sais pas pourquoi les humains -- enfin, certains humains que sur ce forum on appelle généralement des zèbres -- tiennent absolument à se triturer les méninges pour établir à quoi ressemble la vérité dans tel ou tel domaine raccordé à rigoureusement rien de concret. Mais c'est comme ça. Comme dit le scorpion dans la fable du scorpion et de la grenouille: "Que veux-tu, c'est dans ma nature."

Je ne sais pas trop ce que je vais faire de tout ça maintenant. Une table des matières, un index thématique, une compilation, ce genre de trucs... oui, c'est probable. Mais après?

En tout cas, je n'ai pas été mécontent de le faire.

Je songe vaguement à transformer les onze pages de ce fil en une petite monographie libre de diffusion, à usage des matheux des générations futures... et à cette fin, voici déjà un index chronologique. Je crains que ça n'intéresse que moi, mais vous pouvez quand même vous en servir, vous avez ma bénédiction.

Mar 24 Fév 2015 - 0:00
Présentation générale - Concept de réactions en chaîne

Mar 24 Fév 2015 - 16:34
Présentation technique de la version "partrois"

Mer 25 Fév 2015 - 10:54
Explication de l'objectif: le maximum de cases jaunes

Mer 25 Fév 2015 - 11:54
Pourquoi le nombre de cases est toujours pair

Mer 25 Fév 2015 - 13:30
Aspect visuel des optima

Jeu 26 Fév 2015 - 10:30
Théorèmes du premier, deuxième et dernier coup

Jeu 26 Fév 2015 - 16:17
Les scores optimaux les plus courants

Ven 27 Fév 2015 - 12:32
Théorème de l'avant-dernier coup - Notion de cavexe - Résolution détaillée de la grille "janvier"

Dim 1 Mar 2015 - 17:29
Grille "chirac": insoluble de façon classique car dépourvue de pentagone

Mar 3 Mar 2015 - 9:44
Interrogation sur le nombre de grilles différentes

Mar 3 Mar 2015 - 16:42
Evaluation (erronée) du nombre de grilles

Mer 4 Mar 2015 - 17:32
Grille "decembre"

Ven 6 Mar 2015 - 16:00
Notion de cavexe inversible

Sam 7 Mar 2015 - 9:22
Amorce de méthode pour déterminer avec certitude si deux grilles sont différentes

Sam 7 Mar 2015 - 18:59
Un réseau d'hexagones sur un tore

Sam 7 Mar 2015 - 19:23
La façon la plus simple d'inscrire des hexagones sur un tore

Dim 8 Mar 2015 - 0:47
Digression: unifier la surface des cases

Dim 8 Mar 2015 - 12:13
Les trente-quatre grilles classées par difficulté

Lun 9 Mar 2015 - 10:29
Grille "mai" - Facile parce qu'insoluble de façon classique

Lun 9 Mar 2015 - 23:42
Exemple de deux grilles différentes alors que leurs descriptifs concis seraient semblables

Mar 10 Mar 2015 - 9:45
Grille "octobre" - En quoi les quadrilatères sont gênants

Mer 11 Mar 2015 - 9:13
Grille "atchoum"

Mer 11 Mar 2015 - 12:15
Estimation de la complexité de la résolution d'une grille

Mer 11 Mar 2015 - 16:50
Solutions de la grille "atchoum" sans les cinq derniers coups

Jeu 12 Mar 2015 - 9:51
Grille "lundi"

Ven 13 Mar 2015 - 9:59
Gamberges sur le caractère intelligent ou non des solutions bizarroïdes

Mar 17 Mar 2015 - 9:03
Grille "mars"

Mar 17 Mar 2015 - 11:23
Difficultés pédagogiques: faire appliquer une méthode non comprise

Mer 18 Mar 2015 - 10:20
Caractère inversible ou non d'un cavexe; concavité, convexité

Mer 18 Mar 2015 - 16:49
Tenons et mortaises

Jeu 19 Mar 2015 - 10:07
Les cavexes à mortaise

Ven 20 Mar 2015 - 9:20
Grille "avril" - Cinq rangées horizontales

Ven 20 Mar 2015 - 11:43
Obtenir l'optimum de façon non classique (méthode Jean-Pierre Liégois de Carpentras)

Dim 22 Mar 2015 - 10:03
Grille "juin"

Dim 22 Mar 2015 - 18:17
Le cavexe le plus concis est-il toujours le meilleur?

Lun 23 Mar 2015 - 8:41
Grille "aout"

Mar 24 Mar 2015 - 8:58
Grille "novembre"

Mar 24 Mar 2015 - 23:19
Solutions orthodoxes mais bizarres, dont un cavexe torsadé - Se montrer "fort contre Dieu"

Jeu 26 Mar 2015 - 0:00
Grille "septembre" (effroyablement difficile, soluble uniquement avec des cavexes "à mortaise") - Les vignettes Panini

Jeu 26 Mar 2015 - 14:25
Les grilles "cinq ou huit" - Grille "prof"

Jeu 26 Mar 2015 - 20:04
Pourquoi une grille "cinq ou huit" peut être la meilleure et la pire des grilles - Chercher un chat noir dans une pièce sombre sans savoir s'il y est

Ven 27 Mar 2015 - 9:46
Grille "grincheux"

Sam 28 Mar 2015 - 10:28
Grille "joyeux" - Les multiples façons de terminer en sacrifiant huit cases

Dim 29 Mar 2015 - 18:41
Les solutions extraterrestres

Lun 30 Mar 2015 - 17:43
L'horloger de Voltaire - Une petite réplique à Richard Dawkins

Mer 1 Avr 2015 - 0:07
Les pouvoirs paranormaux de Triancey

Jeu 2 Avr 2015 - 9:57
Grille "simplet"

Ven 3 Avr 2015 - 10:30
Grille "timide" - Cavexe horizontal sur grille à structure horizontale

Sam 4 Avr 2015 - 11:56
Grille "degaulle" - Grille "inratable": multiplicité de solutions

Mar 7 Avr 2015 - 9:51
Grille "pompidou" - Une seule solution, qui tombe donc sous le sens

Mer 8 Avr 2015 - 10:01
Grille "mercredi"

Ven 10 Avr 2015 - 8:57
Le Saint-Graal du Triancey partrois (théorie): une seule case bleue sur toute la grille

Sam 11 Avr 2015 - 0:16
Structure informatique des descriptifs des grilles

Sam 11 Avr 2015 - 10:29
Les scripts Unix de production des grilles

Sam 11 Avr 2015 - 16:55
La grille "Saint-Graal"

Mar 14 Avr 2015 - 9:54
Grille "mardi" (avec un exemple de cavexe qu'on peut dessiner mais non employer)

Mar 14 Avr 2015 - 17:11
Digression métaphysique - Pourquoi la perfection ennuie Dieu (conversion de Saint Paul)

Jeu 16 Avr 2015 - 10:36
Grille "giscard" (exemple heureusement rare d'une grille vraiment ennuyeuse; c'est un "cinq ou huit" se terminant sur huit sans aucune élégance)

Ven 17 Avr 2015 - 10:42
Grille "jeudi" - De l'utilité de la foi en la victoire

Dim 19 Avr 2015 - 9:33
Grille "mitterrand"

Lun 20 Avr 2015 - 10:38
Grille "sarkozy"

Mer 22 Avr 2015 - 9:22
Grille "hollande" (particulièrement facile)

Jeu 23 Avr 2015 - 10:17
Grille "fevrier" - Très difficile - et vexante quand on voit qu'il y existait quand même une solution simple

Lun 27 Avr 2015 - 9:11
Grille "juillet" - "Particulière" (on peut la terminer sur un quadrilatère)

Lun 27 Avr 2015 - 18:20
Résolution erronée (et apparemment irréprochable) de la grille "juillet" - Exemple détaillé, donc pédagogique

Mer 29 Avr 2015 - 9:52
Grille "vendredi" - Difficile en raison de l'abondance des solutions

Sam 2 Mai 2015 - 9:23
Grille "blancheneige" - Difficile mais de solution évidente pour des esprits méthodiques - Exemple détaillé

Dim 3 Mai 2015 - 19:33
Cas rare d'un cavexe non orthodoxe (non inversible) et pourtant compréhensible

Lun 4 Mai 2015 - 8:58
Grille "samedi"

Jeu 7 Mai 2015 - 8:53
Grille "dormeur" - Susceptible de solutions hérétiques

Sam 9 Mai 2015 - 8:46
Grille "dimanche"

Encore un post principalement à l'usage de votre serviteur et de sa monographie future: un inventaire des grilles de démonstration, indiquant leur difficulté et renvoyant aux moments où l'on a discuté de chacune d'entre elles.

Les douze mois de l'année

Grille janvier - Très facile (et particulièrement pédagogique)
Discussion en date du Ven 27 Fév 2015 - 12:32

Grille février - Difficile (et même très -- mais il existe quand même une solution simple)
Discussion en date du Jeu 23 Avr 2015 - 10:17

Grille mars - Difficulté moyenne
Discussion en date du Mar 17 Mar 2015 - 9:03

Grille avril - Difficulté moyenne (on peut noter sa structure très horizontale)
Discussion en date du Ven 20 Mar 2015 - 9:20

Grille mai - Facile (mais insoluble de façon classique)
Discussion en date du Lun 9 Mar 2015 - 10:29

Grille juin - Difficulté moyenne
Discussion en date du Dim 22 Mar 2015 - 10:03

Grille juillet - Particulier (on peut la terminer sur un quadrilatère)
Discussion en date du Lun 27 Avr 2015 - 9:11

Grille aout - Difficulté moyenne
Discussion en date du Lun 23 Mar 2015 - 8:41

Grille septembre - "Cinq ou huit" (effroyablement difficile, soluble uniquement avec des cavexes "à mortaise")
Discussion en date du Jeu 26 Mar 2015 - 0:00

Grille octobre - Facile
Discussion en date du Mar 10 Mar 2015 - 9:45

Grille novembre - Difficulté moyenne
Discussion en date du Mar 24 Mar 2015 - 8:58

Grille decembre - Difficile (la difficulté est liée au fait qu'on peut se braquer sur une hypothèse de résolution irréalisable)
Discussion en date du Mer 4 Mar 2015 - 17:32

Blanche-Neige et les sept nains

Grille blancheneige - Difficile (mais de solution évidente pour des esprits méthodiques)
Discussion en date du Sam 2 Mai 2015 - 9:23

Grille atchoum - Facile
Discussion en date du Mer 11 Mar 2015 - 9:13

Grille dormeur - Difficile (et susceptible de solutions hérétiques)
Discussion en date du Jeu 7 Mai 2015 - 8:53

Grille grincheux - Difficulté moyenne
Discussion en date du Ven 27 Mar 2015 - 9:46

Grille joyeux - Difficulté moyenne (multiples façons de terminer en sacrifiant huit cases)
Discussion en date du Sam 28 Mar 2015 - 10:28

Grille prof - "Cinq ou huit" (typique de ce genre de grilles)
Discussion en date du Jeu 26 Mar 2015 - 14:25

Grille simplet - Difficulté moyenne
Discussion en date du Jeu 2 Avr 2015 - 9:57

Grille timide - Difficulté moyenne (structure horizontale sur laquelle un cavexe "en ruban" est possible)
Discussion en date du Ven 3 Avr 2015 - 10:30

Les présidents de la Ve République

Grille degaulle - Difficulté moyenne (grille "inratable": multiplicité de solutions)
Discussion en date du Sam 4 Avr 2015 - 11:56

Grille pompidou - Difficulté moyenne (guère qu'une solution, mais qui tombe donc sous le sens)
Discussion en date du Mar 7 Avr 2015 - 9:51

Grille giscard - "Cinq ou huit" (grille ennuyeuse; on ne peut que terminer sur huit sans aucune élégance)
Discussion en date du Jeu 16 Avr 2015 - 10:36

Grille mitterrand - Difficulté moyenne (rien de particulier, à part qu'il faut terminer sur huit)
Discussion en date du Dim 19 Avr 2015 - 9:33

Grille chirac - Particulier (dépourvue de pentagone et donc insusceptible de résolution classique)
Discussion en date du Dim 1 Mar 2015 - 17:29

Grille sarkozy - Difficulté moyenne
Discussion en date du Lun 20 Avr 2015 - 10:38

Grille hollande - Facile
Discussion en date du Mer 22 Avr 2015 - 9:22

Les sept jours de la semaine

Grille lundi - Facile
Discussion en date du Jeu 12 Mar 2015 - 9:51

Grille mardi - Difficulté moyenne (avec un exemple de cavexe qu'on peut dessiner mais non employer)
Discussion en date du Mar 14 Avr 2015 - 9:54

Grille mercredi - Difficulté moyenne
Discussion en date du Mer 8 Avr 2015 - 10:01

Grille jeudi - "Cinq ou huit" (intéressant: démontre l'utilité de la foi en la victoire)
Discussion en date du Ven 17 Avr 2015 - 10:42

Grille vendredi - Difficulté moyenne (difficile en raison de l'abondance des solutions)
Discussion en date du Mer 29 Avr 2015 - 9:52

Grille samedi - "Cinq ou huit"
Discussion en date du Lun 4 Mai 2015 - 8:58

Grille dimanche - "Cinq ou huit"
Discussion en date du Sam 9 Mai 2015 - 8:46

Allez, juste pour vous faire honte d'avoir peur de petits triangles de rien du tout, bande de surdoués à la noix:



Je vous signale qu'il y a des mômes que les jeujeux de triangles n'effraient pas: un petit tournoi de Triancey (bon, d'accord, pas la version "casse-tête") a été organisé tout récemment au collège de la Cerisaie de Charenton-le-Pont, et une douzaine de moutards très sages se sont creusé la tête pendant plus de deux heures avec mes grilles et mes pions bicolores, même que je crois bien qu'il s'est agi du premier tournoi de Triancey de l'histoire (allez, n'ayons pas peur des mots: de l'histoire de l'humanité).

Et vous, là, vous êtes pas foutus de me résoudre la moindre grille? Alors que vous vous dites surdoués? Mmm?

Bande de nases. Je m'en fous, je vais bouder, na.

Rha la vache, c'était vraiment hard-core mais j'ai réussi à trouver comment les résoudre intégralement en un minimum de coups. Je n'ai fais que le premier semestre, les autres solutions arriveront lorsque j'aurai le temps.

Ton exemple :
12 coups : 9 - 5 - 11 - 39 - 31 - 36 - 43 - 15 - 28 - 19 - 7 - 13

Janvier :

10 coups : 27 - 37 - 30 - 8 - 17 - 23 - 32 - 34 - 3 - 12

Février :

11 coups : 31 - 35 - 38 - 25 - 34 - 16 - 5 - 14 - 11 - 0 - 9

Mars :

11 Coups : 32 - 34 - 30 - 17 - 25 - 37 - 0 - 39 - 11 - 4 - 13

Avril :

10 coups : 29 - 35 - 26 - 2 - 32 - 16 - 18 - 12 - 9 - 14

Mai :

11 Coups : 34 - 36 - 23 - 16 - 18 - 21 - 2 - 13 - 31 - 9 - 39

Juin :

11 Coups : 35 - 36 - 32 - 25 - 28 - 21 - 10 - 23 - 16 - 2 - 14

Je pense qu'avec un peu d'efforts supplémentaires je peux même résoudre intégralement le jeu.

Bon allez, maintenant que j'y suis : la fin de l'année...

Juillet :

11 Coups : 17 - 41 - 36 - 6 - 9 - 31 - 0 - 33 - 38 - 22 - 24

Aout:

11 Coups : 33 - 40 - 35 - 25 - 27 - 23 - 13 - 17 - 9 - 4 - 11

Septembre :

12 Coups : 45 - 26 - 37 - 32 - 28 - 30 - 8 - 3 - 5 - 21 - 14 - 15

Octobre :

10 Coups : 20 - 25 - 17 - 0 - 10 - 24 - 36 - 22 - 5 - 32

Novembre :

11 Coups : 37 - 40 - 36 - 21 - 29 - 34 - 3 - 8 - 24 - 12 - 14

Decembre :

11 Coups : 37 - 39 - 27 - 20 - 22 - 12 - 8 - 14 - 32 - 4 - 34

hobb a écrit:Rha la vache, c'était vraiment hard-core mais j'ai réussi à trouver comment les résoudre intégralement en un minimum de coups.

Mais mais mais ma parole tu t'es cassé le tronc à tout renuméroter? Pourquoi diable?

Sans blague, ça sert à quoi que Petitagore il se décarcasse à programmer des interfaces clicables en Javascript?

Tes solutions m'ont l'air élégantes (très, même... enfin, je n'en ai encore étudié que deux), mais peux-tu être certain que tu as toujours trouvé le minimum minimorum, et que quelqu'un d'encore plus ingénieux que toi (ou un algorithme puissant) ne pourrait pas de temps à autre réussir à tout prendre avec encore un coup de moins que toi?

J'espère que tu peux faire mieux que me répondre "chiche"...

Oui, je suis certain que j'ai trouvé le minimum. Ce n'est pas par une méthode statistique, c'est déterministe. Au mieux on pourra les trouver plus rapidement (c'est meme sur, d'ailleurs je cherche encore à optimiser mon algo), mais c'est tout, il est impossible de les compléter en moins de coups. Par contre je pense qu'avec un peu de gymnastique je pourrai en faire une IA imbattable (ou match nul).

Quant à les numéroter, c'est nécessaire pour que mon algo puisse bouffer les paramètres d'entrée... peu importe la numération, mon algo sortira quand meme un minimum.

hobb a écrit:Oui, je suis certain que j'ai trouvé le minimum. Ce n'est pas par une méthode statistique, c'est déterministe.

Ah, tu as donc planché sur un algorithme, OK.

Pourrais-tu envisager d'en faire un logiciel libre? (oui, cette question est bassement intéressée) Et si la réponse est positive (autrement, je m'en fous   ), tu as écrit ça en quel langage?

Quant à les numéroter, c'est nécessaire pour que mon algo puisse bouffer les paramètres d'entrée... peu importe la numération, mon algo sortira quand meme un minimum.

Bien sûr. Mais tant qu'à faire, tu aurais pu prendre en paramètres d'entrée les fichiers XML exploités par mes listings Javascript, dans ce genre-là. C'est peut-être ce que tu as fait, d'ailleurs, mais alors je m'étonne que tu n'en aies pas profité pour récupérer la numérotation (balise "alias").

J'ai fais ça en fortran. Pour en faire un logiciel libre, why not, au pire je peux te passer les bibliothèques précompilées gratis sinon (parce que si ça a prit autant d'ampleur ça a peut etre moyen de finir en publi, auquel as il ne faut pas que je le mette en public avant qu'il ne parte en referee).

Non pour la numérotation je n'avais pas envie de m'emm****** à décrypter du xml avec du fortran (qui n'est quand meme pas super adapté pour bidouiller du texte tu en conviendras), donc en entrée je n'entre que les les 3 liens de chaque triangle avec les autres, il s'occupe du reste.

Et puis très honnetement, le code est vraiment compliqué (serieusement)... Je veux bien t'expliquer l'algorithme mais sur le net ça serait vraiment trop long...

Je viens de regarder, tu es sur de mettre le code à dispo de tout le monde ça ne risque pas de pourrir les jeux du meme type dispos sur le net ? C'est toi qui l'a inventé ?

Merci, je vais essayer de comprendre au moins la démarche générale.

En fait le but est de faire de la remontée d'échelle de la taille des polygones. On sait que pour poser un triangle, il faut un coup.

Après, tu détermines TOUS les polygones possibles (triangles ajoutés), et tu les tries par taille.
Pour chaque couple de polygones, tu cherches quel autre polygone ça donne. Le nombre de coup pour obtenir ce polygone est donc la somme des coups nécessaires pour avoir ceux d'en dessous. A chaque fois que tu fais le lien, tu regarde si le cumul est pas plus petit. Ca pour chercher le minimum.
Ensuite tu fais une recherche inverse : tu pars tu polygone le plus grand (tout rempli quoi), et tu remontes aux 2 polygones qui ont nécessités le moins de coup pour donner celui-là par récursion, et tu trouves la dispositions des triangles nécessaires pour l'obtenir.

Ca c'est dans les grandes lignes, ça va de soi que les préallocations / quicksort / recherches dichtomiques etc sont nécessaires pour optimiser la vitesse, tu manipule quand meme des millions de polygones potentiels...

Tiens, voilà le code, si tu veux en faire une IA j'ai une idée de comment il faut faire (en jouant sur la parité du nombre d'action nécessaire pour chaque polygone) :

Code:

program temp2
!!! By HObb / ZC forum
 implicit none
 type polygon
  integer(2) :: nb_tri
  integer(2), allocatable, dimension(:) :: tri
 end type
 type polygon_finaux
  integer(2) :: nb_tri
  integer(2), allocatable, dimension(:) :: tri
  integer, dimension(2) :: min_from, max_from
  integer(2) :: cumul_min, cumul_max
 end type
 integer, allocatable, dimension(:) :: borne_inf,  borne_sup
 type(polygon), dimension(:), allocatable :: polygones
 type(polygon_finaux), dimension(:), allocatable :: polygones_finaux
 integer(2), dimension(:,:), allocatable :: reduced_polygons, reduced_polygons_sorted
 integer, allocatable, dimension(:,:) :: liens
 logical, dimension(:), allocatable :: powered
 integer :: taille_loc, nbpoly=0,iloc,jloc,kloc,lloc,nblink, nbpoly_tmp = 0, nbpoly_fin = 0
 integer :: debut, fin, med !! pour la dichotomie
 integer :: min_act, max_act
 logical :: finished
 character(30) :: filename
 call getarg(1,filename)
 allocate(polygones(10000000))
 allocate(polygones_finaux(10000000))

 open (file=filename, unit=10)
 read(10,*) nblink
 allocate(liens(nblink,3),powered(nblink))
 allocate(borne_inf(nblink), borne_sup(nblink))
 do iloc = 1, nblink
   read(10,*) kloc, liens(iloc,:)
   write(*,*) 'link n°',iloc, ' : ' , liens(iloc,:)
   liens(iloc,:) = liens(iloc,:) + 1
 enddo
 close(10)
 !!! CHECK LINKS
 do iloc = 1, nblink
   do jloc = 1, 3
     kloc = liens(iloc,jloc)
     finished = .false.
     do lloc = 1, 3
       if (liens(kloc,lloc)==iloc) finished = .true.
     enddo
     if (.not.finished) then
       write(*,*) 'ERROR LINK ', ILOC, ': linking to un-reverse ', KLOC
       stop
     endif
   enddo
 enddo
 
 do taille_loc = 1,nblink      ! compute all polygons ! -> 44
   do iloc = 1, nblink
     powered = .true.
     powered(iloc) = .false.
     call expand_poly(powered,iloc,taille_loc)
   enddo
   write(*,*) 'computing polygons of size : ', taille_loc, '->', nbpoly - nbpoly_tmp, 'total : ', nbpoly
   write(13,*) taille_loc, nbpoly - nbpoly_tmp, nbpoly
   nbpoly_tmp = nbpoly
 enddo
 write(*,*) 'now, detecting twins polygons...'
       !!! now reduce the twins polygones !!!
 write(*,*) '-> sort each triangle number in each polygon'
 do taille_loc = 1,nblink       ! compute all polygons size
   allocate(reduced_polygons(10000000,taille_loc),reduced_polygons_sorted(10000000,taille_loc))
   kloc = 0
   do iloc = 1, nbpoly
     if (polygones(iloc)%nb_tri == taille_loc) then
       kloc = kloc + 1
       reduced_polygons(kloc,:) = polygones(iloc)%tri(:)
       call QsortC1D(taille_loc,reduced_polygons(kloc,:))
     endif
   enddo
   write(*,*) '-> sort ', kloc,'polygons'
! reduced_polygon now contains all polygons of size 'taille_loc', sorted by increased tri number
! now, sorting by tri numbers, to detect duplicates polygons
   call QsortC2D(kloc,taille_loc,reduced_polygons(1:kloc,:))
! copying, ignoring twins
   write(*,*) '-> delete duplicated polygons'
   if (kloc > 0) then
     kloc = 0
     borne_inf(taille_loc) = nbpoly_fin + 1
     nbpoly_fin = nbpoly_fin + 1    
     kloc = kloc + 1
     allocate(polygones_finaux(nbpoly_fin)%tri(taille_loc))
     polygones_finaux(nbpoly_fin)%nb_tri = taille_loc
     polygones_finaux(nbpoly_fin)%tri(:) = reduced_polygons(1,:)    
     polygones_finaux(nbpoly_fin)%cumul_min = nblink
     polygones_finaux(nbpoly_fin)%cumul_max = 0
     reduced_polygons_sorted(kloc,:) = reduced_polygons(1,:)
     do iloc = 1, nbpoly
       if (any(reduced_polygons(iloc,:) /= reduced_polygons_sorted(kloc,:)).and.any(reduced_polygons(iloc,:)/=0)) then
         nbpoly_fin = nbpoly_fin + 1
         kloc = kloc + 1
         allocate(polygones_finaux(nbpoly_fin)%tri(taille_loc))
         reduced_polygons_sorted(kloc,:) = reduced_polygons(iloc,:)
         polygones_finaux(nbpoly_fin)%nb_tri = taille_loc
         polygones_finaux(nbpoly_fin)%tri(:) = reduced_polygons(iloc,:)
         polygones_finaux(nbpoly_fin)%cumul_min = nblink ! for the min research after
         polygones_finaux(nbpoly_fin)%cumul_max = 0 ! for the max research after
       endif
     enddo
     borne_sup(taille_loc) = nbpoly_fin
   endif
! reduced_polygons_sorted now contains kloc un-duplicated polygons of size taille_loc
   write(*,*) '           -> reduced : ', kloc
   write(*,'(A,I8,A,I6,A,I6,A)') 'total polygons : ', nbpoly_fin, '(',borne_inf(taille_loc),',', borne_sup(taille_loc),')'
   deallocate(reduced_polygons,reduced_polygons_sorted)
 enddo

 
! !!!!!!!!!! OK, now we have all the unique polygone in polygones_finaux -> writing it in a file
!  open(file = 'polygons.dat', unit=20)
!  do iloc = 1, nblink
!    write(20,*) iloc
!    write(20,*) borne_inf(iloc),borne_sup(iloc)
!    do jloc = borne_inf(iloc),borne_sup(iloc)
!      write(20,*) polygones_finaux(jloc)%nb_tri
!      write(20,*) polygones_finaux(jloc)%tri(:)
!      write(20,*) polygones_finaux(jloc)%cumul_min
!      write(20,*) polygones_finaux(jloc)%cumul_max
!      write(20,*) polygones_finaux(jloc)%min_from(:)
!      write(20,*) polygones_finaux(jloc)%max_from(:)
!    enddo
!  enddo
!  close(20)


!!!!!!!!!! on action by polygone = triangle, after all the combinaisons are upgraded
 do iloc = borne_inf(1), borne_sup(1)
   polygones_finaux(iloc)%min_from = 0
   polygones_finaux(iloc)%max_from = 0
   polygones_finaux(iloc)%cumul_min = 1
   polygones_finaux(iloc)%cumul_max = 1
 enddo
! now, ALL the combinaisons
 allocate(reduced_polygons(1,nblink))
 do iloc = 1, nbpoly_fin - 1
   write(*,*) 100.*real(iloc)/real(nbpoly_fin), '%'
   do jloc = iloc + 1, nbpoly_fin
     ! if any common triangle : ignore
     if (.not.common_tri(polygones_finaux(iloc)%nb_tri,polygones_finaux(jloc)%nb_tri, &
         polygones_finaux(iloc)%tri(:),polygones_finaux(jloc)%tri(:))) then
       powered = .true.
       do kloc = 1, polygones_finaux(iloc)%nb_tri
         powered(polygones_finaux(iloc)%tri(kloc)) = .false.
       enddo
       do kloc = 1, polygones_finaux(jloc)%nb_tri
         powered(polygones_finaux(jloc)%tri(kloc)) = .false.
       enddo
       ! reducing the developpment of the two polygons
       finished = .false.
       do while (.not.finished)
         finished = .true.
         do kloc = 1, nblink
           if ((count(.not.powered(liens(kloc,:)))>=2).and.powered(kloc)) then
             powered(kloc) = .false.
             finished = .false.
           endif
         enddo
       enddo
       taille_loc = 0
       do kloc = 1, nblink
         if (.not.powered(kloc)) then
           taille_loc = taille_loc + 1
           reduced_polygons(1,taille_loc) = kloc
         endif
       enddo
       call QsortC1D(taille_loc,reduced_polygons(1,:taille_loc))
    ! research the present polygon obtained (with dichotomy)
       debut = borne_inf(taille_loc)
       fin = borne_sup(taille_loc)
       lloc = 1
       do while (lloc /= 0)
         if (med /= (debut + fin) / 2) then
           med = (debut + fin) / 2
           lloc = compare(taille_loc,reduced_polygons(1,:taille_loc),polygones_finaux(med)%tri(:taille_loc))
           if (lloc > 0) then ! ce qu'on cherche est au dessus de la médiane
             debut = med
           elseif(lloc < 0) then ! sinon en dessous
             fin = med
           endif
         else
           lloc = 0!!!! SI on ne trouve pas, c'est que le cumul des 2 polygones donne 2 polygones distincts, osef pour le cumul donc
         endif
       enddo
       ! update min an max if necessary
      
!!!! WARNING : for the max, better algorithm to find : it's false.

       if (all(reduced_polygons(1,:taille_loc)==polygones_finaux(med)%tri(:taille_loc))) then
         min_act = polygones_finaux(iloc)%cumul_min + polygones_finaux(jloc)%cumul_min
         max_act = polygones_finaux(iloc)%cumul_max + polygones_finaux(jloc)%cumul_max
         if (polygones_finaux(med)%cumul_min >= min_act) then
           polygones_finaux(med)%min_from(:) = (/iloc,jloc/)
           polygones_finaux(med)%cumul_min = min_act
         endif
         if (polygones_finaux(med)%cumul_max <= max_act) then
           polygones_finaux(med)%max_from(:) = (/iloc,jloc/)
           polygones_finaux(med)%cumul_max = max_act
         endif
       endif
     endif
   enddo
 enddo
 deallocate(reduced_polygons)
 
!         do kloc = 1, nbpoly_fin
!
!         write(*,*) polygones_finaux(kloc)%tri
!     enddo
!  stop
!
!  write(*,*) '============= MIN ============'
! write(*,*) nbpoly_fin
! ! write(*,*) polygones_finaux(nbpoly_fin)%nb_tri
! ! write(*,*) polygones_finaux(nbpoly_fin)%tri
! ! write(*,*) polygones_finaux(nbpoly_fin)%cumul_min
! write(*,*) polygones_finaux(nbpoly_fin)%cumul_max
! write(*,*) polygones_finaux(nbpoly_fin)%max_from
! iloc = polygones_finaux(nbpoly_fin)%min_from(1)
! jloc = polygones_finaux(nbpoly_fin)%min_from(2)
!
! write(*,*) polygones_finaux(iloc)%tri
! write(*,*) polygones_finaux(jloc)%tri
!
!
! stop
 write(*,*) (polygones_finaux(nbpoly_fin)%cumul_min), 'actions'
 call affichage_min(nbpoly_fin) ! recursive search of minimal action and display

!  write(*,*) '============= MAX ============'

!  write(*,*) (polygones_finaux(nbpoly_fin)%cumul_max), 'actions'
!  call affichage_max(nbpoly_fin) ! recursive search of minimal action and display
 contains
 recursive subroutine expand_poly(power,begin,taille)
   logical, dimension(nblink), intent(inout) :: power
   integer, intent(in) :: begin
   logical, dimension(nblink) :: power2
   logical :: finished
   integer :: i, j, k, taille, taille2
   if (taille==1) then ! taille=1 : récursivement c'est la fin (pas 0, va savoir)
     nbpoly = nbpoly + 1
     allocate(polygones(nbpoly)%tri(count(.not.power)))
     polygones(nbpoly)%nb_tri = count(.not.power)
     k = 0
     do j = 1, nblink
       if (.not.power(j)) then
         k = k + 1
         polygones(nbpoly)%tri(k)=j
       endif
     enddo
   else
     do j = 1, 3 ! for all link centered on the begin'th triangle
       if (power(liens(begin,j))) then
         power2 = power
         power2(liens(begin,j)) = .false.
         taille2 = taille - 1
!        reducing
         finished = .false.
         do while (.not.finished)
           finished = .true.
           do i = 1, nblink
             if ((count(.not.power2(liens(i,:)))>=2).and.power2(i)) then
             power2(i) = .false.
             taille2 = taille2 - 1
             finished = .false.
             endif
           enddo
         enddo
         call expand_poly(power2,liens(begin,j),taille2)
       endif
     enddo
   endif
 end subroutine
 
 !!!!!!!!!!!!!!!!!! QUICKSORT ALGO !!!!!!!!!!!!!!!!! -> 2D & 1D

recursive subroutine slow_sort(taille,nbpol,debut,fin,indexa,A)
  integer, intent(in) :: nbpol,taille,debut,fin,indexa
  integer(2), intent(inout), dimension(taille,nbpol) :: A
  integer(2) :: temp
  integer :: i,j,k, minlocation,nb
  if ((debut < fin).and.(indexa<=nbpol)) then
    do i = debut,fin-1
      minlocation = i
      do j = i+1, fin
        if (A(j,indexa)<A(minlocation,indexa)) minlocation = j
      enddo
      ! exchange A(i) and A(minlocation)
      do k = 1, nbpol
        temp = A(i,k)
        A(i,k) = A(minlocation,k)
        A(minlocation,k) = temp
      enddo
    enddo
    j = 1
    nb = 0
    do while(j+nb<=taille)
      do while((all(A(j,1:indexa)==A(j+nb,1:indexa)).and.(j+nb<=taille)))
        nb = nb + 1
      enddo
      nb = nb - 1
      call slow_sort(taille,nbpol,j,j+nb,indexa+1,A)
      j = j + nb + 1
      nb = 0
    enddo
  endif
 end subroutine


recursive subroutine QsortC2D(taille,nbpol,A)
  integer :: nbpol,taille
  integer(2), intent(in out), dimension(taille,nbpol) :: A
  integer :: iq
  if(taille > 1) then
    call Partition2D(taille, nbpol, iq, A)
    call QsortC2D(iq-1,nbpol,A(:iq-1,:))
    call QsortC2D(taille-iq+1,nbpol,A(iq:,:))
  endif
end subroutine QsortC2D

recursive subroutine QsortC1D(nbpol,A)
  integer :: nbpol
  integer(2), intent(in out), dimension(nbpol) :: A
  integer :: iq

  if(nbpol > 1) then
    call Partition1D(nbpol, iq, A)
    call QsortC1D(iq-1,A(:iq-1))
    call QsortC1D(nbpol-iq+1,A(iq:))
  endif
end subroutine QsortC1D

 subroutine Partition2D(taille,nbpol,marker,A)
  integer :: i, j, k
  integer, intent(in) :: nbpol, taille
  integer(2), intent(inout), dimension(taille,nbpol) :: A
  integer, intent(out) :: marker
!   integer(2), dimension(nbpol) :: x, temp      ! pivot point
  integer(2) :: temp
!   x = A(1,:)
  i= 0
  j= taille + 1
  do
    j = j-1
    do
      if (compare(nbpol,A(j,:),A(1,:)) <= 0) exit
      j = j-1
    end do
    i = i+1
    do
      if (compare(nbpol,A(i,:),A(1,:)) >= 0) exit
      i = i+1
    end do
    if (i < j) then
        ! exchange A(i) and A(j)
       do k = 1, nbpol
         temp = A(i,k)
         A(i,k) = A(j,k)
         A(j,k) = temp
       enddo
     elseif (i == j) then
       marker = i+1
       return
     else
       marker = i
       return
     endif
  end do

 end subroutine Partition2D

  subroutine Partition1D(nbpol,marker,A)
  integer :: i, j, nbpol
  integer(2), intent(in out), dimension(nbpol) :: A
  integer, intent(out) :: marker
  integer(2) :: x, temp      ! pivot point
  x = A(1)
  i= 0
  j= nbpol + 1
  do
    j = j-1
    do
      if (A(j)<=x) exit
      j = j-1
    end do
    i = i+1
    do
      if (A(i)>=x) exit
        i = i+1
      end do
      if (i < j) then
        ! exchange A(i) and A(j)
        temp = A(i)
        A(i) = A(j)
        A(j) = temp
      elseif (i == j) then
        marker = i+1
        return
      else
        marker = i
        return
      endif
    end do

 end subroutine Partition1D
 
 integer function compare(n,A,B) ! return -1 if A<B, 0 if = and 1 if >
  integer :: i
  integer, intent(in) :: n
  integer(2), dimension(n), intent(in) :: A,B
  i = 1
  do while((A(i)==B(i)).and.i<n)
    i = i + 1
  enddo
  if (A(i)<B(i)) then
    compare = -1
  elseif (A(i)>B(i)) then
    compare = 1
  else
    compare = 0
  endif  

 end function
 
 logical function common_tri(N1, N2, T1, T2)
   integer(2), intent(in) :: N1,N2
   integer(2), dimension(N1) :: T1
   integer(2), dimension(N2) :: T2
   integer :: i, j  
   common_tri = .false.
   do i = 1, N1
     do j = 1, N2
       if (T1(i) == T2(j)) then
         common_tri = .true.
         return
       endif
    enddo
  enddo
  end function
  
 recursive subroutine affichage_min(number)
   integer, intent(in) :: number
   if (polygones_finaux(number)%cumul_min /= 1) then
     call affichage_min(polygones_finaux(number)%min_from(1))
     call affichage_min(polygones_finaux(number)%min_from(2))
   else
     write(*,*) polygones_finaux(number)%tri(1) - 1
   endif
 end subroutine
 recursive subroutine affichage_max(number)
   integer, intent(in) :: number
   if (polygones_finaux(number)%cumul_max /= 1) then
     call affichage_max(polygones_finaux(number)%max_from(1))
     call affichage_max(polygones_finaux(number)%max_from(2))
   else
     write(*,*) polygones_finaux(number)%tri(1) - 1
   endif
 end subroutine
  
  
  
 end program

D'ailleurs ce qui est marrant, vu que je pars de l'espace dual, c'est que je peux faire n'importe quelle topologie (Klein, tore, sphere, etc...)

hobb a écrit:C'est toi qui l'a inventé ?

Je veux, mon neveu!

hobb a écrit:Ca c'est dans les grandes lignes, ça va de soi que les préallocations / quicksort / recherches dichtomiques etc sont nécessaires pour optimiser la vitesse, tu manipule quand meme des millions de polygones potentiels...

J'ai très peu fait de Fortran dans ma longue carrière, donc il me serait sans doute plus simple d'essayer d'imiter ta démarche dans un langage que je domine plutôt que d'essayer de comprendre ton listing...

Je suis assez tenté d'employer pour résoudre ton problème (prise de toute la grille avec un minimum de coups) la même méthode quick and dirty que j'ai utilisée pour résoudre le mien (prise d'un maximum de cases de la grille trois par trois): définir une démarche générale dans un langage facile à écrire (Python), noter les résultats intermédiaires dans des fichiers de texte de taille titanesque (pour mon problème, ça se compte parfois en méga-octets), les trier avec l'utilitaire Unix sort (ééénorme avantage: je n'ai aucun besoin de le déboguer), puis les écrémer à mort, de nouveau en Python (je garde 0,5 % des meilleurs résultats, je jette les méga-octets restants): c'est ignominieusement inélégant, mais ça marche et ça ne prend pas des plombes à écrire, ni même à exécuter (il faut quelques dizaines de secondes pour atteindre le résultat qu'un algorithme optimisé pourrait sans doute atteindre en une fraction de seconde... mais je m'en fous du moment que ça va déjà des millions de fois plus vite que ce que pourrait faire mon vrai cerveau en barbaque!).

Dans l'immédiat, ne t'en déplaise, je vais peut-être commencer par traduire les douze résultats que tu as communiqués avec ma numérotation à moi, pour me faire une idée plus claire de leur élégance. Va savoir, ce sera peut-être déjà suffisant pour permettre d'imaginer une démarche exploitable par le cerveau d'un humain (c'est comme ça que j'ai fait pour mon problème "partrois"; il est vrai que j'ai étudié bien plus que douze solutions avant d'élaborer ma méthode des cavexes).

En tout cas, merci beaucoup, vraiment, d'avoir 1) résolu ton problème; 2) communiqué tes résultats. L'air de rien, c'est comme ça qu'on fait avancer la civilisation...

Aaargh, hobb, sur la grille "juillet", tu as oublié de numéroter une case (et du coup, ton nombre total de cases est impair, ce qui est impossible comme démontré beaucoup plus haut)... Bizarre que ça n'ait pas fait planter ton algo, d'ailleurs.

Petitagore a écrit:Aaargh, hobb, sur la grille "juillet", tu as oublié de numéroter une case (et du coup, ton nombre total de cases est impair, ce qui est impossible comme démontré beaucoup plus haut)... Bizarre que ça n'ait pas fait planter ton algo, d'ailleurs.

Ca ne peut pas le faire planter...

Ce que tu veux faire (3 par 3) ne sera pas déterministe.

Apparemment, pour que la solution que tu as donnée pour la grille "juillet" marche, il suffit (colossale finesse) de numéroter la case non numérotée avec le numéro manquant (41)... J'aimerais quand même que tu revérifies, siouplaît (c'est pour les générations futures, sait-on jamais).

Je ne comprends pas ta remarque sur le 3 par 3 non déterministe, mais de toute façon il s'agit d'un autre sujet.

J'ai regardé, en fait j'ai oublié de le numéroter sur l'image mais j'avais bien rentré cette case comme étant la 41° dans le data d'entrée. Le résultat est donc bon ^^

Et en python ça ira pas assez vite. Pour la plupart de tes grilles, mon code mets à l'aise de 2 minutes à plus d'une demi-heure. en python t'en as pour des mois...

J'ai fais ça en fortran, pour que ça aille le plus vite possible. A la rigueur tu peux le faire en C, mais en python t'en as pour des plombes, vraiment.

Quant aux fichiers en Mo........ t'as pas vu ceux que je manipule ^^

Petitagore a écrit:L'air de rien, c'est comme ça qu'on fait avancer la civilisation...

Si tu savais à quel point elle s'en cogne la civilisation de ceux qui la font avancer... Du pur égoïsme individuel : tant que le confort de chacun s'améliore, elle ne fait que gueuler pour que ça soit encore mieux... enfin c'est un autre débat.

hobb a écrit:Si tu savais à quel point elle s'en cogne la civilisation de ceux qui la font avancer...

A vrai dire, je le sais. Mais je fais semblant de ne pas le savoir.

Je viens de mettre en ligne ici une page HTML permettant d'étudier les douze solutions de notre ami Hobb dans une interface clicable (légèrement modifiée pour l'occasion: il n'y a plus de coloration spécifique pour la prise de trois cases à la fois, toutes les prises de cases se font en jaune). Je rappelle que Hobb poursuit un objectif différent de celui auquel j'ai consacré les douze pages qui précèdent: il s'agit pour lui de prendre toutes les cases d'une grille en un minimum de coups. C'est un challenge différent de celui dont j'ai abondamment parlé dans les pages qui précèdent, mais qui peut lui aussi se révéler fort intéressant.

Il serait peut-être envisageable de faire de cette idée toute neuve un nouveau jeu mathématique. Le défi serait alors, ou carrément d'égaler from scratch le record identifié par Hobb, ou seulement de retrouver les n derniers coups à partir des premiers (ce qui nous donnerait un casse-tête un peu similaire aux problèmes de type "mat en trois coups", "mat en cinq coups", bien connus et appréciés des joueurs d'échecs). Ce serait peut-être plus rigolo... et en tout cas, sans doute plus compréhensible que ma pourtant brillantissime idée de recherche de cavexes inversibles -- à laquelle la plupart des lecteurs de ce fil n'ont visiblement pas compris grand-chose, je le dis avec une tristesse infinie et nonobstant compatible avec le peu de lucidité dont je suis capable...

(Je m'en fous, le vrai génie est par nature incompris.)

Pauvres nases.  

En tout cas, j'espère que l'honorable Hobb acceptera de réfléchir avec moi à cette idée.

Je peux adapter l'algo pour qu'il te dise en combien de coups minimum tu peux finir la grille à partir de n'importe quelle configuration, à creuser...

Bon, j'ai fait deux tests à partir des douze grilles résolues par hobb. Primo, j'ai essayé d'atteindre le même optimum que son algorithme à partir d'une grille vide. Deuxio, j'ai amputé ses solutions de leurs cinq derniers coups, et essayé d'imaginer une nouvelle fin permettant de prendre la grille avec cinq coups issus de ma tête.

Résultat: ben c'est de la gnognotte, à mon avis. Non seulement je n'ai pas trouvé ça difficile, mais dans l'immense majorité des cas j'y suis arrivé du premier coup ou presque. Certes, je suis surentraîné, et il est possible que pour quelqu'un qui découvre la logique du jeu ça représente quand même un défi pas complètement inintéressant. Appel au peuple: si quelqu'un de mes sympathiques lecteurs veut faire le test et publier son avis, ça m'intéresserait.

Ça ne veut pas forcément dire qu'on ne peut pas faire un casse-tête avec de telles idées de jeu, mais en l'état ça me paraît seulement voué à élaborer des exercices pédagogiques assez faciles voués par exemple à enseigner le concept de réaction en chaîne aux petits nenfants; c'est très bien, j'aime beaucoup les petits nenfants et je trouve qu'il est important de leur apprendre la logique... en revanche de tels exercices ne me paraissent pas suffisants pour permettre aux surdoués (mes semblables mes frères) de trouver là le merveilleux plaisir masochiste qu'on éprouve à se triturer les méninges.

Oui, je sais, à part moi peu de personnes peuvent approcher l'orgasme en contemplant une grille Triancey. Tant pis pour vous, vous ne savez pas ce que vous perdez.

La recherche d'une prise totale de la grille en un minimum de coups présenterait peut-être plus d'intérêt avec très peu de cases (une vingtaine, voire une douzaine): là, l'algorithme de Hobb trouverait peut-être des solutions extraterrestres d'une élégance difficile à égaler. Symétriquement, on pourrait essayer de travailler avec beaucoup plus de cases... mais je suppose qu'alors ça conduirait à démultiplier exponentiellement les temps de réponse de l'algorithme de Hobb, sans que les optima ainsi identifiés soient forcément difficiles à égaler.

Hobb, je suis à ta disposition pour faire des essais. Ce serait dommage que tes efforts algorithmiques ne servent à rien, mais il faut peut-être leur chercher d'autres applications (avec peut-être des contraintes supplémentaires, du genre obligation de jouer les n premiers coups sur des cases totalement isolées).

Dans l'immédiat, je persiste à trouver que la règle "partrois" dont j'ai si abondamment parlé ci-dessus (quitte à empistrouiller mes lecteurs...) mène à des exercices nettement plus stimulants intellectuellement. Je suis mauvais juge parce que c'est moi que je l'ai inventé et qu'évidemment j'ai pour mon bébé une tendresse compréhensible (voire excusable!). Et puis tout le monde il a pas mes penchants masochistes, même que c'est très heureux... mais quand même, quand même: tel que je vous l'ai montré, il est pas si mal pensé que ça, mon petit jeujeu.

Si, si, je vous assure.

Il sagit d'un algo en O(n²) maximum, donc limité en terme de taille (logique), mais il peut encore monter (sinon avec encore un peu d'optim, genre parallélisation MPI (pas openmp parce que vu la structure de l'algo c'est un coup à attraper des dead-lock), ça pourrait aller plus vite).

Petitagore, je trouve les jeux futiles et que c'est perdre son temps d'intelligence et de concentration pour rien d'autre, le cas échéant d'addiction, qu'une espèce de culturisme du cerveau. Comment peux t'on s'appeler Kasparov et avoir employé tant d'intelligence uniquement pour montrer qu'il a la plus grosse dans un exercice de vie qui vaut bien les poids et haltères plus le régime hyper-protéiné ?

Attention, je ne suis pas en train de juger. En fait je ne fais que donner une opinion qui ne concerne que ma gestion personnelle des ressources intellectuelles dont je dispose : je suis intégralement fada de programmation, même si c'est mon métier depuis 30 ans. Ce qui se passe, c'est que j'estime que cette activité met en jeu les mêmes circuits neuronaux que ce genre de jeux mathématiques ou logiques. Passer du temps à des casse têtes, c'est comme de me reposer d'avoir programmé dix heures dans la journée en faisant un peu de programmation !

Ceci était dit a la fois pour le simple plaisir de la digression pré-oratoire et pour justifier le fait que je n'irai sur ce sujet pas au delà de l'éloge, j'admire résolument ta découverte, j'admire l'originalité, la profondeur et la variété de ce jeu pour lequel, pourtant tu l'as compris, je ne donnerai pas plus de cinq minutes de ma vie à cliquer sur un canevas java bien foutu en plus, ou à réfléchir aux nombreuses et ouvertes variantes des équations que tu proposes à la sagacité des lecteurs joueurs.

Une telle découverte/réalisation mérite largement que des tas et des tas de gens perdent des heures et des heures de leur temps de cerveau disponible à tenter de résoudre ces subtiles et pures équations totalement inutiles et communiquent fébrilement entre eux leur certitude d'avoir la plus grosse à l'aune de cette nouvelle et magnifique échelle !

Magnifique !

mumen a écrit:Une telle découverte/réalisation mérite largement que des tas et des tas de gens perdent des heures et des heures de leur temps de cerveau disponible à tenter de résoudre ces subtiles et pures équations totalement inutiles et communiquent fébrilement entre eux leur certitude d'avoir la plus grosse à l'aune de cette nouvelle et magnifique échelle !

Magnifique !

Hum... J'aurais mauvaise grâce à ne pas prendre tout ça pour un compliment.

Je suis généralement assez de ton avis sur la perte de temps et d'énergie intellectuelle que représentent les jeux. J'ai pas mal étudié les échecs, je pense que ça m'a appris beaucoup de choses, mais ce qu'ils m'ont appris de plus important et de très loin, c'est que... jouer aux échecs est une perte de temps. Tu vois, je pense un peu comme toi.

Pour mon casse-tête, c'est un peu différent. C'est moi qui avais eu l'idée, si ce n'était pas moi qui la creusais personne ne l'aurait fait à ma place... Je me suis senti responsable de mon idée comme le Petit Prince était responsable de sa rose, et puis je suis vraiment titillé par ce paradoxe: il existe de toute éternité, sur ce jeu que j'ai inventé il y a quelques années, sur une grille que mes algorithmes ont fabriquée ce matin, un ensemble parfaitement défini de solutions; ça existe depuis toujours, ça existe à jamais, c'est éternel, incréé, incontestable... comme Dieu, quoi -- sauf que je peux douter de l'existence de Dieu alors que je ne peux pas douter de la validité des solutions de mes grilles!

Par ailleurs, à côté de la version casse-tête qui a fait l'objet de ce fil, il y a la version toute simple à laquelle on peut faire jouer les mômes -- et là je pense que si tu vois les échecs comme du culturisme, alors ce petit jeujeu peut faire en comparaison l'effet d'une saine gymnastique.

Merci de ton commentaire en tout état de cause.

@mumen : Parce que pour toi les gens "intelligents" doivent uniquement appliquer ça au service de l'humanité ? Pas le droit d'avoir un loisir ?

Tu peux aussi les enfermer dans une cave et les interdire de rire et passer leur vie à bosser sur des trucs qu'eux seuls peuvent résoudre. T'en as d'autres des idées à la **** comme ça ?

Bon, je doute qu'il reste qui que ce soit pour suivre encore ce fil, mais tant pis: il me sert toujours à prendre des notes pour une monographie future. Donc, out of the blue, permettez-moi de noter ici une précision dont j'ai pris conscience ce matin en jouant sur cette grille-ci (oui, je joue à mon casse-tête à peu près tous les jours que le Bon Dieu fait; vous ne m'auriez pas cru monomaniaque à ce point, hein? si? ah bon):



... laquelle grille est aussi disponible dans une version interactive (en Javascript) à cette adresse.

Or donc, cette grille, munie d'un trilatère (les cases 17, 18 et 26) montre que le théorème de l'avant-dernier coup (qui affirme que le dernier coup d'une partie à score optimal doit être joué sur un pentagone) peut tolérer des exceptions. La solution ci-dessous (trouvée par mon solveur, bien entendu) en constitue une:

29 4 36 7 27 2 0 37 15 22 12 17 (19)

Eh bien oui, sur cette grille le score optimal peut être obtenu en jouant l'avant-dernier coup sur un trilatère plutôt que sur un pentagone. Vous, je sais pas, mais moi ça m'en a bouché un coin d'en prendre conscience.

C'est tout pour aujourd'hui. Navré de vous avoir dérangés.

Sauf que l'optimum est en 2 coups de moins : 24, 29, 22, 18, 20, 6, 11, 31, 2, 9 ;-)

hobb a écrit:Sauf que l'optimum est en 2 coups de moins : 24, 29, 22, 18, 20, 6, 11, 31, 2, 9 ;-)

On joue sur la même grille, mais pas au même jeu... Je parlais bien sûr de la règle "partrois" (l'essentiel des pages précédentes y est consacré), où l'optimum est constitué de la séquence où chaque coup gagnant prend exactement trois cases, pas une de plus, pas une de moins.

Donc, je t'incite vivement à relire toutes les pages précédentes.