sudokuSolverPython.py 2.5 KB
Newer Older
1
2
#Recursive/backtracking algorithm to solve sudoku puzzle if possible.
#By Nathan Rossol, Computer Science sophomore at the University of Michigan
nrossol's avatar
nrossol committed
3
4
5

#TO RUN THIS PROGRAM: Instal pygame and use terminal to run gui.py. Make sure this file and gui.py 
#are in the same directory.
6
7
8
9
10

#Game rules: The grid has 81 squares: 9 boxes of 9 squares. Each box must contain
#all numbers 1-9 in its squares, and each number can appear only once in any row,
#column, or box.
def solveSudoku(grid):
nrossol's avatar
nrossol committed
11
    zeroIndex = [0,0]
12
    foundZero = findZero(grid, zeroIndex)
nrossol's avatar
nrossol committed
13
14
15
    #print(foundZero),
    #print(zeroIndex[0]),
    #print(zeroIndex[1])
16
17
18
    solved = False

    if foundZero:
nrossol's avatar
nrossol committed
19
        for i in range(1,10):
20
21
22
23
24
25
26
27
28
29
30
31
32
33
            grid[zeroIndex[0]][zeroIndex[1]] = i
            if(checkSolution(grid,zeroIndex[0],zeroIndex[1])):
                solved = solveSudoku(grid)
                if(solved): return True

        grid[zeroIndex[0]][zeroIndex[1]] = 0
        return False

    else:
        return True


def checkBox(grid, row, col):
    numbers = []
nrossol's avatar
nrossol committed
34
35
36
37
38
39
40
    for i in range(row,row+3):
        for j in range(col,col+3):
            if grid[i][j] not in numbers and grid[i][j] != 0: 
                numbers.insert(0, grid[i][j])
            elif grid[i][j] in numbers and grid[i][j] != 0: 
                #print("CheckBox FAILED")
                return False
41
42
43
44
45
46

    return True


def checkSolution(grid, row, col):
    #check cols and rows:
nrossol's avatar
nrossol committed
47
    for i in range(0,9):
48
        if grid[i][col] == grid[row][col] and i != row:
nrossol's avatar
nrossol committed
49
            #print("ROW ALREADY CONTAINS")
50
51
            return False
        elif grid[row][i] == grid[row][col] and i != col:
nrossol's avatar
nrossol committed
52
            #print("COL ALREADY CONTAINS")
53
54
            return False 
    #check boxes:
nrossol's avatar
nrossol committed
55
56
57
58
    for i in range(0,9,3):
        for j in range(0,9,3):
            #print(i),
            #print(j)
59
60
            if not checkBox(grid,i,j):
                return False
nrossol's avatar
nrossol committed
61
    #print("PASSED")
62
63
64
65
    return True


def findZero(grid, zeroIndex): 
nrossol's avatar
nrossol committed
66
67
    for r in range(len(grid)):
        for c in range(len(grid[r])):
68
69
70
            if grid[r][c] == 0:
                zeroIndex[0] = r
                zeroIndex[1] = c
nrossol's avatar
nrossol committed
71
                return True
72

nrossol's avatar
nrossol committed
73
    return False
74
75
76


def printBoard(grid):
nrossol's avatar
nrossol committed
77
78
79
80
81
    for i in range(0,9):
        for j in range(0,9):
            print(grid[i][j], end=' '),
        print("")    
        
82
83
84
85


def solve(grid):
    if solveSudoku(grid):
nrossol's avatar
nrossol committed
86
        print("Solveable :)!")
87
88
89
    else:
        print("Unsolvable :(")

90
91
    #printBoard(grid) 
    #return grid;
nrossol's avatar
nrossol committed
92