Envoyé par
Guardian
Ce qui serait envisageable c'est que des participants au défit proposent un article sur base de leur travail en complétant au besoin le code et les explications qui l'accompagnent pour en faire un tutoriel.
Mais c'est une autre histoire...
Ouais, pourquoi pas ...
Enfin bref, pour revenir un peu au sujet du défi, je vais parler sudoku 
Comme je ne pense pas me remettre a programmer le solveur, je laisse ici les idées que j'ai eu, et si quelqu'un se sent le courage et l'envie de coder, qu'il le code !
Premierement, on peut remarquer qu'un sudoku peut être assimilé a une matrice à 3 dimensions de 9*9*9, contenant que des booleans, par exemple :
TSudoku = array [Lignes,Colonnes,Candidats] of boolean //(bien sur, pour optimiser, faudra changer ca ...)
Ainsi, si équivaut à : Le candidat 8 est interdit dans la ligne 5, colonne 3.
Je noterai par la suite [x,..,y] la ligne des valeurs de [x,1,y] à [x,9,y]. Idem pour chaque dimension.
De meme, je noterai [x,..,..] le plan de valeurs allant de [x,1,1] à [x,9,9].
Résoudre un sudoku reviendra a ce que, sur chacune des 3 dimensions de la matrice, chaque "ligne" de boolean ne contienne qu'un seul true :
Ainsi, par exemple, pour x et y allant de 1 à 9, on ait [x,y,..], [x,..,y], [..,x,y] qui ne contiennent chacune qu'un seul true.
Donc, ajouter un V dans une ligne L et une colonne C revient a mettre à false tout les éléments qui sont présents sur les 3 dimensions de la case [L,C,V].
Donc en gros :
1
2
3
| [L,C,..]:=False
[L,..,V]:=False
[..,C,V]:=False |
Nous pouvons ensuite différencier plusieurs types de méthodes logiques.
Premièrement, celles qui ne travaillent que sur une ligne :
- Candidat Unique (une case ne contient qu'un seul candidat)
- Emplacement Unique (une ligne ou colonne ne contient qu'un seul candidat)
Ensuite, celles qui travaillent sur un plan :
- Candidats Doubles, Triples, ...
- Paires, triplets, ... cachés
- X-Wing, SwordFish ..
Enfin, celles qui travaillent sur la grille entière. Ce dernier cas n'a pas d'améliorations à apporter.
Candidat unique :
Nous travaillons sur la dimension n°3 de la grille ([x,y,..]) : C'est à dire que l'on fixe le no de ligne et le no de colonne, et que l'on regarde si il n'y a qu'un candidat.
Emplacement unique :
Nous travaillons sur la dimension n°1 et 2 de la grille ([x,..,y] et [..,x,y]) : On regarde dans une ligne ou une colonne précise si un candidat est présent une seule fois.
Méthode générale sur une ligne :
Nous remarquons que ces techniques sont tres semblables. Le truc serait donc de creer une procedure qui, pour chaque "ligne" sur chaque dimensions de la matrice, compte le nombre de "true". Si il vaut 1, nous pouvons placer la valeur. (il y a 9*9*3 = 243 "lignes" de valeur à vérifier)
Voila pour les méthodes sur une ligne.
Faisons de même pour les méthodes s'appliquant sur un plan entier.
Candidats Doubles, Triples, ... :
Nous fixons soit une ligne, soit une colonne. Nous travaillons donc soit sur un plan [x,..,..], soit sur [..,x,..]. Nous généraliserons en appelant cette méthode de résolution CandidatsNièmes, ou N est le nombre de candidats a chercher. Si N=2, alors on cherche des candidats doubles.
Par exemple, pour la colonne 3 : on regarde si on peut trouver N cases contenant chacune au maximum N candidats, et si on a en tout N candidats différents. (pour ceux qui aiment bien se creuser la tete : si on a moins de N candidats différents, la grille ne possede pas de solutions.) Nous pouvons supprimer les N candidats de toutes les autres cases.
Exemple concret !!
1
2
3
4
| | | | | | | | |
8 | 2 3 | 2 3 9 | 1 2 6 | 1 2 3 7 | 1 3 6 7 | 4 | 2 9 | 5
| | | | | | | |
X X X |
Nous remarquons des candidats triples dans les cases marquées d'un "X". Pour notre algo, N=3. Nous trouvons 3 cases, qui contiennent :
1
2
3
| .23......
.23.....9
.2......9 |
Toutes ces cases contiennent en tout 3 candidats différents : le 2, le 3 et le 9.
Paires, triplets cachés :
De meme, nous fixons soit une ligne, soit une colonne. Nous travaillons donc soit sur un plan [x,..,..], soit sur un plan [..,x,..]. On appelle la méthode Nièmes Cachés, N donne le nombre de candidats cachés.
Reprennons la colonne 3 :
on regarde si on peut trouver N cases contenant chacune au minimum N candidats, et si on a en tout N candidats communs.(de meme : si on a plus de N candidats communs, la grille ne possede pas de solutions.)
Nous pouvons supprimer les autres candidats des cases concernées.
Remarque importante : les Nièmes Cachés et les Candidats Niemes sont étroitements liés : sur un élement (ligne, colonne) de la grille, si on a 5 cases non trouvées, rechercher des candidats Nième revient à chercher des (5-N)ièmes cachés.
Exemple :
Dans l'exemple du dessus, on a :
8 | 2 3 | 2 3 9 | 1 2 6 | 1 2 3 7 | 1 3 6 7 | 4 | 2 9 | 5
on a trouvé des candidats triples (N=3), et on a 6 cases vides. On doit donc pouvoir trouver un (6-3=3) triplet caché.
En effet, dans les cases 4,5,6, nous avons bien un triplet caché de 1,6,7.
Faisons un tableau récapitulatif sur ces deux méthodes, dans notre cas de la colonne 3 :
1
2
3
4
5
6
7
8
9
10
| ValeursTrouvées = ...45..8.
CandidatsNonFixés = 123..67.9
CasesTrouvées = 1.....7.9
CasesVides = .23456.8.
| Cand. Triples | Triplets Cachés | Somme
------------------------------------------------------------------------
Dans les cases | .23....8. | ...456... | CasesVides
Cand. concernés | .23.....9 | 1....67.. | CandidantsNonFixés
------------------------------------------------------------------------ |
On peut aussi dessiner le plan de booleans et on obtient :
1
2
3
4
5
6
7
8
9
10
11
12
13
| Candidat
^
9 | X X
|X
| XX Rouge = Déja placé
| X X Bleu = Candidats Triples
| X Vert = Triplet cachés
| X Noir = A supprimer
| XX XX
| XXXX X
1 | XXX
+--------->
1 9 N° Case |
Nous remarquons de nombreuses choses, mais on va s'arreter la ...
X-Wing, SwordFish :
Nous fixons une valeur. Nous travaillons donc sur un plan [..,..,x]. Dans mon solveur, j'ai appelé ces méthodes "Etoile à N branche", ou N est le nombre de lignes ou colonnes. N=2 : X-Wing, N=3 : SwordFish, N=4 : JellyFish.
On prends le 2 comme valeur. Le principe est donc de trouver N lignes dont chacune contient au maximum N fois la valeur 2, et que les 2 de toutes ces lignes soit sur N colonnes différentes (si on a moins de N colonnes différentes, la grille n'a pas de solution) Nous pouvons supprimer les 2 dans les N colonnes, qui ne sont pas dans les N lignes de départ.
Un exemple de grille, les X sont les positions des "1" :
1
2
3
4
5
6
7
8
9
10
11
12
13
| N° Ligne
^
9 |XX X
| X
|X X X
| X
|X X
| X
|X X X
| X
1 |XX X
+--------->
1 9 N° Colonne |
Nous remarquons un SwordFish (N=3) sur les lignes 3,5,7. Nous remarquons aussi un X-Wing (N=2) sur les colonnes 2,9.
En couleurs, ca donne :
1
2
3
4
5
6
7
8
9
10
11
12
13
| N° Ligne
^
9 |XX X
| X Rouge = valeurs placées
|X X X Bleu = X-Wing sur les colonnes
| X Vert = SwordFish sur les lignes
|X X Noir = Candidats à supprimer
| X
|X X X
| X
1 |XX X
+--------->
1 9 N° Colonne |
Encore une fois, on a
SwordFish+XWing = NbLignesNonTrouvees
Méthode générale sur un plan :
On a une forte similitude avec les candidats Niemes, les Niemes cachés et les étoiles a N branches.
Nous alons donc établir une méthode générale. Cette méthode prendra en argument un plan. Sur chaque plan, nous alons tout d'abord compter le nombre de valeurs fixes Nf, et le soustraire à 9 : on a N=9-Nf. Nous allons ensuite chercher dans les 2 sens, la configuration qui nous interresse, a savoir N lignes dont les "X" sont à N emplacements différents.
Finalement, ces 2 méthodes générales permettent de faire le travail de nombreuses techniques de résolution. Maintenant, plusieurs problemes arrivent : Il faut trouver un moyen permettant d'isoler rapidement une ligne ou un plan de notre matrice pour pouvoir l'analyser. Un autre problème de taille : la représentation des "zones", "régions", "blocs" ...
Enfin voila. Ceci sont toutes mes observations sur le sudoku. Si quelqu'un veut les coder, libre a lui. Il serait interressant de voir après optimisation jusqu'à quels temps on peut descendre !!
A+
Mick605
.
Création d'un système de chat en Pascal
Répondre avec citation
Partager