sudoku solver

Go Back home

Excellent sudoku solver (credit); uses dfs.

 1 from time import time
 2 
 3 from collections import defaultdict as ddict
 4 from collections import deque
 5 from itertools import product
 6 
 7 def solveSudoku(self, board):
 8     rows, cols, triples, visit = ddict(set), ddict(set), ddict(set), deque([])
 9     for r, c in product(range(9), repeat=2):
10         if board[r][c] != ".":
11             rows[r].add(board[r][c])
12             cols[c].add(board[r][c])
13             triples[(r // 3, c // 3)].add(board[r][c])
14         else:
15             visit.append((r, c))
16     def dfs():
17         if not visit:
18             return True
19         r, c = visit[0]
20         t = (r // 3, c // 3)
21         for dig in ["1", "2", "3", "4", "5", "6", "7", "8", "9"]:
22             if dig not in rows[r] and dig not in cols[c] and dig not in triples[t]:
23                 board[r][c] = dig
24                 rows[r].add(dig)
25                 cols[c].add(dig)
26                 triples[t].add(dig)
27                 visit.popleft()
28                 if dfs():
29                     return True
30                 else:
31                     board[r][c] = "."
32                     rows[r].discard(dig)
33                     cols[c].discard(dig)
34                     triples[t].discard(dig)
35                     visit.appendleft((r, c))
36         return False
37     dfs()
38 
39 def print_sudoku(A):
40     for r in A:
41         print(r)
42     print('')
43 
44 A = [[".",".","3","8",".",".","4",".","."],
45     [".",".",".",".","1",".",".","7","."],
46     [".","6",".",".",".","5",".",".","9"],
47     [".",".",".","9",".",".","6",".","."],
48     [".","2",".",".",".",".",".","1","."],
49     [".",".","4",".",".","3",".",".","2"],
50     [".",".","2",".",".",".","8",".","."],
51     [".","1",".",".",".",".",".","5","."],
52     ["9",".",".",".",".","7",".",".","3"]]
53 
54 s = time()
55 print(solveSudoku(A))
56 print_sudoku(A)
57 print(time() - s)