Unicité de la solution d'une grille

Vous bloquez sur une grille ou vous souhaitez débloquer les sudokistes, c'est par ici...

Unicité de la solution d'une grille

Messagepar patrick_b » Mer 5 Jan 2011 18:34

Yep,

Suite à mon précédent message je m'interroge sur ce qu'on appelle une solution unique pour une grille.

En gros.. L'unicité de la solution ne dépend-elle pas de la technique employée ?

Si en employant une technique type "brute-force" (essayer toutes les combinaisons possibles) une grille peut avoir plusieurs solutions mais qu'en se cantonnant à toutes les techniques logiques connues elle n'a qu'une solution [EST-CE POSSIBLE ?] cette grille est-elle quand même incorrecte/mauvaise/toute pourrite/et-j'en-passe ??

Un exemple quand même.. On ne tombe sur aucune incohérence en faisant cette grille, pourtant elle a plusieurs solutions (j'en mets que deux, on voit la variation en L5C1/L5C2) :
Code: Tout sélectionner
..9.86.41
52...3.7.
4...2.3..
6.2831795
..52746..
8376951.4
..4.6...2
.5.9...63
16.45.9..

379586241
526143879
481729356
642831795
195274638
837695124
914367582
758912463
263458917

379586241
526143879
481729356
642831795
915274638
837695124
194367582
758912463
263458917



Patrick
patrick_b
 
Messages: 32
Inscription: Ven 31 Déc 2010 17:11

Re: Unicité de la solution d'une grille

Messagepar Timothy » Mer 5 Jan 2011 20:04

1 solution unique ?ça veut dire qu’il y a qu'1 solution qui respecte les régles du sudoku

pour vérifier qu’il y a qu’une seule et unique solution ? il faut seulement ne pas utiliser cette technique car tu ne sait pas encore qu’elle est unique !cette technique ce base là dessus justement,c’est la conséquence

exemple :grille de e-sudoku 6x6 n°331

-avec le RI tu déduit 4#l3c6 et 4#l4c6 qui arrive à 1 solution
-si tu faite le contraire normalement tu arrive à 1 impossibilité
->preuve que la grille a 1 solution unique

je sais pas si c’est très clair...
Facile=0'39 ;Moyen=0’46 ;diff=1’00 ;diabo=1'20 ;RGT=3'45
global=0'54+1’21+1'40+1'26=5'21
Timothy
 
Messages: 1523
Inscription: Jeu 22 Oct 2009 22:29

Re: Unicité de la solution d'une grille

Messagepar Fred76 » Jeu 6 Jan 2011 01:18

Salut Patrick,

patrick_b a écrit:Suite à mon précédent message je m'interroge sur ce qu'on appelle une solution unique pour une grille.
En gros.. L'unicité de la solution ne dépend-elle pas de la technique employée ?


Non, l'unicité de la grille ne dépend pas de la technique employée.

Il y a exactement 3 cas de figure pour les grilles de sudoku:
  • la grille n'a aucune solution. Elle est fausse et donc, une contradiction apparaîtra, qui empêchera de trouver une solution à la grille.
  • la grille a une unique solution. Il y a une seule manière de remplir la grille de manière à ce que les règles soient respectées.
  • la grille a plusieurs solutions.

Le créateur de grilles tente d'éviter les cas N°1 et 3 pour ne présenter que des grilles à solution unique.

Les techniques d'unicité:
Certaines techniques ont été développées (rectangle interdit et autres boucles interdites) prenant en compte le fait que la grille a une unique solution. Si on sait que la grille a une unique solution, l'utilisation de ces techniques peut s'avérer utile et peut faire gagner pas mal de temps pour la résolution de grilles.
Quel est l'effet de l'utilisation de ces techniques sur une grille à solutions multiples? dans la majeure partie des cas, si on utilise cette technique alors que la grille a plusieurs solution, ça va sélectionner arbitrairement une solution. La grille n'en aura pas moins plusieurs solutions, mais on ne le remarquera pas, n'en trouvant qu'une seule.

Le créateur doit donc s'assurer que la grille a une unique solution avant de la résoudre en utilisant les techniques d'unicité ! Une fois qu'on a prouvé que la grille a une unique solution, on peut utiliser ces techniques.

J'étais un adepte des techniques d'unicité autrefois, je les utilise moins maintenant:
  • d'une part je crée des grilles, donc j'ai la nécessité de les résoudre sans utiliser ces techniques pour prouver la solution unique.
  • Il m'arrive de tester les grilles d'autres auteurs, notamment pour des tournois. Dans la plupart des cas j'essaie d'éviter d'utiliser les techniques d'unicité: au cas ou la grille aurait plusieurs solutions (ce qui peut arriver même à de bons auteurs...), je peux mettre en garde l'auteur qui peut ainsi corriger sa grille. Si j'utilise la technique d'unicité parce que je ne vois pas d'autre moyen, j'en informe l'auteur, qui saura ainsi que le testeur n'a pas vérifier l'unicité de la solution.

J'espère que ça t'aide à y voir plus clair ;-)

Bonne continuation dans la création de grilles !

Fred
Facile: 45s; Moyenne: 0'58; Difficile: 1'27; Diabo: 1'43; Global: 6'38
Image LIVRE DE SUDOKU
http://sudokuvariante.blogspot.com/
http://sudokuvariante.forumactif.com/
Avatar de l’utilisateur
Fred76
 
Messages: 1436
Inscription: Mer 11 Mar 2009 12:43
Localisation: devant l'ordi

Re: Unicité de la solution d'une grille

Messagepar patrick_b » Jeu 6 Jan 2011 14:30

Bonjour et merci pour vos réponses !

Je commence à y voir plus clair mais quand même il y a un truc que je ne comprends pas, désolé hein !!

Peut-on dire qu'une grille a plusieurs solutions si en ignorant toute forme de technique on place arbitrairement une valeur ou l'autre, la grille sera résolvable quand même ?

Ci dessous un exemple tout bête (un cas concrêt m'aidera sûrement mieux à bien comprendre le truc).
L'outil de résolution du site mots-fleches me dit qu'il y a plusieurs solutions possibles hors je ne vois pas 50 façons de résoudre la grille. Si je tire un candidat au pif en L7C4 effectivement je pourrai terminer la grille dans les deux cas (avec un 4 ou 5). Mais si je me base sur "la règle du rectangle interdit" j'enlève 4 et 5 de L5C6 la grille se termine sans avoir de choix arbitraire à faire !

step_56.png


Merci pour votre patience :(
Patrick
patrick_b
 
Messages: 32
Inscription: Ven 31 Déc 2010 17:11

Re: Unicité de la solution d'une grille

Messagepar Timothy » Jeu 6 Jan 2011 15:03

ton exemple est contradictoire,en effet il y a 2 RI :
-celui du doublet 45 qui implique l5c6=2
-mais tu 1 autre RI d’un autre type qui s’étale sur plusieurs régions qui implique l5c4=4,autre solution,différente de la premiere

ça dépend comment on le voit,il y a donc 2 façon de résoudre !
Facile=0'39 ;Moyen=0’46 ;diff=1’00 ;diabo=1'20 ;RGT=3'45
global=0'54+1’21+1'40+1'26=5'21
Timothy
 
Messages: 1523
Inscription: Jeu 22 Oct 2009 22:29

Re: Unicité de la solution d'une grille

Messagepar Fred76 » Jeu 6 Jan 2011 15:11

Puisque ta grille a plusieurs solutions, tu ne peux pas appliquer la technique du rectangle interdit.
Comme je l'ai expliquée dans mon post précédent, cette technique tient compte du fait qu'on est sûr que la grille a une seule solution. Le rectangle est interdit du moment qu'on a qu'une solution. Regarde cette grille:
Image
Elle a 2 solutions: on peut placer arbitrairement les deux 6 et 7 restant. Pourtant la technique du rectangle interdit nous interdirait de placer un seul chiffre..
Ton exemple est très bon, puisqu'il mélange un rectangle interdit et une boucle interdite: tu as vu le rectangle interdit en région 5 et 8. Mais si on connaît bien les boucles interdites, on peut en voir une dans les régions 1, 2, 3, 4 et 5 avec les chiffres 24. L'utilisation de cette technique nous obligerait à enlever le 2 et le 4 de L5C6, conduisant exactement à l'autre solution qu'en utilisant le rectangle interdit.

Je vais essayer de fabriquer une grille à 2 solutions qui imbrique 2 RI pour que ce soit plus clair.

Fred
Facile: 45s; Moyenne: 0'58; Difficile: 1'27; Diabo: 1'43; Global: 6'38
Image LIVRE DE SUDOKU
http://sudokuvariante.blogspot.com/
http://sudokuvariante.forumactif.com/
Avatar de l’utilisateur
Fred76
 
Messages: 1436
Inscription: Mer 11 Mar 2009 12:43
Localisation: devant l'ordi

Re: Unicité de la solution d'une grille

Messagepar Fred76 » Jeu 6 Jan 2011 15:17

Et hop regarde cet exemple qui devrait être la révélation pour toi :mrgreen: :

Image

Fred
Facile: 45s; Moyenne: 0'58; Difficile: 1'27; Diabo: 1'43; Global: 6'38
Image LIVRE DE SUDOKU
http://sudokuvariante.blogspot.com/
http://sudokuvariante.forumactif.com/
Avatar de l’utilisateur
Fred76
 
Messages: 1436
Inscription: Mer 11 Mar 2009 12:43
Localisation: devant l'ordi

Re: Unicité de la solution d'une grille

Messagepar patrick_b » Jeu 6 Jan 2011 15:29

Ah ben voilà !! Merveilleux super merci !
patrick_b
 
Messages: 32
Inscription: Ven 31 Déc 2010 17:11


Retourner vers Forum d'entraide

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 4 invités