-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoko solver.py
103 lines (93 loc) · 2.85 KB
/
sudoko solver.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
board=[[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]]
#------------------------------------------------------------------------
#print pretty
#------------------------------------------------------------------------
def print_board(board):
if board is None:
print("Empty Board")
col = len(board[0])
row = len(board)
print(" SODUKO ")
for i in range(row):
line_to_print=""
if i%3 == 0:
print("-------------------------")
for j in range(col):
if board[i][j] == 0:
board[i][j] = ' '
if j%3 ==0:
line_to_print +="| " + str(board[i][j]) + " "
else:
line_to_print += str(board[i][j]) + " "
print(line_to_print + "|")
print("-------------------------")
#------------------------------------------------------------------------
## Print the Soduko board
#------------------------------------------------------------------------
def printboard(board):
if board is None:
print("Empty Board")
col = len(board[0])
row = len(board)
for i in range(row):
line_to_print=""
for j in range(col):
line_to_print += str(board[i][j]) + ", "
print(line_to_print)
#------------------------------------------------------------------------
## Find the indexes of the empty cells (Empty cells contain 0)
#------------------------------------------------------------------------
def findzero(board):
zero_ans = []
for i in board:
if 0 in i:
zero_ans.append(board.index(i))
zero_ans.append(i.index(0))
return zero_ans
else:
None
#------------------------------------------------------------------------
# Check if a value is valid in the empty cell according to soduko rules
#------------------------------------------------------------------------
def isvalid(board, row, col, value):
#Check row
if value in board[row]:
return False
#Check column
for i in board:
if i[col] == value:
return False
#Divide the soduko board to 3X3 boards
x=(row//3)*3
y=(col//3)*3
for j in range(0,3):
for k in range(0,3):
if board[x+j][y+k]==value:
return False
return True
#------------------------------------------------------------------------
#Solve the soduko board using recursion
#------------------------------------------------------------------------
def solve(board):
zPlacement = findzero(board)
#Base Case
if zPlacement == None:
return print_board(board)
x = zPlacement[0]
y = zPlacement[1]
#recursive case
for i in range(1, 10):
if isvalid(board, x, y, i):
board[x][y] = i
solve(board)
board[x][y] = 0
return None
solve(board)