From: Vincent Le Gallic Date: Sun, 29 Sep 2013 18:41:12 +0000 (+0200) Subject: Solveur de sudokus. Sous plusieurs formes. X-Git-Url: http://gitweb.pimeys.fr/?p=sudoku.git;a=commitdiff_plain;h=bf9d28609ea65fd320add7e2af4ff941dd5781e7 Solveur de sudokus. Sous plusieurs formes. --- bf9d28609ea65fd320add7e2af4ff941dd5781e7 diff --git a/sudoku.py b/sudoku.py new file mode 100755 index 0000000..c893bce --- /dev/null +++ b/sudoku.py @@ -0,0 +1,212 @@ +#!/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 + diff --git a/sudoku_types.py b/sudoku_types.py new file mode 100644 index 0000000..e70a0fd --- /dev/null +++ b/sudoku_types.py @@ -0,0 +1,143 @@ +#!/usr/bin/env python +# -*- coding: utf-8 -*- + +"""Définition des linked_fields de différents types de sudoku""" + +rouge = "" +rien = "" + +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