Grille Extra 122

papyg
Admin
Grille Extra 122 RangAdmin

Inscrit le: 11 Oct 2005
Messages: 1130

Posté le: Ven 12/01/2007 14:36 Sujet du message: Grille Extra 122

Une nouvelle grille pour ne pas vous faire trop attendre...

Code:

+-------+-------+-------+
| . . 5 | 8 . . | 7 9 . |
| . . . | . . . | . . . |
| . . 7 | . . 6 | . . 4 |
+-------+-------+-------+
| 4 . . | . 1 . | . . 2 |
| 1 . . | . 7 . | . . 6 |
| 3 . . | . 5 . | . . 8 |
+-------+-------+-------+
| 8 . . | 9 . . | 3 . . |
| . . . | . . . | . . . |
| . 2 6 | . . 1 | 8 . . |
+-------+-------+-------+

papyg

BONJOUR
Sudoka Expert
Grille Extra 122 RangExpert

Inscrit le: 23 Aoû 2006
Messages: 867
Localisation: Courcelles-Les-Montbéliard (25420)

Posté le: Sam 13/01/2007 15:55 Sujet du message:

Bonjour

Grille complétée par choix uniques jusqu'à la 25ème case remplie

Code:

a b c | d e f | g h i |
|----------------------------|----------------------------|----------------------------|
1 | 26 1346 5 | 8 234 234 | 7 9 13 |
2 | 269 134689 123489 | 123457 2349 234579 | 1256 123568 135 |
3 | 29 1389 7 | 1235 239 6 | 125 12358 4 |
|----------------------------|----------------------------|----------------------------|
4 | 4 56789 89 | 36 1 389 | 59 357 2 |
5 | 1 589 289 | 234 7 23489 | 459 345 6 |
6 | 3 679 29 | 246 5 249 | 149 147 8 |
|----------------------------|----------------------------|----------------------------|
7 | 8 1457 14 | 9 6 2457 | 3 12457 157 |
8 | 579 134579 1349 | 23457 8 23457 | 124569 124567 1579 |
9 | 579 2 6 | 3457 34 1 | 8 457 579 |
|----------------------------|----------------------------|----------------------------|

grille ne contenant que les candidats postulants à des cases vides

Code:

a b c | d e f | g h i |
|----------------------------|----------------------------|----------------------------|
1 | 26 1346 | 234 234 | 13 |
2 | 269 134689 123489 | 123457 2349 234579 | 1256 123568 135 |
3 | 29 1389 | 1235 239 | 125 12358 |
|----------------------------|----------------------------|----------------------------|
4 | 56789 89 | 36 389 | 59 357 |
5 | 589 289 | 234 23489 | 459 345 |
6 | 679 29 | 246 249 | 149 147 |
|----------------------------|----------------------------|----------------------------|
7 | 1457 14 | 2457 | 12457 157 |
8 | 579 134579 1349 | 23457 23457 | 124569 124567 1579 |
9 | 579 | 3457 34 | 457 579 |
|----------------------------|----------------------------|----------------------------|

triplet 269 en a123
=> a8=57, a9=57, b1=134, b2=1348, b3=138, c2=1348, a1=6

paire 57 en a89
=> b7=14, b8=1349

triplet 289 en c456
=> b8=9, i9=9, b5=5, c8=3, b7=14, c7=14, b4=67, b6=67, d8=2457, f8=2457, g8=12456, i8=157

paire 14 en bc7
=> f7=257, h7=257, i7=57

alignement 2 ligne 1
alignement 2 colonne e
=> e1=2, d2=13457, d3=135, e2=349, f1=34, f2=34579

triplet 349 en e23f1
=> d2=157, d3=15, f2=57

alignement 3 colonne i
=> h2=12568, h3=1258

alignement 7 colonne i
=> h7=25, h8=12456, h9=45

A 31 cases remplies, situation des RAP, après la tournée des popotes

Code:

a b c | d e f | g h i |
|-------------------------|-------------------------|-------------------------|
1 | 6 134 5 | 8 2 34 | 7 9 13 |
2 | 29 1348 14 | 157 349 57 | 1256 12568 135 |
3 | 29 138 7 | 15 39 6 | 125 1258 4 |
|-------------------------|-------------------------|-------------------------|
4 | 4 67 89 | 36 1 389 | 59 357 2 |
5 | 1 5 289 | 234 7 23489 | 49 34 6 |
6 | 3 67 29 | 246 5 249 | 149 147 8 |
|-------------------------|-------------------------|-------------------------|
7 | 8 14 14 | 9 6 257 | 3 25 57 |
8 | 57 9 3 | 2457 8 2457 | 12456 12456 157 |
9 | 57 2 6 | 3457 34 1 | 8 45 9 |
|-------------------------|-------------------------|-------------------------|

Code:

a b c | d e f | g h i |
|-------------------------|-------------------------|-------------------------|
1 | 134 | 34 | 13 |
B
2 | 29 1348 14 | 157 349 57 | 1256 12568 135 |
B
3 | 29 138 | 15 39 | 125 1258 |

|-------------------------|-------------------------|-------------------------|
4 | 67 89 | 36 389 | 59 357 |

5 | 289 | 234 23489 | 49 34 |

6 | 67 29 | 246 249 | 149 147 |

|-------------------------|-------------------------|-------------------------|
7 | 14 14 | 257 | 25 57 |
=# B'
8 | 57 | 2457 2457 | 12456 12456 157 |
# # # # B'
9 | 57 | 3457 34 | 45 |
B BA
|-------------------------|-------------------------|-------------------------|

fait A: h9=5
fait B: h9=4, e9=3, f1=3, i2=3, i78=5
h7#5, g8#5, h8#5
=> h7=2, g8=146, h8=146, f7=57, h2=1568, h3=158

paire 57 en f27
=> f8=24

Code:

a b c | d e f | g h i |
|-------------------------|-------------------------|-------------------------|
1 | 134 | 34 | 13 |
AB A
2 | 29 1348 14 | 157 349 57 | 1256 1568 135 |
# # #AB
3 | 29 138 | 15 39 | 125 158 |
A A A #A
|-------------------------|-------------------------|-------------------------|
4 | 67 89 | 36 389 | 59 357 |

5 | 289 | 234 23489 | 49 34 |

6 | 67 29 | 246 249 | 149 147 |

|-------------------------|-------------------------|-------------------------|
7 | 14 14 | 57 | 57 |

8 | 57 | 2457 24 | 146 146 157 |

9 | 57 | 3457 34 | 45 |
B B
|-------------------------|-------------------------|-------------------------|

fait A: f1=3, i2=3, b3=3, i1=1, d3=1, h3=8, g3=5
fait B: f1=4, e9=4, h9=5, i2=5
g2#5, h2#5, h3#5, i2#1
=> g2=126, h2=168, h3=18

Code:

a b c | d e f | g h i |
|-------------------------|-------------------------|-------------------------|
1 | 134 | 34 | 13 |
B B
2 | 29 1348 14 | 157 349 57 | 126 168 35 |
B
3 | 29 138 | 15 39 | 125 18 |

|-------------------------|-------------------------|-------------------------|
4 | 67 89 | 36 389 | 59 357 |
B B
5 | 289 | 234 23489 | 49 34 |
= AB A
6 | 67 29 | 246 249 | 149 147 |
= B
|-------------------------|-------------------------|-------------------------|
7 | 14 14 | 57 | 57 |

8 | 57 | 2457 24 | 146 146 157 |
=
9 | 57 | 3457 34 | 45 |

|-------------------------|-------------------------|-------------------------|

fait A: g5=4, h5=3, d5=2, c6=2, f8=2
fait B: g5=9, i2=5, i1=3, f1=4, f8=2, f6=9, c6=2, d5=2
=> d5=2, c6=2, f8=2

Code:

a b c | d e f | g h i |
|-------------------------|-------------------------|-------------------------|
1 | 134 | 34 | 13 |
AB
2 | 29 1348 14 | 157 349 57 | 126 168 35 |
A
3 | 29 138 | 15 39 | 125 18 |
A
|-------------------------|-------------------------|-------------------------|
4 | 67 89 | 36 389 | 59 357 |
A
5 | 289 | 3489 | 49 34 |

6 | 67 | 46 49 | 149 147 |
B B =
|-------------------------|-------------------------|-------------------------|
7 | 14 14 | 57 | 57 |

8 | 57 | 457 | 146 146 157 |

9 | 57 | 3457 34 | 45 |

|-------------------------|-------------------------|-------------------------|

fait A: f1=3, i2=3, g3=5, h4=5, h6=7
fait B: f1=4, d6=4, b6=6, h6=7
=> h6=7 puis choix uniques jusqu'à la fin Grille Extra 122 Icon_biggrin

_________________
Amicalement
Bonne journée

BONJOUR

papa
Sudoka Expert
Grille Extra 122 RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Dim 14/01/2007 13:05 Sujet du message:

La première difficulté consiste à repérer les nombreuses paires et triplets cachés dans la grille pour aboutir au tableau suivant :

Code:

A B C D E F G H I
+-------------------+-------------------+-------------------+
1 | 6 134 5 | 8 2 {34} | 7 9 13 |
2 | {29} 1348 14 | 157 {349} 57 | 1256 12568 135 |
3 | {29} 138 7 | 15 {39} 6 | 125 1258 4 |
+-------------------+-------------------+-------------------+
4 | 4 67 {89} | 36 1 389 | 59 357 2 |
5 | 1 5 {289} | 234 7 23489 | 49 34 6 |
6 | 3 67 {29} | 246 5 249 | 149 147 8 |
+-------------------+-------------------+-------------------+
7 | 8 {14} {14} | 9 6 257 | 3 25 57 |
8 | 57 9 3 | 2457 8 2457 | 12456 12456 157 |
9 | 57 2 6 | 3457 34 1 | 8 45 9 |
+-------------------+-------------------+-------------------+

L'étude du deuxième bloc horizontal, et en particulier de ses boucles interdites donne la solution
du problème... En fait, ce deuxième bloc peut être résolu presque entièrement de façon isolée sans avoir
recours au reste de la grille !!!

Le voici en version compacte, après avoir retiré les chiffres connus :

Code:

+---------+------------+----------+
| 67 89 | 36 389 | 59 357 |
| 289 | 234 23489 | 49 34 |
| 67 29 | 246 249 | 149 147 |
+---------+------------+----------+

Pour voir apparaitre les boucles interdites, on va progressivement séparer les différents cas selon
que tel chiffre est dans telle ou telle colonne :

Code:

1 : le chiffre 1 en maison 6 est dans la 1ère colonne :
+---------+------------+----------+
| 67 89 | 36 389 | 59 357 |
| 289 | 234 23489 | 49 34 |
| 67 29 | 246 249 | 1 47 |
+---------+------------+----------+
2 : le chiffre 1 en maison 6 est dans la 2ème colonne :
+---------+------------+----------+
| 6 89 | 3 89 | 5 7 |
| 289 | 24 2489 | 49 3 |
| 7 29 | 6 249 | 49 1 |
+---------+------------+----------+

On continue à subdiviser :

Code:

1 : le chiffre 1 en maison 6 est dans la 1ère colonne :
1.1 : le chiffre 5 en maison 6 est dans la 1ère colonne :
+---------+------------+----------+
| 67 89 | 36 389 | 5 37 |
| 28 | 234 2348 | 9 34 |
| 67 29 | 246 249 | 1 47 |
+---------+------------+----------+
1.2 : le chiffre 5 en maison 6 est dans la 2ème colonne :
+---------+------------+----------+
| 7 8 | 6 3 | 9 5 |
| 9 | 2 8 | 4 3 |
| 6 2 | 4 9 | 1 7 |
+---------+------------+----------+
2 : le chiffre 1 en maison 6 est dans la 2ème colonne :
2.1 : le chiffre 2 en maison 5 est dans la 1ère colonne :
+---------+------------+----------+
| 6 89 | 3 89 | 5 7 |
| 89 | 2 489 | 49 3 |
| 7 2 | 6 49 | 49 1 |
+---------+------------+----------+
2.1 : le chiffre 2 en maison 5 est dans la dernière colonne :
+---------+------------+----------+
| 6 89 | 3 89 | 5 7 |
| 28 | 4 28 | 9 3 |
| 7 29 | 6 29 | 4 1 |
+---------+------------+----------+

Le 1.1 reste à subdiviser, le 1.2 est une solution possible, et le 2.1 et le 2.2 sont des boucles interdites.

Code:

1 : le chiffre 1 en maison 6 est dans la 1ère colonne :
1.1 : le chiffre 5 en maison 6 est dans la 1ère colonne :
1.1.1 : le chiffre 2 en maison 5 est dans la 1ère colonne :
+---------+------------+----------+
| 67 89 | 36 389 | 5 37 |
| 28 | 234 348 | 9 34 |
| 67 29 | 246 49 | 1 47 |
+---------+------------+----------+
1.1.2 : le chiffre 2 en maison 5 est dans la dernière colonne :
+---------+------------+----------+
| 67 89 | 36 89 | 5 37 |
| 28 | 34 28 | 9 34 |
| 67 29 | 46 29 | 1 47 |
+---------+------------+----------+

Le 1.1.2 est une boucle interdite, reste le 1.1.1...

Code:

1 : le chiffre 1 en maison 6 est dans la 1ère colonne :
1.1 : le chiffre 5 en maison 6 est dans la 1ère colonne :
1.1.1 : le chiffre 2 en maison 5 est dans la 1ère colonne :
1.1.1.1 : le chiffre 3 en maison 5 est dans la 1ère colonne :
+---------+------------+----------+
| 67 89 | 36 89 | 5 37 |
| 28 | 23 48 | 9 34 |
| 67 29 | 26 49 | 1 47 |
+---------+------------+----------+
1.1.1.2 : le chiffre 3 en maison 5 est dans la dernière colonne :
+---------+------------+----------+
| 7 9 | 6 8 | 5 3 |
| 8 | 2 3 | 9 4 |
| 6 2 | 4 9 | 1 7 |
+---------+------------+----------+

Le 1.1.1.1 est une boucle interdite alors que le 1.1.1.2 est une solution envisageable.
On a donc deux solutions possibles pour ce bloc :

Code:

+----------+----------+-----------+
4 | 4 7 89 | 6 1 38 | 59 35 2 |
5 | 1 5 89 | 2 7 38 | 49 34 6 |
6 | 3 6 2 | 4 5 9 | 1 7 8 |
+----------+----------+-----------+

La grille est finie.

Je sais que ce type de raisonnement presque exclusivement basé sur l'unicité est assez inhabituel, mais dans le cas présent, c'est extrèmement efficace.

papyg
Admin
Grille Extra 122 RangAdmin

Inscrit le: 11 Oct 2005
Messages: 1130

Posté le: Dim 14/01/2007 21:49 Sujet du message:

Bonsoir à tous, Situation intéressante, ou les solutions de BONJOUR et de papa sont radicalement différentes ! BONJOUR : en transcrivant sous forme de forme chaîne votre première élimination, vous auriez vu qu'il s'agit en fait d'une boucle : 5h9—4h9 / 4e9—3e9 / 3e23—3f1 / 3i1—3i2 / 5i2—5i78 / @ qui élimine également 4d9, 3b1 ... mais on ne va pas beaucoup plus loin avec! L'approche de papa est vraiment peu commune. Il est vrai que la grille recelait plusieurs RI plus ou moins exploitables, mais les boucles interdites... comment faites-vous pour les voir, papa ? papyg

papa
Sudoka Expert
Grille Extra 122 RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Lun 15/01/2007 8:38 Sujet du message:

papyg : vous avez raison pour les RI, j'en avait vu pas moins de 5 exploitables à partir du tableau étincelant, mais aucun ne permettait d'avancer vraiment significativement. En ce qui concerne la technique que j'ai utilisée, quelques explications ne seraient pas inutiles. J'en ai deja un peu parlé dans une fiche sur la résolution des blocs mais elle s'est un peu affinée depuis... D'abord, je répond à votre question sur les boucles interdites : Soient deux (ou trois, ou plus) "solutions possibles" d'un même bloc horizontal, qui respectent toutes ce que l'on attend d'une solution, à savoir : - 9 chiffres différents dans chaque ligne. - 9 chiffres différents dans chaque maison. - le tout compatible avec le tableau des candidats que nous avons préalablement déterminé. Si en plus, ces solutions contiennent exactement les mêmes chiffres dans chaque pseudo-case verticale (mais pas dans le même ordre), alors, les deux "solutions possibles" sont interchangeables. Si l'une est la vraie solution du sudoku, l'autre (ou les autres) l'est aussi. Conclusion, elles sont toutes fausses. Pour le vérifier, il suffit de constater que si une des solutions permet d'avoir chaque chiffre une fois par ligne, par colonne et par maison, les autres le permettent aussi. Toute la méthode utilisée plus haut est basée la-dessus. Je peut la détailler si vous le voulez, mais je pense qu'une fois qu'on à compris ce concept de boucle interdite, elle coule de source... Dernière édition par papa le Lun 15/01/2007 17:51; édité 1 fois

papyg
Admin
Grille Extra 122 RangAdmin

Inscrit le: 11 Oct 2005
Messages: 1130

Posté le: Lun 15/01/2007 11:14 Sujet du message:

Merci papa pour ces précisions. Bien vu, et très efficace ici,... malheureusement pas vraiment exploitable sans ordinateur ! papyg

papa
Sudoka Expert
Grille Extra 122 RangExpert

Inscrit le: 08 Juin 2006
Messages: 169

Posté le: Lun 15/01/2007 17:49 Sujet du message:

Si ! Je l'exploite absolument sans ordinateur. Ceci dit, la complexité est très liée au nombre de candidats qui ne sont pas déjà localisés dans des pseudo cases... Il faut donc éviter les blocs surchargés pour ne pas s'enliser. Dans le cas présent, la méthode etait utilisable à peu près sur n'importe quel bloc et j'en ai étudié plusieurs (entièrement à la main) avant de constater que le deuxième bloc horizontal etait le point faible... Ceci dit, je pense que cette méthode se prète très bien à une résolution automatisée par ordinateur, et permet d'intégrer dans un solveur les méthodes liées à l'unicité de façon pertinente et efficace.

BONJOUR
Sudoka Expert
Grille Extra 122 RangExpert

Inscrit le: 23 Aoû 2006
Messages: 867
Localisation: Courcelles-Les-Montbéliard (25420)

Posté le: Mar 16/01/2007 0:01 Sujet du message:

papyg a écrit:

Bonsoir à tous,

BONJOUR : en transcrivant sous forme de forme chaîne votre première élimination,
vous auriez vu qu'il s'agit en fait d'une boucle :

5h9—4h9 / 4e9—3e9 / 3e23—3f1 / 3i1—3i2 / 5i2—5i78 / @
qui élimine également 4d9, 3b1
... mais on ne va pas beaucoup plus loin avec!
papyg

Merci Papyg

Il me semblait qu'il s'agissait d'une boucle, sans en être sur... donc dans le doute, je ne mentionne rien

Je vais imprimer les deux formules que vous m'avez donné, j'essayerai de spécifier la nature de mes analyses, sur les prochaines grilles.

Merci pour la 123, j'ai cru devoir recourir au RI pour la résoudre.
_________________
Amicalement
Bonne journée

BONJOUR

leon1789
Sudoka Expert
Grille Extra 122 RangExpert

Grille Extra 122 18040515694533b98055045

Inscrit le: 02 Aoû 2006
Messages: 495

Posté le: Dim 21/01/2007 21:56 Sujet du message:

Bonsoir... j'arrive bien après la bataille, mais voici une toute petite chaîne tueuse Grille Extra 122 Icon_smile

Juste après la tournée des popotes, à 31 cases remplies, on en est à :

Code:

a b c d e f g h i
+--------------------+--------------------+--------------------+
1 | 6 134 5 | 8 2 34 | 7 9 13 |
2 | 29 1348 14 | 157 349 57 | 1256 12568 135 |
3 | 29 138 7 | 15 39 6 | 125 1258 4 |
+--------------------+--------------------+--------------------+
4 | 4 67 89 | 36 1 389 | 59 357 2 |
5 | 1 5 289 | 234 7 23489 | 49 34 6 |
6 | 3 67 29 | 246 5 249 | 149 147 8 |
+--------------------+--------------------+--------------------+
7 | 8 14 14 | 9 6 257 | 3 25 57 |
8 | 57 9 3 | 2457 8 2457 | 12456 12456 157 |
9 | 57 2 6 | 3457 34 1 | 8 45 9 |
+--------------------+--------------------+--------------------+

eqc A en g3(125), i1(13), de liberté 2
als B en a3(29), b3(138), d3(15), e3(39), h3(1258), de liberté 1
eqc C en a3(29), e3(39), g3(125) de liberté 2
als D en c4(89), f4(389), g4(59), de liberté 1

A(2) --25-- B --1-- C(2) --5-- D

somme des libertés - somme des contraintes (charnières) = 6-4 = 2

Tout candidat voyant trois (2+1) éléments du réseau est éliminé.
Par exemple, le f1#3 voyant les 3 de A, de C, et D.

..et la grille se termine avec les choix uniques.

» Grille Extra 23
» Grille Extra 46
» Grille Extra 40
» Grille Extra 88
» Grille Extra 107