-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku_solver.py
204 lines (133 loc) · 6.01 KB
/
sudoku_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
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
#Code is written by ÖZER TANRISEVER
#Credit : https://www.linkedin.com/in/ozer-tanrisever/
# The boards taken from https://dingo.sbs.arizona.edu/~sandiway/sudoku/examples.html
#For GUI representation import sudoku_solver_gui and make adjustments accordingly.
import color_lib as cl
import time
#import sudoku_solver_gui as gui
#Easy
board = [[0,0,0,2,6,0,7,0,1],
[6,8,0,0,7,0,0,9,0],
[1,9,0,0,0,4,5,0,0],
[8,2,0,1,0,0,0,4,0],
[0,0,4,6,0,2,9,0,0],
[0,5,0,0,0,3,0,2,8],
[0,0,9,3,0,0,0,7,4],
[0,4,0,0,5,0,0,3,6],
[7,0,3,0,1,8,0,0,0]]
#Darn hard! Very very hard!
board2 = [[0,2,0,0,0,0,0,0,0],
[0,0,0,6,0,0,0,0,3],
[0,7,4,0,8,0,0,0,0],
[0,0,0,0,0,3,0,0,2],
[0,8,0,0,4,0,0,1,0],
[6,0,0,5,0,0,0,0,0],
[0,0,0,0,1,0,7,8,0],
[5,0,0,0,0,9,0,0,0],
[0,0,0,0,0,0,0,4,0]]
steps_taken = [] # This holds the taken steps in the game!
def print_board():
global board
print()
for i in range(len(board)):
if (i % 3 == 0):
print('-------------------------')
for j in range(len(board[0])):
if(j % 3 == 0):
print('| ' , end = '')
print(str(board[i][j]) + ' ' , end = '')
if(j == len(board)-1):
print('|')
if(i == len(board)-1):
print('-------------------------')
print()
def find_empty_square_index():
'''This returns an empty item index on board (If it exists).'''
global board
for i in range(len(board)):
for j in range (len(board[0])):
if(board[i][j] == 0):
return i,j #row,column
return None
def find_threeXthreeSquareElements(row,column):
''''This returns a list of appropriate 3x3 square elements relative to it's row and columns (except itself)'''
global board
tts =[]
if( (0 <= row <=2 ) and (0 <= column <= 2) ):
low_border_row, high_border_row, low_border_column, high_border_column = 0,2,0,2
elif( (0 <= row <=2 ) and (3 <= column <= 5) ):
low_border_row, high_border_row, low_border_column, high_border_column = 0,2,3,5
elif( (0 <= row <=2 ) and (6 <= column <= 8) ):
low_border_row, high_border_row, low_border_column, high_border_column = 0,2,6,8
elif( (3 <= row <=5 ) and (0 <= column <= 2) ):
low_border_row, high_border_row, low_border_column, high_border_column = 3,5,0,2
elif( (3 <= row <=5 ) and (3 <= column <= 5) ):
low_border_row, high_border_row, low_border_column, high_border_column = 3,5,3,5
elif( (3 <= row <=5 ) and (6 <= column <= 8) ):
low_border_row, high_border_row, low_border_column, high_border_column = 3,5,6,8
elif( (6 <= row <=8 ) and (0 <= column <= 2) ):
low_border_row, high_border_row, low_border_column, high_border_column = 6,8,0,2
elif( (6 <= row <=8 ) and (3 <= column <= 5) ):
low_border_row, high_border_row, low_border_column, high_border_column = 6,8,3,5
elif( (6 <= row <=8 ) and (6 <= column <= 8) ):
low_border_row, high_border_row, low_border_column, high_border_column = 6,8,6,8
for i in range(low_border_row,high_border_row+1):
for j in range(low_border_column,high_border_column+1):
tts.append(board[i][j])
return tts
def validation_check(test_num, row_vec, column_vec, square_vec):
'''This method checks whether or not the number is suitable.'''
if(test_num in row_vec or test_num in column_vec or test_num in square_vec or test_num >=10):
return False
else:
return True
def find_column_vector(column):
global board
cv = []
for i in range(len(board)):
cv.append(board[i][column])
return cv
def assign_a_number(row,column):
global board, steps_taken
test_number = board[row][column] # Current number in that position
#This three lists will be used in validation!
column_vec = find_column_vector(column)
row_vec = board[row]
square_vec = find_threeXthreeSquareElements(row, column)
#cl.print_warning('Row vector : ' + str(board[row]) + '\n' + 'Column vector: ' + str(column_vec) + '\n3x3 vector : ' + str(square_vec) ) #For debugging
while True:
test_number +=1 # The new number may be the one (Algorithm can be slightly improved.)
#cl.print_warning('The candidate number for this position is : ' + str(test_number)) # For debugging
if (validation_check(test_number,row_vec, column_vec, square_vec)):
#İf this happens, picked number is valid!
board[row][column] = test_number
if(len(steps_taken) >= 2 and [row,column] == steps_taken[-1]):
return
else:
steps_taken.append([row,column])
return
elif(test_number >=10):
test_number = 0
board[row][column] = 0
back_track()
return #For test purposes
def back_track():
global steps_taken, board
#print_board() #For debugging
prev_step = []
prev_step.append(steps_taken[-1])
#cl.print_error('The given indexes are : = > ' + str(prev_step[-1][0]) +' '+ str(prev_step[-1][1])) # For debugging
if(len(steps_taken) > 1 ):
del steps_taken[-1]
assign_a_number(prev_step[-1][0],prev_step[-1][1])
return
#This part of the code is for backup.
start_solving = time.time()
while(find_empty_square_index() != None):
r,c = find_empty_square_index()
#cl.print_success('The found index of 0 is : (rov X column) ' + str(r) +' X '+ str(c)) #For debugging
assign_a_number(r,c)
#print_board() #For debugging # This line can be used for Graphical Representation!
end_solving = time.time()
cl.print_success('The time spent for solving is : ' + str(end_solving - start_solving))
print_board()