--- /dev/null
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+"""Résolution de sudoku."""
+
+# Recodé le 12/03/13, parce que je retrouvais pas l'ancien
+# … et que j'en avais marre du projet why3
+
+import sudoku_types
+
+VERBOSE = False
+
+DEPTH = 0
+
+# Fonctions logiques
+def exists(l):
+ """Vérifie qu'au moins une valeur de l est vraie."""
+ return not all([not i for i in l])
+
+def one(l):
+ """Vérifie que l contient une et une seule valeur de vérité."""
+ return sum([bool(i) for i in l]) == 1
+
+def none(l):
+ """Vérifie que l ne contient aucune valeur de vérité."""
+ return all([not i for i in l])
+
+class CheckError(Exception):
+ """Levée si une grille est insoluble."""
+ def __init__(self, msg):
+ Exception.__init__(self, msg)
+
+def quick_input():
+ """Lit une chaîne et renvoie un les caractères un par un. Ne marche que pour le sudoku à caractère unique"""
+ chain = raw_input("Input (_=vide):")
+ # On remplace quand même les 0 par des _
+ chain = chain.replace("0", "_")
+ return [i for i in chain]
+
+class Grid(object):
+ """Grille de sudoku, contenant des valeurs."""
+
+ def check_depth(self):
+ """Affiche la valeur de la profondeur d'hypothèse si on n'a jamais atteint ce niveau"""
+ global DEPTH
+ if self.depth > DEPTH:
+ print "Profondeur : %s" % self.depth
+ DEPTH += 1
+
+ def __init__(self, typ, values, depth=0):
+ if len(values) != typ.size:
+ raise ValueError("%s valeurs incompatibles avec le type de sudoku (%s)" % (len(values), typ.size))
+ self.typ = typ
+ self.values = [i for i in values] # On fait une copie de la liste pour avoir un passage par valeurs
+ self.possible = [[True for i in range(len(typ.chars))] for j in range(len(values))]
+ self.depth = depth
+ self.check_depth()
+
+ def case_filled(self, i):
+ """Dit si la case ``i`` contient une valeur."""
+ return self.values[i] in self.typ.chars
+
+ def deduce(self):
+ """Rajoute des valeurs dans les cases en déduisant de ``self.possible``.
+ On renvoie ``True`` si on a fait quelque chose."""
+ something = False
+ # Si une case ne peut plus contenir qu'un seul symbole, on le met dedans
+ for case in range(self.typ.size):
+ if not self.case_filled(case) and one(self.possible[case]):
+ place = self.possible[case].index(True)
+ self.values[case] = self.typ.chars[place]
+ if VERBOSE:
+ print "%s placé en %s [case]" % (self.typ.chars[place], place)
+ something = True
+ # Si un linked_field contient déjà tous les symboles sauf un, on le place dans la case restante
+ for field in self.typ.linked_fields:
+ for nchar in range(len(self.typ.chars)):
+ l_field = [self.possible[i][nchar] for i in field]
+ if one(l_field):
+ place = field[l_field.index(True)]
+ if not self.case_filled(place):
+ self.values[place] = self.typ.chars[nchar]
+ if VERBOSE:
+ print "%s placé en %s [field %s]" % (self.typ.chars[nchar], place, field)
+ something = True
+ return something
+
+ def __str__(self):
+ """Affiche la grille."""
+ return self.typ.render(self.values)
+
+ def update_possible(self):
+ """Enlève des possibilités en déduisant de ``self.values``."""
+ for case in range(self.typ.size):
+ if self.case_filled(case): # la case contient quelque chose
+ numchar = self.typ.chars.index(self.values[case])
+ # Il n'y a plus rien de possible dans cette case
+ for p in range(len(self.typ.chars)):
+ self.possible[case][p] = False
+ # Il est impossible que la valeur soit dans tout linked_field de cette case
+ for f in self.typ.linked_fields:
+ if case in f:
+ for c in f:
+ self.possible[c][numchar] = False
+
+ def is_full(self):
+ """Dit si la grille est pleine."""
+ return all([self.case_filled(i) for i in range(self.typ.size)])
+
+ def logic_solve(self):
+ """Résoud la grille uniquement par déduction.
+ Renvoie ``True`` si elle est entièrement résolue.
+ """
+ action = True
+ while action:
+ self.update_possible()
+ action = self.deduce()
+ return self.is_full()
+
+ def _first_empty(self):
+ """Renvoie l'index de la première case vide."""
+ for i in range(self.typ.size):
+ if not self.case_filled(i):
+ return i
+
+ def hypothesis(self):
+ """Émet une hypothèse."""
+ if self.is_full():
+ raise RuntimeError("Pas besoin de faire une hypothèse, la grille est pleine !")
+ # On prend la première case vide
+ where = self._first_empty()
+ # On choisi le premier symbole possible
+ what = self.possible[where].index(True)
+ return where, what
+
+ def check(self):
+ """Vérifie qu'une grille est toujours cohérente."""
+ # Les cases dans lesquelles on ne peut plus rien mettre
+ empty_cases = [none(self.possible[c]) for c in range(self.typ.size)]
+ for c in range(self.typ.size):
+ if empty_cases[c] and not self.case_filled(c):
+ # La case ne peut rien contenir et ne contient rien
+ raise CheckError("La case %s ne peut rien contenir !" % (c))
+ # Les linked_field dans lesquels un symbole ne peut plus être placé
+ for nchar in range(len(self.typ.chars)):
+ empty_fields = [none([self.possible[c][nchar] for c in f]) for f in self.typ.linked_fields]
+ for nfield in range(len(self.typ.linked_fields)):
+ field = self.typ.linked_fields[nfield]
+ lll = [self.values[c] == self.typ.chars[nchar] for c in field]
+ if empty_fields[nfield] and not exists(lll):
+ # Le field ne peut pas contenir le caractère et ne le contient effectivement pas
+ raise CheckError("Le field %s ne peut pas contenir de %s !" % (field, self.typ.chars[nchar]))
+
+ def is_valid(self):
+ """Répond ``True`` si la grille est cohérente."""
+ try:
+ self.check()
+ return True
+ except CheckError:
+ return False
+
+ def hypothetic_solve(self):
+ """Résoud en faisant des hypothèses.
+ ``self.update_possible`` doit avoir été appliqué."""
+ where, what = self.hypothesis()
+ charwhat = self.typ.chars[what]
+ daughter = Grid(self.typ, self.values, self.depth+1)
+ # On applique l'hypothèse
+ if VERBOSE:
+ print "Hypothèse : %s en %s." % (charwhat, where)
+ daughter.values[where] = charwhat
+ try:
+ solved = daughter.solve()
+ except CheckError as e:
+ # L'hypothèse était fausse
+ if VERBOSE:
+ print e.message
+ print "L'hypothèse était fausse"
+ self.possible[where][what] = False
+ return self.solve()
+ if solved:
+ self.values = daughter.values
+ return True
+ else:
+ raw_input("WTF")
+
+ def solve(self):
+ """Résoud la grille."""
+ solved = self.logic_solve()
+ if solved:
+ return True
+ else:
+ self.check()
+ return self.hypothetic_solve()
+
+
+
+
+
+if __name__ == "__main__":
+ basic = sudoku_types.BasicSudoku()
+ samurai = sudoku_types.Samurai()
+ #values = [i for i in sudoku_types.examples.hard]
+ #values = [i for i in "0"*369]
+ #values = quick_input()
+ values = [i for i in sudoku_types.examples.samurai]
+ g = Grid(samurai, values)
+ print g
+ raw_input("\ngo ?")
+ g.solve()
+ print g
+
--- /dev/null
+#!/usr/bin/env python
+# -*- coding: utf-8 -*-
+
+"""Définition des linked_fields de différents types de sudoku"""
+
+rouge = "\e[0;31m"
+rien = "\e[0m"
+
+class SudokuType(object):
+ def render(self, values, adaptsize=True):
+ """Affiche le sudoku avec un contenu."""
+ if adaptsize:
+ maxsize = max([len(i) for i in values])
+ valuetemplate = "%%%ss" % maxsize
+ else:
+ valuetemplate = "%s"
+ map = {str(i) : valuetemplate % values[i] for i in range(self.size)}
+ map["empty"] = valuetemplate % " "
+ return self.template % map
+
+ def render_field(self, field):
+ """Met en évidence un linked_field en l'affichant en rouge"""
+ if type(field) == int:
+ field = self.linked_fields[field]
+ values = [rouge + "X" + rien if i in field else "_" for i in range(self.size)]
+ return self.render(values, False)
+
+class BasicSudoku(SudokuType):
+ size = 81
+ chars = [str(i) for i in range(1, 10)]
+
+ linked_fields = ( [[9*ligne + col for col in range(9)] for ligne in range(9)] # lignes
+ + [[9*ligne + col for ligne in range(9)] for col in range(9)] # colonnes
+ + [[27*bl + 3*bc + 9*l + c for l in range(3) for c in range(3)] for bl in range(3) for bc in range(3)] # blocs
+ )
+
+ template = "\n".join(["".join(["%%(%s)s" % (9*i + j) for j in range(9)]) for i in range(9)])
+
+ # random local garbage
+ del i, j, l, c, bl, bc, col, ligne
+
+class Samurai(SudokuType):
+ size = (4*9 + 5)*9
+ chars = [str(i) for i in range(1, 10)]
+
+ linked_fields = ( [[start + offset for offset in range(9)] for start in [0, 18, 36, 54, 72, 90, 108, 129, 150] + [9, 27, 45, 63, 81, 99, 120, 141, 162] + [114, 135, 156, 171, 180, 189, 204, 225, 246] + [198, 219, 240, 261, 279, 297, 315, 333, 351] + [210, 231, 252, 270, 288, 306, 324, 342, 360]]
+ # Après, j'ai eu la flemme de faire en finesse, j'ai bourrnié et j'hardcode
+ # Les colonnes
+ +[[0, 18, 36, 54, 72, 90, 108, 129, 150],
+ [1, 19, 37, 55, 73, 91, 109, 130, 151],
+ [2, 20, 38, 56, 74, 92, 110, 131, 152],
+ [3, 21, 39, 57, 75, 93, 111, 132, 153],
+ [4, 22, 40, 58, 76, 94, 112, 133, 154],
+ [5, 23, 41, 59, 77, 95, 113, 134, 155],
+ [6, 24, 42, 60, 78, 96, 114, 135, 156],
+ [7, 25, 43, 61, 79, 97, 115, 136, 157],
+ [8, 26, 44, 62, 80, 98, 116, 137, 158],
+ [9, 27, 45, 63, 81, 99, 120, 141, 162],
+ [10, 28, 46, 64, 82, 100, 121, 142, 163],
+ [11, 29, 47, 65, 83, 101, 122, 143, 164],
+ [12, 30, 48, 66, 84, 102, 123, 144, 165],
+ [13, 31, 49, 67, 85, 103, 124, 145, 166],
+ [14, 32, 50, 68, 86, 104, 125, 146, 167],
+ [15, 33, 51, 69, 87, 105, 126, 147, 168],
+ [16, 34, 52, 70, 88, 106, 127, 148, 169],
+ [17, 35, 53, 71, 89, 107, 128, 149, 170],
+ [114, 135, 156, 171, 180, 189, 204, 225, 246],
+ [115, 136, 157, 172, 181, 190, 205, 226, 247],
+ [116, 137, 158, 173, 182, 191, 206, 227, 248],
+ [117, 138, 159, 174, 183, 192, 207, 228, 249],
+ [118, 139, 160, 175, 184, 193, 208, 229, 250],
+ [119, 140, 161, 176, 185, 194, 209, 230, 251],
+ [120, 141, 162, 177, 186, 195, 210, 231, 252],
+ [121, 142, 163, 178, 187, 196, 211, 232, 253],
+ [122, 143, 164, 179, 188, 197, 212, 233, 254],
+ [198, 219, 240, 261, 279, 297, 315, 333, 351],
+ [199, 220, 241, 262, 280, 298, 316, 334, 352],
+ [200, 221, 242, 263, 281, 299, 317, 335, 353],
+ [201, 222, 243, 264, 282, 300, 318, 336, 354],
+ [202, 223, 244, 265, 283, 301, 319, 337, 355],
+ [203, 224, 245, 266, 284, 302, 320, 338, 356],
+ [204, 225, 246, 267, 285, 303, 321, 339, 357],
+ [205, 226, 247, 268, 286, 304, 322, 340, 358],
+ [206, 227, 248, 269, 287, 305, 323, 341, 359],
+ [210, 231, 252, 270, 288, 306, 324, 342, 360],
+ [211, 232, 253, 271, 289, 307, 325, 343, 361],
+ [212, 233, 254, 272, 290, 308, 326, 344, 362],
+ [213, 234, 255, 273, 291, 309, 327, 345, 363],
+ [214, 235, 256, 274, 292, 310, 328, 346, 364],
+ [215, 236, 257, 275, 293, 311, 329, 347, 365],
+ [216, 237, 258, 276, 294, 312, 330, 348, 366],
+ [217, 238, 259, 277, 295, 313, 331, 349, 367],
+ [218, 239, 260, 278, 296, 314, 332, 350, 368]]
+ # Les blocs
+ +[[0, 1, 2, 18, 19, 20, 36, 37, 38],
+ [3, 4, 5, 21, 22, 23, 39, 40, 41],
+ [6, 7, 8, 24, 25, 26, 42, 43, 44],
+ [9, 10, 11, 27, 28, 29, 45, 46, 47],
+ [12, 13, 14, 30, 31, 32, 48, 49, 50],
+ [15, 16, 17, 33, 34, 35, 51, 52, 53],
+ [54, 55, 56, 72, 73, 74, 90, 91, 92],
+ [57, 58, 59, 75, 76, 77, 93, 94, 95],
+ [60, 61, 62, 78, 79, 80, 96, 97, 98],
+ [63, 64, 65, 81, 82, 83, 99, 100, 101],
+ [66, 67, 68, 84, 85, 86, 102, 103, 104],
+ [69, 70, 71, 87, 88, 89, 105, 106, 107],
+ [108, 109, 110, 129, 130, 131, 150, 151, 152],
+ [111, 112, 113, 132, 133, 134, 153, 154, 155],
+ [114, 115, 116, 135, 136, 137, 156, 157, 158],
+ [117, 118, 119, 138, 139, 140, 159, 160, 161],
+ [120, 121, 122, 141, 142, 143, 162, 163, 164],
+ [123, 124, 125, 144, 145, 146, 165, 166, 167],
+ [126, 127, 128, 147, 148, 149, 168, 169, 170],
+ [171, 172, 173, 180, 181, 182, 189, 190, 191],
+ [174, 175, 176, 183, 184, 185, 192, 193, 194],
+ [177, 178, 179, 186, 187, 188, 195, 196, 197],
+ [198, 199, 200, 219, 220, 221, 240, 241, 242],
+ [201, 202, 203, 222, 223, 224, 243, 244, 245],
+ [204, 205, 206, 225, 226, 227, 246, 247, 248],
+ [207, 208, 209, 228, 229, 230, 249, 250, 251],
+ [210, 211, 212, 231, 232, 233, 252, 253, 254],
+ [213, 214, 215, 234, 235, 236, 255, 256, 257],
+ [216, 217, 218, 237, 238, 239, 258, 259, 260],
+ [261, 262, 263, 279, 280, 281, 297, 298, 299],
+ [264, 265, 266, 282, 283, 284, 300, 301, 302],
+ [267, 268, 269, 285, 286, 287, 303, 304, 305],
+ [270, 271, 272, 288, 289, 290, 306, 307, 308],
+ [273, 274, 275, 291, 292, 293, 309, 310, 311],
+ [276, 277, 278, 294, 295, 296, 312, 313, 314],
+ [315, 316, 317, 333, 334, 335, 351, 352, 353],
+ [318, 319, 320, 336, 337, 338, 354, 355, 356],
+ [321, 322, 323, 339, 340, 341, 357, 358, 359],
+ [324, 325, 326, 342, 343, 344, 360, 361, 362],
+ [327, 328, 329, 345, 346, 347, 363, 364, 365],
+ [330, 331, 332, 348, 349, 350, 366, 367, 368]])
+
+ template = "%(0)s%(1)s%(2)s%(3)s%(4)s%(5)s%(6)s%(7)s%(8)s%(empty)s%(empty)s%(empty)s%(9)s%(10)s%(11)s%(12)s%(13)s%(14)s%(15)s%(16)s%(17)s\n%(18)s%(19)s%(20)s%(21)s%(22)s%(23)s%(24)s%(25)s%(26)s%(empty)s%(empty)s%(empty)s%(27)s%(28)s%(29)s%(30)s%(31)s%(32)s%(33)s%(34)s%(35)s\n%(36)s%(37)s%(38)s%(39)s%(40)s%(41)s%(42)s%(43)s%(44)s%(empty)s%(empty)s%(empty)s%(45)s%(46)s%(47)s%(48)s%(49)s%(50)s%(51)s%(52)s%(53)s\n%(54)s%(55)s%(56)s%(57)s%(58)s%(59)s%(60)s%(61)s%(62)s%(empty)s%(empty)s%(empty)s%(63)s%(64)s%(65)s%(66)s%(67)s%(68)s%(69)s%(70)s%(71)s\n%(72)s%(73)s%(74)s%(75)s%(76)s%(77)s%(78)s%(79)s%(80)s%(empty)s%(empty)s%(empty)s%(81)s%(82)s%(83)s%(84)s%(85)s%(86)s%(87)s%(88)s%(89)s\n%(90)s%(91)s%(92)s%(93)s%(94)s%(95)s%(96)s%(97)s%(98)s%(empty)s%(empty)s%(empty)s%(99)s%(100)s%(101)s%(102)s%(103)s%(104)s%(105)s%(106)s%(107)s\n%(108)s%(109)s%(110)s%(111)s%(112)s%(113)s%(114)s%(115)s%(116)s%(117)s%(118)s%(119)s%(120)s%(121)s%(122)s%(123)s%(124)s%(125)s%(126)s%(127)s%(128)s\n%(129)s%(130)s%(131)s%(132)s%(133)s%(134)s%(135)s%(136)s%(137)s%(138)s%(139)s%(140)s%(141)s%(142)s%(143)s%(144)s%(145)s%(146)s%(147)s%(148)s%(149)s\n%(150)s%(151)s%(152)s%(153)s%(154)s%(155)s%(156)s%(157)s%(158)s%(159)s%(160)s%(161)s%(162)s%(163)s%(164)s%(165)s%(166)s%(167)s%(168)s%(169)s%(170)s\n%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(171)s%(172)s%(173)s%(174)s%(175)s%(176)s%(177)s%(178)s%(179)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s\n%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(180)s%(181)s%(182)s%(183)s%(184)s%(185)s%(186)s%(187)s%(188)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s\n%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(189)s%(190)s%(191)s%(192)s%(193)s%(194)s%(195)s%(196)s%(197)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s%(empty)s\n%(198)s%(199)s%(200)s%(201)s%(202)s%(203)s%(204)s%(205)s%(206)s%(207)s%(208)s%(209)s%(210)s%(211)s%(212)s%(213)s%(214)s%(215)s%(216)s%(217)s%(218)s\n%(219)s%(220)s%(221)s%(222)s%(223)s%(224)s%(225)s%(226)s%(227)s%(228)s%(229)s%(230)s%(231)s%(232)s%(233)s%(234)s%(235)s%(236)s%(237)s%(238)s%(239)s\n%(240)s%(241)s%(242)s%(243)s%(244)s%(245)s%(246)s%(247)s%(248)s%(249)s%(250)s%(251)s%(252)s%(253)s%(254)s%(255)s%(256)s%(257)s%(258)s%(259)s%(260)s\n%(261)s%(262)s%(263)s%(264)s%(265)s%(266)s%(267)s%(268)s%(269)s%(empty)s%(empty)s%(empty)s%(270)s%(271)s%(272)s%(273)s%(274)s%(275)s%(276)s%(277)s%(278)s\n%(279)s%(280)s%(281)s%(282)s%(283)s%(284)s%(285)s%(286)s%(287)s%(empty)s%(empty)s%(empty)s%(288)s%(289)s%(290)s%(291)s%(292)s%(293)s%(294)s%(295)s%(296)s\n%(297)s%(298)s%(299)s%(300)s%(301)s%(302)s%(303)s%(304)s%(305)s%(empty)s%(empty)s%(empty)s%(306)s%(307)s%(308)s%(309)s%(310)s%(311)s%(312)s%(313)s%(314)s\n%(315)s%(316)s%(317)s%(318)s%(319)s%(320)s%(321)s%(322)s%(323)s%(empty)s%(empty)s%(empty)s%(324)s%(325)s%(326)s%(327)s%(328)s%(329)s%(330)s%(331)s%(332)s\n%(333)s%(334)s%(335)s%(336)s%(337)s%(338)s%(339)s%(340)s%(341)s%(empty)s%(empty)s%(empty)s%(342)s%(343)s%(344)s%(345)s%(346)s%(347)s%(348)s%(349)s%(350)s\n%(351)s%(352)s%(353)s%(354)s%(355)s%(356)s%(357)s%(358)s%(359)s%(empty)s%(empty)s%(empty)s%(360)s%(361)s%(362)s%(363)s%(364)s%(365)s%(366)s%(367)s%(368)s"
+
+class examples:
+ fail = "011111111000000000000000000000000000000000000000000000000000000000000000000000000"
+ hard = "200000060000075030048090100000300000300010009000008000001020570080730000090000004"
+ easy = "487000503056000000031500090000840051070605030310072000060009310000000970703000825"
+ samurai = "000385000000000100039000800960000040400000020003000060000000006000400005000076900000080004000100074290030007004000300010005020080080009000008000700900060007000004000306000064000000200040006000000170000609000900000400070007002000200000200090090030500060003000100500090042610009000900080000002530000300001000500000000040000800090000002010000095005000640002000000000685000"
\ No newline at end of file
projects / sudoku.git / commitdiff