une grille à boucle interdite

Bonjour,

J'attaque mon programme automnal avec la prise en compte, dans le solveur de situations interdites.
Je commence avec les boucles interdites et, comme jeu d'essai, le quelques 140 grilles de ce type extraites du jeu de génération de grilles.

En voici une d'un premier type, que je trouve assez amusante.

Ces grilles se résolvent sans marquage (si on admet que repérer une boucle interdite se fait bien sans.)

.....8..1
.7.....5.
..394.6..
..2..93..
..4.7....
6..3.....
..96..4..
.1.....8.
2.......5 _14

amicalement

G.penet

Bonjour Gpenet,
ravi de vous lire.
Boucle 58, e4=6

Bonjour JEANLE,

toujours sans marquage ni assimilé, celle-ci, du même type, qui, dans ma solution, réserve un léger piège, mais qui sera peut-être évité dans votre chemin.



.....1..2
..3....4.
56.....7.
....673..
...8.2...
..195....
.2.....56
.8....1..
9..3..... _111

je n'ai pas regardé, mais elle doit être assez coriace sans RI

amitiés

G.Penet

Oui, RI 56 d1-g1-g2 => d2#56, d2=2, d8=56=f9, f8=49, f2=56
Boucle interdite 56 d8-d1-g1-g2-f2-f9-c9 => c8#56, c8=7
A+

Bonjour JEANLE,

je poursuis avec un exemple assez différent, mais toujous sans marquage donc.

...1...6.
..2...9..
.1..2...3
4..3...7.
..1.9.2..
.....8...
.9..1..4.
6..9..7..
..8.....6 _7

Je ferai sans doute pour me rapprocher du classement SE, mais je ne suis pas entièrement convaincu de l'intérêt de rechercher une telle configuration.

amitiés

G.penet

bonjour gpenet,

je suis arrivé au bout sans boucle interdite (la 45 sans doute !), par gratte-ciel ou coloriage monocandidat (4); Le solveur MC fait de même.

Pourriez-vous me dire comment votre esclave traite la grille "à tuer (4a885)" ? Je pressens que du ternaire ou une pseudo-case devrait suffire, mais je n'ai pas trouvé, même si la solution d'abi donne des pistes.

Merci. A+

jeanlé a écrit:

bonjour gpenet,

je suis arrivé au bout sans boucle interdite (la 45 sans doute !), par gratte-ciel ou coloriage monocandidat (4); Le solveur MC fait de même.

Pourriez-vous me dire comment votre esclave traite la grille "à tuer (4a885)" ? Je pressens que du ternaire ou une pseudo-case devrait suffire, mais je n'ai pas trouvé, même si la solution d'abi donne des pistes.

Merci. A+

Bonjour JEANLE,

soyez curieux et reprenez là, la boucle interdite est sur le 35 et la ferneture se fait par un triangle.

La suivante se ferme par un Z (sur le 45).

Je regarde votre grille

voici le "Z"

..3.....8
.9...6.2.
2.....9..
.....3.1.
....7...5
.6.5.2...
..2...6..
.1.7...9.
7...8...3_9

amitiés

G.Penet

Je vais regarder. Je vous signale que la lecture de vos grilles avec les ... est très difficile pour les bigleux comme moi. Je préfère les 0 si possible.

jeanlé a écrit:

Je vais regarder. Je vous signale que la lecture de vos grilles avec les ... est très difficile pour les bigleux comme moi. Je préfère les 0 si possible.

Le choix du '0' ou du '.' pour les cases vides est un débat sans fin.

Le '.' permet plus facilement de lire la structure de la grille, ce qui est parfois utile (j'en donnerai bientôt deux exemples).

Heuresusement, avec le bloc-notes, on passe facilement de l'un à l'autre.

Je tiendrai compe de votre remarque.

amitiés

G.penet

Je ne vois pas la boucle dont vous parlez, ni pour la 7 ni pour la 11, et encore moins la fermeture (à part celle de mon esprit !).

Pour la 7, c'est un peu difficile, car comme je vais au bout sans problème, je ne sais pas sur quelle grille vous raisonnez.
Pour la 11, je ne vois pas. A+

Pour la _7, j'arrive sans encombre, comme Sudoku Explainer dans cette position

__ A_ B__ C__ |D_ E_ F_ |G_ H_ I_
1||8_ 7__ 45_ |1_ 3_ 9_ |45 6_ 2_
2||35 345 2__ |8_ 6_ 45 |9_ 1_ 7_
3||9_ 1__ 6__ |45 2_ 7_ |45 8_ 3_
4||4_ 2__ 9__ |3_ 5_ 1_ |6_ 7_ 8_
5||35 8__ 1__ |7_ 9_ 6_ |2_ 35 4_
6||7_ 6__ 35_ |2_ 4_ 8_ |1_ 35 9_
7||2_ 9__ 7__ |6_ 1_ 3_ |8_ 4_ 5_
8||6_ 345 345 |9_ 8_ 45 |7_ 2_ 1_
9||1_ 45_ 8__ |45 7_ 2_ |3_ 9_ 6_
La boucle est A2; A5; H5; H6; C6 pour la partie "paires".
Elle se ferme par C8; B8; B2
Le chiffre excéedentaire '4' doit exister en B2;B8;C8 donc B9=5

La deuxième grille, après un RI, arrive dans cette position
__ A__ B__ C__ |D__ E__ F_ |G__ H_ I_
1||6__ 7__ 3__ |9__ 2__ 1_ |45_ 45 8_
2||458 9__ 458 |348 345 6_ |7__ 2_ 1_
3||2__ 458 1__ |48_ 45_ 7_ |9__ 3_ 6_
4||58_ 2__ 578 |6__ 9__ 3_ |48_ 1_ 47
5||14_ 3__ 9__ |14_ 7__ 8_ |2__ 6_ 5_
6||148 6__ 478 |5__ 14_ 2_ |3__ 78 9_
7||9__ 458 2__ |13_ 13_ 45 |6__ 78 47
8||3__ 1__ 458 |7__ 6__ 45 |458 9_ 2_
9||7__ 45_ 6__ |2__ 8__ 9_ |1__ 45 3_

Le départ de boucle est G1;H1;H9;B9
Le "Z" de fermeture B7;F7;F8;G8
On a donc 8 B7;G8 donc pas de 8 en C8
d'ou B7=8; G8=8
amitiés
G.Penet

Merci, je ne connaissais pas. Il me reste à comprendre, ce sera pour demain. A+

Bonjour JEANLE,

je poursuis mon analyse des situations de boucle interdite et leur intégration dans le programme.

En voici un type très particulier (j'en ai quatre exemplaires)
toujours donc des grilles à résoudre sans marquage.

100020003
040000050
000607000
004000300
300040002
006000800
000809000
010000060
200030004 _36


Cette analyse m'a montré combien il était important de traiter en priorité les situations d'ensemble "assimilé complet" (donc la pseudo case type papyg) avant d'aborder les actions qui détruisent le RI.
Si on ne procède pas dans cet ordre, et sauf précisément à considérer les RI dégénérés, ce que l'on ne fait pas couramment, on rate des sorties simples.

amitiés
G.Penet

PS: Accessoirement, ce travail m'a fait corriger une erreur dans la famille des XWings que vous aviez signalée il y a un bon moment, mais que je n'avais pas eu le temps de rechercher.

Bonjour Gpenet,

Une grille très sympa !
J'ai fait un premier balayage (non noté) "tout seul", avec RI à pseudo-case, etc. puis un deuxième sensiblement différent avec le solveur MC (donc sans gratte-ciel, ni XYZ-wing, ni RI) pour être sûr de ne pas faire d'erreur juste.
Au blocage du solveur MC, après swordfish, XY-wing, etc.

_|_a___b___c_|_d___e___f_|_g___h____i
1|_1___7___89|45___2___45|_6__89___3
2|_6___4___2_|39___89__38|_1___5___7
3|89___3___5_|_6___1___7_|_4___2___89

4|57___9___4_|27__578__28|_3___1___6
5|_3___8___1_|59___4___6_|579__79__2
6|57___2___6_|13__579__13|_8___4___59

7|_4___5___7_|_8___6___9_|_2___3___1
8|89___1___3_|24___57__24|79___6___589
9|_2___6___89|157__3___15|579_789__4

RI57 a4-a6-e6-e4 avec 5 jumeaux en équerre a6a4e4 => -7e6, a6=7, a4=5 (non indispensable me semble-t-il ? Edit : je confirme qu'il est inutile))
XYZ-wing c9(89)-h9(789)-g8(79) => -9g9
X-wing des 9 c1h1-c9h9 => -9h5, h5=7, h9=89
Boucle interdite 89 h9-c9-a8-a3-c1-h1-i3 => -89i8, i8=5, etc. au bout.

A+

Bonjour JEANLE,

Les boucles interdites n'ont évidemment plus de secret pour vous.

Celle-ci, faite de deux "faux RI" simples composés dans les mêmes quatre boites est assez interessante.
C'est pour le moment la seule configuration que j'ai identifiée oùu on ne peut pas former la boucle avec seulement des chemins lignes et colonnes.

amitiés

G.Penet