1
def load_puzzle(path):
2
    with open(path) as fin:
3
        contents = fin.read()
4
        lines = contents.split('\n')
5
        sudoku = []
6
    
7
    for row in lines:
8
        row_string = row.split()
9
        row_int = [int(n) for n in row_string]
10
        sudoku.append(row_int)
11
    print("Sudoku loaded from", path,"\n")
12
    return sudoku
13

14
def display_puzzle(puzzle):
15
    for i in range(len(puzzle)):
16
        if i % 3 == 0:
17
            print("+" + "-------+"*3)
18

19
        for j in range(len(puzzle[0])):
20
            char = puzzle[i][j]
21
            if char == 0:
22
                char = "."
23

24
            if j % 3 == 0:
25
                print("| ", end="")
26

27
            if j == 8:
28
                print(char, "|")
29
            else:
30
                print(str(char) + " ", end = "")
31
    print("+" + "-------+"*3)
32

33

34
def get_next(row, col):
35
    if col < 8:
36
        return row,col+1
37
    elif col == 8 and row < 8:
38
        return row+1,0
39
    elif col == 8 and row == 8:
40
        return None,None
41

42

43
def get_options(puzzle, row, col):
44
    if puzzle[row][col] > 0:
45
        return None
46

47
    used = []
48

49
    for i in range(0,9):
50
        if puzzle[row][i] > 0:
51
            used.append(puzzle[row][i])
52

53
    for i in range(0,9):
54
        if puzzle[i][col] > 0:
55
            used.append(puzzle[i][col])
56

57
    box_x = row // 3
58
    box_y = col // 3
59

60
    for i in range(box_x * 3, box_x * 3 + 3):
61
        for j in range(box_y * 3, box_y * 3 + 3):
62
            if puzzle[i][j] > 0:
63
                used.append(puzzle[i][j])
64
    options = []
65
    for i in range(1,10):
66
        if i not in used:
67
            options.append(i)
68
    return options
69

70

71
def copy_puzzle(puzzle):
72
    new_puzzles = []
73
    for i in range(0,len(puzzle)):
74
        new_copy = puzzle[i].copy()
75
        new_puzzles.append(new_copy)
76
    return new_puzzles
77

78

79
def solve(puzzle, row = 0, col = 0):
80
    if puzzle[row][col] != 0:
81
        next_row, next_col = get_next(row,col)
82
        if next_row is None:
83
            return puzzle
84
        else:
85
            return solve(puzzle, next_row, next_col)
86

87
    options = get_options(puzzle, row, col)
88

89
    if options == []:
90
        return None
91

92
    for cur_opt in options:
93
        new_puzzle = copy_puzzle(puzzle)
94
        new_puzzle[row][col] = cur_opt
95
        result = solve(new_puzzle, row, col)
96

97
        if result is not None:
98
            return result
99
    return None
100