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