Data-Structures-and-Algorithms/Python/sudoku.py at 10cb42645680bac91567ff5e43dddeaed4cda623 · hackprot2/Data-Structures-and-Algorithms · GitHub

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
board = [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]

def print_board(bo):
    for i in range(len(bo)):
        if(i%3==0 and i):
            print("- - - - - - - - - - - - - -")
        for j in range(len(bo[0])):
            if(j%3==0):
                print( " | " , end = " ")
            if(j==8):
                print(str(bo[i][j]) + "|" )
            else:
                print(str(bo[i][j]) + " " , end = "")
    print()

def find_empty(bo):
    for i in range(len(bo)):
        for j in range(len(bo[0])):
            if bo[i][j] == 0:
                return (i, j)  # row, col

    return 0;

def valid(bo, num, pos):
    for i in range(len(bo[0])):
        if(bo[pos[0]][i]==num and i!=pos[1]):
            return 0
    for i in range(len(bo)):
        if(bo[i][pos[1]]==num and i!=pos[0]):
            return 0
    box_x = pos[0] // 3
    box_y = pos[1] // 3

    for i in range(box_x*3, box_x*3 + 3):
        for j in range(box_y*3, box_y*3 + 3):
            if(bo[i][j] == num and (i,j) != pos):
                return 0;
    return 1;

# Main Function

def solve(bo):
    pos = find_empty(bo)
    if not pos:
        return 1;
    else:
        row,col = pos

    for i in range(1,10):
        if(valid(bo,i,(row,col))):
            bo[row][col] = i;

            if solve(bo):
                return 1;

            bo[row][col] = 0;

    return 0;

print_board(board)

solve(board)

print("Solved",'\n')

print_board(board)