SUDOKU PASCAL
athanor70
Messages postés
3
Date d'inscription
samedi 26 mai 2007
Statut
Membre
Dernière intervention
26 mai 2007
-
26 mai 2007 à 00:54
Doc VB Messages postés 16 Date d'inscription vendredi 24 novembre 2000 Statut Membre Dernière intervention 20 juillet 2007 - 20 juil. 2007 à 14:41
Doc VB Messages postés 16 Date d'inscription vendredi 24 novembre 2000 Statut Membre Dernière intervention 20 juillet 2007 - 20 juil. 2007 à 14:41
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/42841-sudoku-pascal
https://codes-sources.commentcamarche.net/source/42841-sudoku-pascal
20 juil. 2007 à 14:41
Je me demande s'il n'y a pas une faute de frappe, dans la liste des "Rectangles" :
...
30-35-40-45
32-27-42-47 => je pense qu'il faut plutôt lire "32-37-42-47" non ?
34-38-44-48
...
En poussant la recherche, un résultat m'a interpellé dans la liste des combinaisons à huit chiffres (la quatrième ligne):
30-32-35-37-40-42-45-47
Est-ce que cette combinaison de 8 chiffres à vraiment une existence propre ? elle est constituée de 2 rectangles déjà cités précédemment (le "30-35-40-45" et le "32-37-42-47"). Ainsi, ne conserver qu'un seul chiffre sur les huit ne suffirait pas à rendre la grille faisable. Enfin de toute façon cette combinaison semble redondante avec celles déjà mémorisées.
Sinon, merci pour cette belle étude sur les combinaisons à prendre en considération lors de l'élaboration d'une grille.
17 juin 2007 à 18:52
17 juin 2007 à 18:47
produisaient des solutions multiples. Si je réussis à l'ajouter à ce message je te livre le résultat de mes recherches.
Après avoir éliminé tous ces cas j'ai encore trouvé une autre combinaison(très rare) de cases donnant 2 solutions, mais devant la complexité du problème j'ai abandonné.
D'autre part la difficulté du problème ne dépend pas que du nombre de cases vides. Par exemple avec 45 cases vides(le minimum) on peut avoir des problèmes très faciles ,moyens ou très difficiles. Je ne vois pas comment traiter cette
difficulté.GRILLE DE TRAVAIL :
Il faut vider des cases de la grille solution.
D'après ce que j'ai pu observer il semblerait qu'un facteur de la difficulté soit le nombre de cases vides.(je pense que leur
position doit aussi avoir une influence , mais je ne vois pas comment en tenir compte)
Il semblerait que pour les faciles ce nombre soit de 45 à 47,pour les moyennes de48 à 50, pour les difficiles de 51 à 53 et au delà de
53 pour les diaboliques.
Dans la grille solution, il existe des ?rectangles? dont les cases sommet ne contiennent que 2 chiffres.
si l'on vide les 4 cases , 2 cas peuvent se présenter
a) le rectangle est formé avec 4 zones(chiffres gras)
s'il il reste dans l'une des 4 zones concernées un chiffre 3 ou un chiffre 1 il n'y aura pas d'incertitude .
.S'il ne reste ni 1 ni 3 dans l'une des 4 zones
on aura 2 solutions possibles, celle affichée ou celle obtenue en permutant 3 et1 dans les colonnes ou dans les lignes
j'ai opté pour la solution qui consiste à ne pas vider, dans la grille de
travail, un des coins du rectangle. On effectue une recherche de tous ces rectangles et on impose
pour la suite de ne pas vider un de ces coins
6 2 4 7 1 5 9 3 8
7 1 5 3 9 8 2 6 4
8 3 9 4 6 2 5 7 1
5 6 2 8 4 3 1 9 7
9 7 1 5 2 6 4 8 3
4 8 3 1 7 9 6 5 2
3 9 8 2 5 1 7 4 6
1 5 7 6 8 4 3 2 9
2 4 6 9 3 7 8 1 5
b)le rectangle est formé sur deux zones(chiffres gras italiques) :
On est alors obligé de conserver un des coins
.
Il existe aussi sur 3 zones alignées verticalement ou horizontalement ce que j'appelle des ?hélices? ;
Chiffres gras, soulignés vague : hélice horizontales, chiffres gras soulignés : hélices verticales.
Si pour une hélice toutes les case sont vides on aura 2 solutions obtenues par permutation de chiffres dans les 3 colonnes pour les
hélices horizontales ou dans les lignes pour les hélices verticales.
Il faudra donc conserver au moins une case non vide pour chaque hélice.
Selon les grilles le nombre des rectangles et des hélices est très variable. Dans l'exemple ci-dessus je pense qu'on est dans un cas
extrême car il contient 14 hélices et 18 rectangles.
On peut aussi obtenir des hélices à partir de 6 carrés, soit à la verticale soit à l'horizontale
Par exemple dans la grille ci-dessus les cases 1,0(2) ; 3,0(7) ;6,0(9) ;
1,6(9) ; 3,6(2) ;6,6(7) ; pour un exemple horizontal
ou les cases 4,2(6) ;4,5(7) ;4,6(5 ;
6,2(5) ;6,5(6) ;6,6(7) ;
ce qui porte à 21 le nombre des hélices
Heureusement ces hélices et ces rectangles ont des points communs que l'on recherchera et on commencera par conserver
les chiffres placés dans ces cases et ensuite on y ajoutera une case des ?célibataires?.
Dans le cas de cette mauvaise grille le nombre de cases qui doivent impérativement ne pas être vidées est de21 dont
6 dans le carré 00( les carrés de 9 chiffres ayant des coordonnées de 0,1,2).
Nouvelle découverte :
En essayant des grilles pour lesquelles on avait remédié aux problèmes précédents il en est apparu un autre semblable aux précédents.
4 2 6 9 3 5 1 7 8
5 1 7 8 2 4 9 3 6
3 8 9 1 6 7 2 4 5
2 6 1 7 5 8 4 9 3
7 9 5 3 4 2 6 8 1
8 4 3 6 1 9 5 2 7
1 3 2 4 7 6 8 5 9
9 7 4 5 8 1 3 6 2
dans la grille ci-dessus, on a marqué en italique ce que je nomme une ?spirale? qui si dans la grille de travail n'a au départ aucun représentant, conduira à deux solutions par permutation es chiffres dans les colonnes.
Il faut conserver au départ un des 8 chiffres .
L'étude détaillée de cette grille a montré qu'elle possédait :
16 rectangles, 6 hélices et 20 spirales.
On recherche toutes les cases concernées par ces 42 cas et on détermine le nombre de fois où elles apparaissent.
On commence par retenir la plus fréquente ,qui entre dans la liste des cases à ne pas vider, et on élimine des listes les rectangles ,hélices
et spirales qui la contenaient. On continue jusqu'à ce que les listes de rectangles ,hélices et spirales soient vides.
Pour cette grille on obtient une liste de 17 cases à conserver(54,04,24,21,31,41,01,26,44,56,66,03,68,84,00,30,42)
Autre Problème:
Dans cette grille : 1 8 3 4 6 2 9 7 5
7 2 4 5 1 9 3 8 6
6 5 9 8 3 7 4 1 2
2 1 5 7 9 3 6 4 8
3 9 6 1 4 8 5 2 7
8 4 7 2 5 6 1 3 9
4 3 2 9 8 5 7 6 1
9 6 8 3 7 1 2 5 4
5 7 1 6 2 4 8 9 3
si aucun des chiffres en gras italique n'est conservé, on a deux solutions obtenues par permutation des chiffres rouges dans chaque zone.
Cette disposition que je nomme T(avec pied horizontal ou vertical) est relativement facile à détecter pour fixer au moins un chiffre.
Autre Problème (équerre) :
Dans la grille ci- dessous
1 8 2 7 3 9 4 5 6
9 3 7 4 5 6 2 8 1
6 5 4 8 2 1 9 7 3
3 1 6 2 4 5 8 9 7
5 4 8 9 7 3 1 6 2
7 2 9 1 6 8 3 4 5
8 7 5 3 9 2 6 1 4
2 6 1 5 8 4 7 3 9
4 9 3 6 1 7 5 2 8
si les cases recevant les chiffres soulignés sont vidées il y aura deux solutions obtenues par permutations ?en diagonale?
des chiffres de la zone36(qui contient les 4 chiffres 4,5,6,7) et permutation entre 4 et 6 d'une part et 7 et 5 d'autre part .
Autre problème (peut-être le dernier)(spirales 10 cases)
Dans cette grille
5 2 4 8 1 6 7 3 9
7 1 3 2 9 4 6 8 5
8 6 9 5 3 7 2 1 4
2 7 8 1 6 9 4 5 3
9 5 1 4 2 3 8 7 6
4 3 6 7 5 8 9 2 1
1 4 5 9 7 2 3 6 8
3 8 2 6 4 1 5 9 7
6 9 7 3 8 5 1 4 2
Si aucun des chiffres en rouge n'est donné, on obtient 2 solutions par permutation dans les colonnes des chiffres considérés
En résumé :
Autre problème : portant sur 6 cases mais non alignées, formant un ANGLE
1 4 5 7 8 9 3 2 6
2 6 7 3 1 4 8 9 5
3 8 9 2 5 6 1 4 7
8 2 1 4 3 5 7 6 9
5 7 4 6 9 1 2 3 8
9 3 6 8 7 2 5 1 4
6 5 2 1 4 7 9 8 3
4 9 8 5 2 3 6 7 1
7 1 3 9 6 8 4 5 2
dans cette grille si aucun des chiffres soulignés n'est donné on obtient encore deux solutions possibles en permutant ces chiffres
Conclusion :
L'étude complète de cette grille donne :
-19 rectangles,
-8 hélices et angles
-19 spirales, tes et équerres,
-10 spirales sur 10 cases.
Compte tenu des points communs il suffit de fixer 15 cases pour ne pas obtenir de solutions multiples
1 - - 7 -- - - -
- 6 - - - 4 - - -
- - 9 2 - - 1 - 7
8 - - - 3 - - 6 -
- - - 6 - - 2 - -
- - - - - - - - -
- - - - - - - 8 -
- - - - - - - - -
- - 3 - - - - - -
Si l'on opte pour une répartition symétrique par rapport au centre des cases vides (comme c'est souvent le cas dans
les différentes publications) on aura alors 30 cases pleines donc 51 vides , ce qui correspond à un problème
assez difficile. On peut rajouter à son gré des cases pleines jusqu? à 45 cases vides( le minimum rencontré partout).
Annexe :
Ci-dessous les coordonnées (x de 0 à 8,y de 0 à 8 de haut en bas ) des cases impliquées dans les différentes figures
Présentes dans la grille ci- dessus :
00-02-60-62
01-02-31-32
03-06-73-76
11-18-41-48
12-17-22-27
12-14-82-84
13-14-63-64
23-25-73-75
26-28-86-88
27-28-57-58
30-35-40-45
32-27-42-47
34-38-44-48
35-36-75-76
51-58-61-68
60-64-70-74
61-66-71-76
63-67-73-77
74-76-84-86
03-33-83-05-35-85
24-34-84-25-35-85
31-33-37-51-53-57
31-33-36-41-43-46
62-65-68-72-75-78
72-75-77-82-85-87
04-23-00-20-54-53
43-55-47-57-13-15
13-43-53-63-15-45-55-65
00-03-04-07-20-23-24-27
30-32-35-37-40-42-45-47
30-34-35-38-40-44-45-48
32-34-37-38-42-44-47-48
60-61-64-66-70-71-74-76
60-63-64-67-70-73-74-77
61-63-66-67-71-73-76-77
61-64-65-68-81-84-85-88
70-71-73-78-80-81-83-88
16-08-56-76-58-78-14-04
30-52-34-36-54-56-80-82
50-41-00-70-01-71-54-44
52-47-26-76-27-77-55-45
80-71-10-50-11-51-83-73
10-21-20-11-80-81-24-14
03-24-23-04-53-54-27-07
40-52-50-42-20-22-58-48
43-55-53-45-63-65-57-47
03-23-33-73-83-05-25-35-75-85
01-02-05-06-08-21-22-25-26-28
30-31-33-35-36-40-41-43-45-46
31-32-33-36-37-41-42-43-46-47
31-33-34-36-38-41-43-44-46-48
60-62-64-65-68-70-72-74-75-78
61-62-65-66-68-71-72-75-76-78
62-63-65-67-68-72-73-75-76-78
60-62-63-66-67-80-82-83-86-87
72-74-75-76-77-82-84-85-86-87
28 mai 2007 à 19:13
j'ai ecris ce programme seulement pour tester ma procedure de solution (quelle solution, elle resoud les grilles de niveaux 1 et 2 (facile et moyenne)) ....................
je fais de mon mieux pour rewrite this program !!!
thinks a lot..
26 mai 2007 à 00:54
il ne suffit pas de laisser plus de cases vides pour que le sudoku soit plus difficile comme tu penses le croire (si je lis bien ton code). Certes cela contribue un peu mais pas forcement. Ayant ecrit le logiciel Sudoku Imperator en delphi, je peux t'assurer que c'est bien plus complexe que cela... la difficulté se fait en fonction des methodes que doit utiliser le joueur pour trouver la solution UNIQUE. trop de logiciels se limitent comme le tiens a vider plus de cases pour augmenter la difficulté. cela ne fonctionne pas ainsi. Mais je suis sûr que tu vas trouver...
amicalement,
patrick