]>
gitweb.pimeys.fr Git - sudoku.git/blob - sudoku.py
c893bce8699fcb06c222de4920950b2f33e2f19c
2 # -*- coding: utf-8 -*-
4 """Résolution de sudoku."""
6 # Recodé le 12/03/13, parce que je retrouvais pas l'ancien
7 # … et que j'en avais marre du projet why3
17 """Vérifie qu'au moins une valeur de l est vraie."""
18 return not all([not i
for i
in 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
25 """Vérifie que l ne contient aucune valeur de vérité."""
26 return all([not i
for i
in l
])
28 class CheckError(Exception):
29 """Levée si une grille est insoluble."""
30 def __init__(self
, msg
):
31 Exception.__init
__(self
, msg
)
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
]
41 """Grille de sudoku, contenant des valeurs."""
43 def check_depth(self
):
44 """Affiche la valeur de la profondeur d'hypothèse si on n'a jamais atteint ce niveau"""
46 if self
.depth
> DEPTH
:
47 print "Profondeur : %s" % self
.depth
50 def __init__(self
, typ
, values
, depth
=0):
51 if len(values
) != typ
.size
:
52 raise ValueError("%s valeurs incompatibles avec le type de sudoku (%s)" % (len(values
), typ
.size
))
54 self
.values
= [i
for i
in values
] # On fait une copie de la liste pour avoir un passage par valeurs
55 self
.possible
= [[True for i
in range(len(typ
.chars
))] for j
in range(len(values
))]
59 def case_filled(self
, i
):
60 """Dit si la case ``i`` contient une valeur."""
61 return self
.values
[i
] in self
.typ
.chars
64 """Rajoute des valeurs dans les cases en déduisant de ``self.possible``.
65 On renvoie ``True`` si on a fait quelque chose."""
67 # Si une case ne peut plus contenir qu'un seul symbole, on le met dedans
68 for case
in range(self
.typ
.size
):
69 if not self
.case_filled(case
) and one(self
.possible
[case
]):
70 place
= self
.possible
[case
].index(True)
71 self
.values
[case
] = self
.typ
.chars
[place
]
73 print "%s placé en %s [case]" % (self
.typ
.chars
[place
], place
)
75 # Si un linked_field contient déjà tous les symboles sauf un, on le place dans la case restante
76 for field
in self
.typ
.linked_fields
:
77 for nchar
in range(len(self
.typ
.chars
)):
78 l_field
= [self
.possible
[i
][nchar
] for i
in field
]
80 place
= field
[l_field
.index(True)]
81 if not self
.case_filled(place
):
82 self
.values
[place
] = self
.typ
.chars
[nchar
]
84 print "%s placé en %s [field %s]" % (self
.typ
.chars
[nchar
], place
, field
)
89 """Affiche la grille."""
90 return self
.typ
.render(self
.values
)
92 def update_possible(self
):
93 """Enlève des possibilités en déduisant de ``self.values``."""
94 for case
in range(self
.typ
.size
):
95 if self
.case_filled(case
): # la case contient quelque chose
96 numchar
= self
.typ
.chars
.index(self
.values
[case
])
97 # Il n'y a plus rien de possible dans cette case
98 for p
in range(len(self
.typ
.chars
)):
99 self
.possible
[case
][p
] = False
100 # Il est impossible que la valeur soit dans tout linked_field de cette case
101 for f
in self
.typ
.linked_fields
:
104 self
.possible
[c
][numchar
] = False
107 """Dit si la grille est pleine."""
108 return all([self
.case_filled(i
) for i
in range(self
.typ
.size
)])
110 def logic_solve(self
):
111 """Résoud la grille uniquement par déduction.
112 Renvoie ``True`` si elle est entièrement résolue.
116 self
.update_possible()
117 action
= self
.deduce()
118 return self
.is_full()
120 def _first_empty(self
):
121 """Renvoie l'index de la première case vide."""
122 for i
in range(self
.typ
.size
):
123 if not self
.case_filled(i
):
126 def hypothesis(self
):
127 """Émet une hypothèse."""
129 raise RuntimeError("Pas besoin de faire une hypothèse, la grille est pleine !")
130 # On prend la première case vide
131 where
= self
._first
_empty
()
132 # On choisi le premier symbole possible
133 what
= self
.possible
[where
].index(True)
137 """Vérifie qu'une grille est toujours cohérente."""
138 # Les cases dans lesquelles on ne peut plus rien mettre
139 empty_cases
= [none(self
.possible
[c
]) for c
in range(self
.typ
.size
)]
140 for c
in range(self
.typ
.size
):
141 if empty_cases
[c
] and not self
.case_filled(c
):
142 # La case ne peut rien contenir et ne contient rien
143 raise CheckError("La case %s ne peut rien contenir !" % (c
))
144 # Les linked_field dans lesquels un symbole ne peut plus être placé
145 for nchar
in range(len(self
.typ
.chars
)):
146 empty_fields
= [none([self
.possible
[c
][nchar
] for c
in f
]) for f
in self
.typ
.linked_fields
]
147 for nfield
in range(len(self
.typ
.linked_fields
)):
148 field
= self
.typ
.linked_fields
[nfield
]
149 lll
= [self
.values
[c
] == self
.typ
.chars
[nchar
] for c
in field
]
150 if empty_fields
[nfield
] and not exists(lll
):
151 # Le field ne peut pas contenir le caractère et ne le contient effectivement pas
152 raise CheckError("Le field %s ne peut pas contenir de %s !" % (field
, self
.typ
.chars
[nchar
]))
155 """Répond ``True`` si la grille est cohérente."""
162 def hypothetic_solve(self
):
163 """Résoud en faisant des hypothèses.
164 ``self.update_possible`` doit avoir été appliqué."""
165 where
, what
= self
.hypothesis()
166 charwhat
= self
.typ
.chars
[what
]
167 daughter
= Grid(self
.typ
, self
.values
, self
.depth
+1)
168 # On applique l'hypothèse
170 print "Hypothèse : %s en %s." % (charwhat
, where
)
171 daughter
.values
[where
] = charwhat
173 solved
= daughter
.solve()
174 except CheckError
as e
:
175 # L'hypothèse était fausse
178 print "L'hypothèse était fausse"
179 self
.possible
[where
][what
] = False
182 self
.values
= daughter
.values
188 """Résoud la grille."""
189 solved
= self
.logic_solve()
194 return self
.hypothetic_solve()
200 if __name__
== "__main__":
201 basic
= sudoku_types
.BasicSudoku()
202 samurai
= sudoku_types
.Samurai()
203 #values = [i for i in sudoku_types.examples.hard]
204 #values = [i for i in "0"*369]
205 #values = quick_input()
206 values
= [i
for i
in sudoku_types
.examples
.samurai
]
207 g
= Grid(samurai
, values
)