]> gitweb.pimeys.fr Git - sudoku.git/blob - sudoku.py
666110e2f89c51f6f2f1eb7a9bbd3acd7e00d5ee
[sudoku.git] / sudoku.py
1 #!/usr/bin/env python
2 # -*- coding: utf-8 -*-
3
4 """Résolution de sudoku."""
5
6 # Recodé le 12/03/13, parce que je retrouvais pas l'ancien
7 # … et que j'en avais marre du projet why3
8
9 import sudoku_types
10
11 VERBOSE = False
12
13 DEPTH = 0
14
15 # Fonctions logiques
16 def exists(l):
17 """Vérifie qu'au moins une valeur de l est vraie."""
18 return not all([not i for i in l])
19
20 def one(l):
21 """Vérifie que l contient une et une seule valeur de vérité."""
22 return sum([bool(i) for i in l]) == 1
23
24 def none(l):
25 """Vérifie que l ne contient aucune valeur de vérité."""
26 return all([not i for i in l])
27
28 class CheckError(Exception):
29 """Levée si une grille est insoluble."""
30 def __init__(self, msg):
31 Exception.__init__(self, msg)
32
33 def quick_input():
34 """Lit une chaîne et renvoie un les caractères un par un. Ne marche que pour le sudoku à caractère unique"""
35 chain = raw_input("Input (_=vide):")
36 # On remplace quand même les 0 par des _
37 chain = chain.replace("0", "_")
38 return [i for i in chain]
39
40 class Grid(object):
41 """Grille de sudoku, contenant des valeurs."""
42
43 def check_depth(self):
44 """Affiche la valeur de la profondeur d'hypothèse si on n'a jamais atteint ce niveau"""
45 global DEPTH
46 if self.depth > DEPTH:
47 # On affiche l'état avant de faire l'hypothèse
48 print self
49 print "Profondeur : %s" % self.depth
50 DEPTH += 1
51
52 def __init__(self, typ, values, depth=0):
53 if len(values) != typ.size:
54 raise ValueError("%s valeurs incompatibles avec le type de sudoku (%s)" % (len(values), typ.size))
55 self.typ = typ
56 self.values = [i for i in values] # On fait une copie de la liste pour avoir un passage par valeurs
57 self.possible = [[True for i in range(len(typ.chars))] for j in range(len(values))]
58 self.depth = depth
59 self.check_depth()
60
61 def case_filled(self, i):
62 """Dit si la case ``i`` contient une valeur."""
63 return self.values[i] in self.typ.chars
64
65 def deduce(self):
66 """Rajoute des valeurs dans les cases en déduisant de ``self.possible``.
67 On renvoie ``True`` si on a fait quelque chose."""
68 something = False
69 # Si une case ne peut plus contenir qu'un seul symbole, on le met dedans
70 for case in range(self.typ.size):
71 if not self.case_filled(case) and one(self.possible[case]):
72 place = self.possible[case].index(True)
73 self.values[case] = self.typ.chars[place]
74 if VERBOSE:
75 print "%s placé en %s [case]" % (self.typ.chars[place], place)
76 something = True
77 # Si un linked_field contient déjà tous les symboles sauf un, on le place dans la case restante
78 for field in self.typ.linked_fields:
79 for nchar in range(len(self.typ.chars)):
80 l_field = [self.possible[i][nchar] for i in field]
81 if one(l_field):
82 place = field[l_field.index(True)]
83 if not self.case_filled(place):
84 self.values[place] = self.typ.chars[nchar]
85 if VERBOSE:
86 print "%s placé en %s [field %s]" % (self.typ.chars[nchar], place, field)
87 something = True
88 return something
89
90 def __str__(self):
91 """Affiche la grille."""
92 return self.typ.render(self.values)
93
94 def update_possible(self):
95 """Enlève des possibilités en déduisant de ``self.values``."""
96 for case in range(self.typ.size):
97 if self.case_filled(case): # la case contient quelque chose
98 numchar = self.typ.chars.index(self.values[case])
99 # Il n'y a plus rien de possible dans cette case
100 for p in range(len(self.typ.chars)):
101 self.possible[case][p] = False
102 # Il est impossible que la valeur soit dans tout linked_field de cette case
103 for f in self.typ.linked_fields:
104 if case in f:
105 for c in f:
106 self.possible[c][numchar] = False
107
108 def is_full(self):
109 """Dit si la grille est pleine."""
110 return all([self.case_filled(i) for i in range(self.typ.size)])
111
112 def logic_solve(self):
113 """Résoud la grille uniquement par déduction.
114 Renvoie ``True`` si elle est entièrement résolue.
115 """
116 action = True
117 while action:
118 self.update_possible()
119 action = self.deduce()
120 return self.is_full()
121
122 def _first_empty(self):
123 """Renvoie l'index de la première case vide."""
124 for i in range(self.typ.size):
125 if not self.case_filled(i):
126 return i
127
128 def hypothesis(self):
129 """Émet une hypothèse."""
130 if self.is_full():
131 raise RuntimeError("Pas besoin de faire une hypothèse, la grille est pleine !")
132 # On prend la première case vide
133 where = self._first_empty()
134 # On choisi le premier symbole possible
135 what = self.possible[where].index(True)
136 return where, what
137
138 def check(self):
139 """Vérifie qu'une grille est toujours cohérente."""
140 # Les cases dans lesquelles on ne peut plus rien mettre
141 empty_cases = [none(self.possible[c]) for c in range(self.typ.size)]
142 for c in range(self.typ.size):
143 if empty_cases[c] and not self.case_filled(c):
144 # La case ne peut rien contenir et ne contient rien
145 raise CheckError("La case %s ne peut rien contenir !" % (c))
146 # Les linked_field dans lesquels un symbole ne peut plus être placé
147 for nchar in range(len(self.typ.chars)):
148 empty_fields = [none([self.possible[c][nchar] for c in f]) for f in self.typ.linked_fields]
149 for nfield in range(len(self.typ.linked_fields)):
150 field = self.typ.linked_fields[nfield]
151 lll = [self.values[c] == self.typ.chars[nchar] for c in field]
152 if empty_fields[nfield] and not exists(lll):
153 # Le field ne peut pas contenir le caractère et ne le contient effectivement pas
154 raise CheckError("Le field %s ne peut pas contenir de %s !" % (field, self.typ.chars[nchar]))
155
156 def is_valid(self):
157 """Répond ``True`` si la grille est cohérente."""
158 try:
159 self.check()
160 return True
161 except CheckError:
162 return False
163
164 def hypothetic_solve(self):
165 """Résoud en faisant des hypothèses.
166 ``self.update_possible`` doit avoir été appliqué."""
167 where, what = self.hypothesis()
168 charwhat = self.typ.chars[what]
169 daughter = Grid(self.typ, self.values, self.depth+1)
170 # On applique l'hypothèse
171 if VERBOSE:
172 print "Hypothèse : %s en %s." % (charwhat, where)
173 daughter.values[where] = charwhat
174 try:
175 solved = daughter.solve()
176 except CheckError as e:
177 # L'hypothèse était fausse
178 if VERBOSE:
179 print e.message
180 print "L'hypothèse était fausse"
181 self.possible[where][what] = False
182 return self.solve()
183 if solved:
184 self.values = daughter.values
185 return True
186 else:
187 raw_input("WTF")
188
189 def solve(self):
190 """Résoud la grille."""
191 solved = self.logic_solve()
192 if solved:
193 return True
194 else:
195 self.check()
196 return self.hypothetic_solve()
197
198
199
200
201
202 if __name__ == "__main__":
203 basic = sudoku_types.BasicSudoku()
204 samurai = sudoku_types.Samurai()
205 #values = [i for i in sudoku_types.examples.hard]
206 #values = [i for i in "0"*369]
207 #values = quick_input()
208 values = [i for i in sudoku_types.examples.samurai]
209 g = Grid(samurai, values)
210 print g
211 raw_input("\ngo ?")
212 g.solve()
213 print g