-
Notifications
You must be signed in to change notification settings - Fork 0
/
Main.py
103 lines (73 loc) · 2.18 KB
/
Main.py
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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
boards = [
[8, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 6, 0, 0, 0, 0, 0],
[0, 7, 0, 0, 9, 0, 2, 0, 0],
[0, 5, 0, 0, 0, 7, 0, 0, 0],
[0, 0, 0, 0, 4, 5, 7, 0, 0],
[0, 0, 0, 1, 0, 0, 0, 3, 0],
[0, 0, 1, 0, 0, 0, 0, 6, 8],
[0, 0, 8, 5, 0, 0, 0, 1, 0],
[0, 9, 0, 0, 0, 0, 4, 0, 0]
]
def printboard(board):
for i in range(9):
if i % 3 == 0 and i != 0:
print("------------------------------------")
for j in range(9):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(board[i][j])
else:
print(str(board[i][j]) + " ", end="")
def box_empty(board):
for i in range(9):
for j in range(9):
if board[i][j] == 0:
return (i, j)
return None
def valid_row(board, num, pos):
#ROW
for x in range(9):
if board[pos[0]][x] == num and pos[1] != x:
return False
return True
def valid_column(board, num, pos):
#COLUMN
for y in range(9):
if board[y][pos[1]] == num and pos[0] != y:
return False
return True
def valid_grid(board, num, pos):
#SUB GRID
box_x = pos[1]//3
box_y = pos[0]//3
for a in range(box_y*3, box_y*3 + 3):
for b in range(box_x*3, box_x*3 + 3):
if board[a][b] == num and (a, b) != pos:
return False
return True
count = 0
def solve(board):
global count
empty = box_empty(board)
if not empty:
return True
else:
row, column = empty
for x in range(1, 10):
if valid_row(board, x, (row, column)) and valid_column(board, x, (row, column)) and valid_grid(board, x, (row, column)):
board[row][column] = x
count = count + 1
if solve(board):
return True
board[row][column] = 0
return False
print("\n\nOriginal Sudoku: \n\n")
printboard(boards)
print("\n")
solve(boards)
print("\nSolved Sudoku: \n\n")
printboard(boards)
print("\n\nNumber of permutations: ", count)
print("\n\n")