Discussion :

[Paille Pot]

Voilà je découvre le tcl/tk et je me suis dit : pourquoi ne pas faire un Sudoku avec ce petit langage bien sympa.
Mais je bloque sur le remplissage de la grille.
J'ai fait une grille et j'aimerais des conseils pour programmer un "resolveur" (je ne sais pas si ça se dit) de Sudoku.

Voici le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#!/usr/bin/wish
 
 
#afficher la grille
frame .f1
frame .f2
 
 
pack .f1 -side top
pack .f2 -side top
 
 
for {set i 0} {$i<3} {incr i} {
	for {set j 0} {$j<3} {incr j} {
		for {set k 0} {$k<3} {incr k} {
			for {set l 0} {$l<3} {incr l} {
				entry .f1.$i$j$k$l -textvariable e($i,$j,$k,$l) -width 1
			}
		}
	}
}
 
for {set i 0} {$i<3} {incr i} {
	for {set k 0} {$k<3} {incr k} {
		for {set j 0} {$j<3} {incr j} {
			for {set l 0} {$l<3} {incr l} {
				set r [expr $i*3+$k]
				set c [expr $j*3+$l]
				grid .f1.$i$j$k$l -row $r -column $c
			}
		}
	}
}
 
button .f2.quit -text "Quit" -command {exit 0}
button .f2.search -text "Search" -command {resolutionSudoku e}
pack .f2.search -side left
pack .f2.quit -side left
 
 
#resoudre le sudoku
 
proc resolutionSudoku {re} {
	upvar $re e
	for {set i 0} {$i<3} {incr i} {
		for {set k 0} {$k<3} {incr k} {
			for {set j 0} {$j<3} {incr j} {
				for {set l 0} {$l<3} {incr l} {
					puts -nonewline "$e($i,$j,$k,$l)"
				}
			}
			puts ""
		}
	}
}

Mon raisonnement serait de vérifier si le même chiffre est dans la colonne, dans la ligne et enfin dans le carré (3X3) "interieur"...

Si ça parle a quelqu'un...

Merci d'avance pour les conseils !!!

[habilité]

Salut.

1) Tu peux faire une grille de probabilités.
2) Suivant les réponses, il te suffit d'ôter les probabilités de la grille des probablités. Cette deuxième étape est la plus dure, car il faut ôter les probabilités selon l'horizontale, la verticale ainsi que le carré qui sont exposés par les probabilités.
3) Lorsque tu auras fait ces deux étapes, tu peux passer par un programme de résolution.

IMPORTANT: Un autre détail important pour la résolution dont il est nécessaire de faire attention lorsqu'il y a conflit entre probabilités est de choisir le bon pourcentage parmi des probabilités. Il est nécessaire de ne pas perdre de vue cet aspect-là dans la résolution pour des cas de SUDOKUS difficiles.

4) Une fois cela fait, il te reste à passer à l'interface graphique pour afficher les valeurs finales.


Cette méthode est toutefois complexe à réaliser. Peut-être que d'autres ont des méthodes plus simples...pour résoudre un SUDOKU de façon informatique.

A+

[Mathusalem]

il y a un excellent tutoriel pour résoudre très simplement, les sudokus en Prolog sur ce site, mais vu que tu veux te faire la main avec Tcl.

Ton raisonnement est bon pour les grilles simples, mais pour les difficiles ne donnant pas de 1ère case évidente, tu vas être dans les choux.

Essaye peut-être par backtracking il suffit à l'algorithme de choisir 1 pour la première cellule, puis 2 pour la prochaine, ainsi de suite tant qu'aucune contradiction n'apparaît. Lorsqu'une contradiction apparaît, l'algorithme essaie une autre valeur pour la cellule qui amène la contradiction. Une fois toutes les possibilités épuisées pour cette cellule, l'algorithme « revient sur ses pas » et recommence avec l'avant-dernière cellule.
Je sais c'est bourrin, mais ça marche dans tous les cas


Un algo plus évolué serait de déterminer pour chaque case la liste des possibilités. Quand une case n'a plus qu'une possibilité, on fixe et on écrit le chiffre et on l'enlève des possibilités des cases impactés.
Même soucis de démarrage que l'algo naïf : il faut que le programme puisse faire des hypothèses si il n'y a pas de case à 1 solution : il en essaye une jusqu'à résolution ou contradiction, etc.

[habilité]

Salut.

Pour votre information:

Voici les liens pour les méthodes de résolution des Sudoku:
http://hypo.ge.ch/www/math/html/root.html (voire histoire du Sudoku dans la rubrique (de côté gauche) sous Problèmes)
http://flying.guy.chez-alice.fr/solveMethodFr.htm
http://www.sudoku129.com/grilles/tips_intro.php
http://jeusegment.9online.fr/sudoku/programme.htm

A+

[Cthulhu_RLyeh]

Je viens de finir ma séance de Tp, et le sujet correspond à ce que tu voulais.

Tiens, voici une réponse, en utilisant du backtracking :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#
!/usr/bin/wish
 
frame .f1
frame .f2
 
pack .f1 -side top
pack .f2 -side top
 
for {set i 0} {$i<3} {incr i} {
	for {set j 0} {$j<3} {incr j} {
		for {set k 0} {$k<3} {incr k} {
			for {set l 0} {$l<3} {incr l} {
				set e($i,$j,$k,$l) " "
				entry .f1.$i$j$k$l -textvariable e($i,$j,$k,$l) -width 1
			}
		}
	}
}
 
for {set i 0} {$i<3} {incr i} {
	for {set k 0} {$k<3} {incr k} {
		for {set j 0} {$j<3} {incr j} {
			for {set l 0} {$l<3} {incr l} {
				set r [expr $i*3+$k]
				set c [expr $j*3+$l]
				grid .f1.$i$j$k$l -row $r -column $c
			}
		}
	}
}
 
button .f2.quit -text "Quitter" -command {exit 0}
button .f2.search -text "Résoudre" -command {resolution_Sudoku e}
pack .f2.search -side left
pack .f2.quit -side left
 
proc resolution_Sudoku {re} {
	upvar $re e
	set liste {1 2 3 4 5 6 7 8 9}
	set trouve [position_vide e]	
	if {[lindex $trouve 0]!=-10} {
		set i [lindex $trouve 0]
		set j [lindex $trouve 1]
		set k [lindex $trouve 2]
		set l [lindex $trouve 3]
		unset trouve
		foreach chiffre $liste {
			if {[carre e $chiffre $i $j] && [ligne e $chiffre $i $k] && [colonne e $chiffre $j $l]} {
				set e($i,$j,$k,$l) $chiffre
				update				
				resolution_Sudoku e
				set e($i,$j,$k,$l) " "
			}
		}
	} else {
		puts "C'est parti"
		update
		for {set i 0} {$i<3} {incr i} {
			for {set k 0} {$k<3} {incr k} {
				for {set j 0} {$j<3} {incr j} {
					for {set l 0} {$l<3} {incr l} {
						puts -nonewline "$e($i,$j,$k,$l)"
					}
				}
				puts ""
			}
		}
	}
}
 
proc position_vide {re} {
	upvar $re e
	set trouve {-10}
	for {set i 0} {$i<3} {incr i} {
		for {set j 0} {$j<3} {incr j} {
			for {set k 0} {$k<3} {incr k} {
				for {set l 0} {$l<3} {incr l} {
					if {$e($i,$j,$k,$l)==" "} {
						set trouve [list $i $j $k $l]
					}
				}
			}
		}
	}		
	return $trouve
}
 
proc carre {re chiffre i j} {
	upvar $re e
	set sortie 1
	for {set k 0} {$k<3} {incr k} {
		for {set l 0} {$l<3} {incr l} { 
			if {$chiffre == $e($i,$j,$k,$l)} {
				set sortie 0
			}
		}
	}
	return $sortie
}
 
proc ligne {re chiffre i k} {
	upvar $re e
	set sortie 1
	for {set j 0} {$j<3} {incr j} {
		for {set l 0} {$l<3} {incr l} {
			if {$chiffre == $e($i,$j,$k,$l)} {
				set sortie 0
			}
		}
	}
	return $sortie
}
 
proc colonne {re chiffre j l} {
	upvar $re e
	set sortie 1
	for {set i 0} {$i<3} {incr i} {
		for {set k 0} {$k<3} {incr k} { 
			if {$chiffre == $e($i,$j,$k,$l)} {
				set sortie 0
			}
		}
	}
	return $sortie
}

Assez simple, enfin, je pense !!

[habilité]

Salut.

J'ai essayé de lancer ton script sur Windows XP, mais il me donne une erreur...
Il me met une erreur du style:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
invalid command name "yb#"

alors que j'utilise le code suivant:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
#\ exec wish85 "$0" ${1+"$@"}
console show

Que faut-il faire pour que cela marche?
Merci d'avance.

A+