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             print "Profondeur : %s" % self.depth
  48             DEPTH += 1
  49
  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))
  53         self.typ = typ
  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))]
  56         self.depth = depth
  57         self.check_depth()
  58
  59     def case_filled(self, i):
  60         """Dit si la case ``i`` contient une valeur."""
  61         return self.values[i] in self.typ.chars
  62
  63     def deduce(self):
  64         """Rajoute des valeurs dans les cases en déduisant de ``self.possible``.
  65            On renvoie ``True`` si on a fait quelque chose."""
  66         something = False
  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]
  72                 if VERBOSE:
  73                     print "%s placé en %s [case]" % (self.typ.chars[place], place)
  74                 something = True
  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]
  79                 if one(l_field):
  80                     place = field[l_field.index(True)]
  81                     if not self.case_filled(place):
  82                         self.values[place] = self.typ.chars[nchar]
  83                         if VERBOSE:
  84                             print "%s placé en %s [field %s]" % (self.typ.chars[nchar], place, field)
  85                         something = True
  86         return something
  87
  88     def __str__(self):
  89         """Affiche la grille."""
  90         return self.typ.render(self.values)
  91
  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:
 102                     if case in f:
 103                         for c in f:
 104                             self.possible[c][numchar] = False
 105
 106     def is_full(self):
 107         """Dit si la grille est pleine."""
 108         return all([self.case_filled(i) for i in range(self.typ.size)])
 109
 110     def logic_solve(self):
 111         """Résoud la grille uniquement par déduction.
 112            Renvoie ``True`` si elle est entièrement résolue.
 113            """
 114         action = True
 115         while action:
 116             self.update_possible()
 117             action = self.deduce()
 118         return self.is_full()
 119
 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):
 124                 return i
 125
 126     def hypothesis(self):
 127         """Émet une hypothèse."""
 128         if self.is_full():
 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)
 134         return where, what
 135
 136     def check(self):
 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]))
 153
 154     def is_valid(self):
 155         """Répond ``True`` si la grille est cohérente."""
 156         try:
 157             self.check()
 158             return True
 159         except CheckError:
 160             return False
 161
 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
 169         if VERBOSE:
 170             print "Hypothèse : %s en %s." % (charwhat, where)
 171         daughter.values[where] = charwhat
 172         try:
 173             solved = daughter.solve()
 174         except CheckError as e:
 175             # L'hypothèse était fausse
 176             if VERBOSE:
 177                 print e.message
 178                 print "L'hypothèse était fausse"
 179             self.possible[where][what] = False
 180             return self.solve()
 181         if solved:
 182             self.values = daughter.values
 183             return True
 184         else:
 185             raw_input("WTF")
 186
 187     def solve(self):
 188         """Résoud la grille."""
 189         solved = self.logic_solve()
 190         if solved:
 191             return True
 192         else:
 193             self.check()
 194             return self.hypothetic_solve()
 195
 196
 197
 198
 199
 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)
 208     print g
 209     raw_input("\ngo ?")
 210     g.solve()
 211     print g
 212