-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathSudoku_solver.py
226 lines (201 loc) · 8.31 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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#
# Sudoku Solver
# by Furkan Ercevik
# 30 October 2021
# This program implements basic features of object-oriented programming and the recursive backtracking algorithm to
# devise a solution to an incomplete Sudoku puzzle
#
import time
import pygame
def get_square_coors(indices: tuple) -> list:
"""
Finds the coordinates of the other elements in the corresponding square
located in
:param indices: row and column indices
:return: list of tuples representing coordinates
"""
coors = []
row, col = indices
# Find the values of the start row and column coordinates
if row < 3:
start_row = 0
elif row < 6:
start_row = 3
else:
start_row = 6
if col < 3:
start_col = 0
elif col < 6:
start_col = 3
else:
start_col = 6
# Append the list of coordinates in the square
for i in range(3):
for j in range(3):
coors.append((start_row + i, start_col + j))
# Remove the initial coordinates
coors.remove(indices)
# Return the final list of coordinates
return coors
class Sudoku(object):
def __init__(self, board=None, file=None):
"""
Constructs a Sudoku object
:param board: 2x2 matrix consisting of numbers from 0-9 where 0 represents an empty cell
"""
# If a board matrix exists use it
if board:
self.board = board
# Otherwise use the text file containing the numbers as the board where each 9 numbers corresponds to a single
# row
else:
self.board = []
with open(file, "r") as f:
w = f.read().replace("\n", " ")
nums = [int(n) for n in w.split()]
for i in range(9):
self.board.append(nums[i*9:(i*9)+9])
def solve(self, squares=None, screen=None, delay=None) -> bool:
"""
Using a backtracking algorithm, this function sets and resets the values of empty cells to numbers between
1 and 9 until all of the cells are filled with values that abide by Sudoku's rules
:param squares: list of square objects that can be manipulated if they exist (for visualization purposes)
:param screen: a pygame screen
:param delay: the delay factor for the visualization
:return: True if all the cells can be properly filled with values from 1-9, False if otherwise
"""
# Iterate over all the rows and columns
for r in range(9):
for c in range(9):
# If the value at board[r][c] is 0 start trying out values from 1-9
if not self.board[r][c]:
for val in range(1, 10):
# Validate that the value at that position works
if self.validate(r, c, val):
self.board[r][c] = val
# If Square objects are passed
if squares:
# Retrieve the affected Square object and call the replace method on it
# Then draw the affected square onto the screen
affected = squares[r][c]
affected.replace(val)
time.sleep(delay)
affected.draw(screen)
pygame.display.update(affected.rect)
# If all the solutions for the next empty cells make logical sense return True
if self.solve(squares, screen, delay):
return True
else:
# Otherwise reassign the current value to 0 and redo the backtracking process
# (for visualization)
self.board[r][c] = 0
if squares:
# Retrieve the changed Square object and call the delete method on it
# Then draw the affect square onto the screen
to_change = squares[r][c]
to_change.delete()
time.sleep(delay)
to_change.draw(screen)
pygame.display.update(to_change.rect)
# If all the values have been tried and don't work then this solution is incorrect
return False
# If there are no more empty cells return True
return True
def solved(self) -> bool:
"""
Checks if the Sudoku board has been solved
:return: True if it solved, False if otherwise
"""
for i in range(9):
for j in range(9):
if self.board[i][j] == 0:
return False
return True
def validate(self, r: int, c: int, val: int) -> bool:
"""
Checks if the value at self.board[r][c] doesn't violate the rules of Sudoku
:param self: the Sudoku object itself
:param val: value that is being checked
:param r: int value corresponding to a row position
:param c: int value corresponding to a col position
:return: True if it doesn't violate rules of Sudoku, False if it does
"""
# Create a list of values in the same column as (r,c)
cols = []
for i in range(9):
if i != r:
cols.append(self.board[i][c])
rows = self.board[r][:c] + self.board[r][c+1:]
sq = get_square_coors((r, c))
sq_vals = []
for s in sq:
r,c = s
sq_vals.append(self.board[r][c])
if val in cols:
return False
if val in rows:
return False
if val in sq_vals:
return False
return True
def __str__(self) -> str:
"""
Returns an elegant string representation of the board
:return: string representing the board and its values
"""
string = ""
for i in range(9):
# Every 3 rows add a big dashed line
if i % 3 == 0:
string += "+---------+---------+---------+\n"
for j in range(9):
# If the col index is a multiple of 3 add a pipe to the string
if j % 3 == 0:
string += "|"
# Add the value or '.' to the string
string += " " + str(self.board[i][j] if self.board[i][j] else ".") + " "
# If the col index is the last one, add a pipe as well
if j == 8:
string += "|"
# Add a new line at every row
string += "\n"
# Add the final big dashed line
string += "+---------+---------+---------+"
return string
# Intended for debugging purposes
def get_col(self, index: int) -> list:
"""
Returns a column of the board corresponding to an index value
:param index: i integer ranging from 0 to 8
:return: a list representing the column
"""
return [val[index] for val in self.board]
def get_row(self, index: int) -> list:
"""
Returns a row of the board corresponding to an index value
:param index: i integer ranging from 0 to 8
:return: a list representing the row
"""
return [val for val in self.board[index]]
def get_col_idx(self, row: int, col: int) -> list:
"""
Returns a list of the indices of a square's column
:param row: row
:param col: col
:return: list of indices
"""
return [(r, col) for r in range(9) if r != row]
def get_row_idx(self, row: int, col: int) -> list:
"""
Returns a list of the indices of a square's row
:param row: row
:param col: col
:return: list of indices
"""
return [(row,c) for c in range(9) if c != col]
def main():
board = [[3, 6, 9, 7, 5, 4, 1, 2, 8], [2, 4, 7, 8, 6, 1, 3, 9, 7], [8, 1, 5, 2, 9, 3, 6, 4, 7], [6, 3, 2, 5, 4, 7, 8, 6, 1], [9, 5, 8, 6, 1, 2, 7, 7, 3], [1, 7, 4, 3, 8, 9, 5, 9, 2], [7, 8, 1, 9, 2, 5, 4, 3, 6], [4, 2, 3, 4, 0, 6, 9, 1, 5], [5, 9, 6, 1, 3, 8, 2, 8, 7]]
s = Sudoku(board=board)
print(s)
s.solve()
print(s)