söndag 18 december 2011

Python sudoku

# Lars.Rasmusson@gmail.com 2011-12-18
class sudoku(dict):
    def __init__(self,game):
        game = [g for g in game if g in ".123456789"]
        for r in range(1,10):
            for c in range(1,10):
                self[(r,c)] = set(range(1,10)) if game[0] == '.' \
                              else set([int(game[0])])
                game = game[1:]
    def row(self, r): return [(r,c) for c in range(1,10)]
    def col(self, c): return [(r,c) for r in range(1,10)]
    def field(self, f):
        fs = []
        for x in range(1,10):
            r = (x - 1) // 3 + 3 * ((f - 1) // 3) + 1
            c = (x - 1) % 3 + 3 * ((f - 1) % 3) + 1
            fs.append((r,c))
        return fs
    def different(self, vars, n):
        from itertools import combinations
        modified = False
        for vs in combinations(vars, n):
            u = set().union(*[self[x] for x in vs])
            o = set().union(*[self[x] for x in vars if not x in vs])
            if len(u) == n and o.intersection(u) != set():
                for v in set(vars)-set(vs):
                    if self[v].intersection(u):
                        self[v] -= u
                modified = True
        return modified
    def solve(self):
        n = 1
        while n < 9:
            mod = False
            for i in range(1,10):
                mod |= self.different(self.row(i),n)
                mod |= self.different(self.col(i),n)
                mod |= self.different(self.field(i),n)
            n = 1 if mod else n + 1
    def write(self):
        for r in range(1,10):
            for c in range(1,10):
                v = self[(r,c)]
                print '.' if len(v) > 1 else list(v)[0],
            print
    def backtrack(self):
        from copy import deepcopy
        self.solve()
        choices = [len(self[var]) for var in self]
        if min(choices) < 1: return None
        if max(choices) == 1: return self
        var = [var for var in self if len(self[var]) > 1][0]
        for val in self[var]:
            s = deepcopy(self)
            s[var] = set([val])
            s = s.backtrack()
            if s != None: return s
        return None
    def check(self):
        for i in range(1,10):
            s1 = set().union(*[self[v] for v in self.row(i)])
            s2 = set().union(*[self[v] for v in self.col(i)])
            s3 = set().union(*[self[v] for v in self.field(i)])
            if not s1 == s2 == s3 == set(range(1,10)):
                return False
        return True

games = ["""
798 ... 2..
... 69. .73
.6. 27. 1..

6.. 94. .81
4.5 .61 .2.
9.2 8.. .3.

2.7 ... 4..
1.. 4.3 76.
..6 .19 .5.
"""
,
"""
... .4. ...
..5 ... .46
..7 ... ..5
.5. 3.. 2..
23. ... 97.
7.. 8.. ...
.9. .8. 3..
... .24 ...
12. .3. .8.
"""
,

"""
5.. 17. .39
..7 9.. ...
.1. ... 4..

... 8.2 7..
3.8 ... 6.2
..5 4.6 ...

..2 ... .5.
... ..5 9..
15. .29 ..7
"""
,
"""
.2. ..6 ..3
.7. 95. ...
..8 ... ...

..5 ... ...
... 248 .1.
.6. ..3 ..2

39. ... ...
... 1.. 79.
... ... 1..

"""
,
"""
... 76. .5.
..2 ... .9.
... .5. 7..

..4 ..1 ...
.3. ..8 57.
... 2.. 6..

42. .3. ...
7.. 8.. ...
... ... ..1

"""
,
"""
.6. .4. ...
8.. ... ..9
..7 ... 15.

... ..8 ...
..3 .9. 7.4
... ... .6.

.1. 6.. ..3
9.. 1.. 8..
62. ..5 ...
"""
,
"""
5.1 ..8 ...
... .4. .3.
... ... 15.

.6. 49. ...
... 6.. 9.7
..3 1.. ...

... ... .42
.4. 8.7 ...
.27 ... .6.
"""

,
"""

. . 2 | 4 . . | . 8 9
. 4 . | . . 8 | 2 7 .
. . . | . . 6 | . . 4
------|-------|------
. 7 . | 9 . . | . . .
. . . | . . . | . . .
3 . 8 | 5 . . | . . .
------|-------|------
. 9 7 | 3 . 1 | . 6 5
. 8 . | 7 2 . | . . .
4 . . | . . . | . . 8
""",

"""
. 4 3 | 9 8 . | 2 5 . 
6 . . | 4 2 5 | . . . 
2 . . | . . 1 | . 9 4 
------|--------|------ 
9 . . | . . 4 | . 7 . 
3 . . | 6 . 8 | . . . 
4 1 . | 2 . 9 | . . 3 
------|--------|------ 
8 2 . | 5 . . | . . . 
. . . | . 4 . | . . 5 
5 3 4 | 8 9 . | 7 1 . 
"""
,
"""
1..4....8
...89.5..
.2...5...
..8....37
.9..5..2.
36....1..
...1...7.
..6.48...
9....3..4
"""
,
"""
.6. .4. ...
8.. ... ..9
..7 ... 15.

... ..8 ...
..3 .9. 7.4
... ... .6.

.1. 6.. ..3
9.. 1.. 8..
62. ..5 ...
"""
]

if __name__ == "__main__":
    for game in games:
        s = sudoku(game)
        s.write()
        # s.solve()
        s = s.backtrack()
        if s:
            if s.check():
                s.write()
            else:
                print "FAILED CHECK!"
        else:
            print None
        print

Inga kommentarer:

Skicka en kommentar