Simply Solving Sudoku

It's been a long time since I last blogged. I've been meaning to for oh so long but you know what they say about the road to hell. For a while I maintained my math blog but even that has been fallow for some time.

Fortunately, I stumbled upon Peter Norvig's article about solving Sudoku, and that has provided the impetus. His approach is probably the most sensible I have seen for a while; there seem to be some really bad solvers out there. I was unimpressed with the one by Skiena in the Algorithm Design Manual, although the truly ridiculous one has to be the so-overblown-I-took-a-whole-book approach in Programming Sudoku; the mind simply boggles at how complex some people make trivial things.

Because solving Sudoku is indeed trivial. There is nothing to it. All you need is a very simple backtracking search. I wrote the solver below originally more than 10 years ago in Javascript and it was used as a generator running on extremely low-powered Microsoft SPOT smart watches. For fun I dug it out, turned it into Python, and tested it on "the world's hardest Sudoku puzzle". How fast can you blink?

But still some people make a big deal out of it all...

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
rows = [0xffff] * 9
cols = [0xffff] * 9
rgns = [0xffff] * 9
board = [0]*81

def init(puz):
    global board, rows, cols, rgns, board
    for r, row in enumerate(puz):
        for c, ch in enumerate(row):
            board[r * 9 + c] = ch
            if ch == '.':
                continue
            m = ~(1 << (ord(ch) - 48))
            rows[r] &= m
            cols[c] &= m
            rgns[(r // 3) * 3 + (c // 3)] &= m

def fill(pos):
    global board, rows, cols, rgns
    if pos == 81:
        return True
    elif board[pos] != '.':
        return fill(pos + 1)
    r = pos // 9
    c = pos % 9
    allowed = rows[r] & cols[c]
    if allowed:
        rg = (r // 3) * 3 + (c // 3)
        allowed &= rgns[rg]
        if allowed:
            for i in range(1, 10):
                tm = 1 << i
                if allowed & tm:
                    im = ~tm
                    rows[r] &= im
                    cols[c] &= im
                    rgns[rg] &= im
                    if fill(pos + 1):
                        board[pos] = chr(48 + i)
                        return True
                    rows[r] |= tm
                    cols[c] |= tm
                    rgns[rg] |= tm
    return False

def solve(puz):
    init(puz)
    return fill(0)

if solve([
"1....7.9.",
".3..2...8",
"..96..5..",
"..53..9..",
".1..8...2",
"6....4...",
"3......1.",
".4......7",
"..7...3.."
]):
    for i in xrange(0, 81, 9):
        print ''.join(board[i:i+9])

Written with StackEdit.

Comments

Comments powered by Disqus