-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku_generator.py
306 lines (279 loc) · 10.9 KB
/
sudoku_generator.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
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
import math
import random
"""
This was adapted from a GeeksforGeeks article "Program for Sudoku Generator" by Aarti_Rathi and Ankur Trisal
https://www.geeksforgeeks.org/program-sudoku-generator/
"""
# in each of the 9 rows of the board, no digit is repeated, each digit occurs once
# same for 9 columns
# in each of the 9 3x3 outlined boxes of the board, no digit is repeated, each digit occurs once
# SudokuGenerator class generates a Sudoku puzzle and the solution
class SudokuGenerator:
'''
create a sudoku board - initialize class variables and set up the 2D board
This should initialize:
self.row_length - the length of each row
self.removed_cells - the total number of cells to be removed
self.board - a 2D list of ints to represent the board
self.box_length - the square root of row_length
Parameters:
row_length is the number of rows/columns of the board (always 9 for this project)
removed_cells is an integer value - the number of cells to be removed
Return:
None
'''
def __init__(self, row_length, removed_cells):
# constructor of SudokuGenerator class
# row_length is always 9
# removed_cells varies based on difficulty level chosen
self.row_length = row_length
self.removed_cells = removed_cells # number of cells to be removed
self.box_length = int(math.sqrt(self.row_length))
self.board = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
'''
Returns a 2D python list of numbers which represents the board
Parameters: None
Return: list[list]
'''
def get_board(self):
# each nested list represents a row
return self.board
'''
Displays the board to the console
This is not strictly required, but it may be useful for debugging purposes
Parameters: None
Return: None
'''
def print_board(self):
for i in range(len(self.board)):
if i % 3 == 0 and i != 0:
print("-------------")
for j in range(len(self.board[0])):
if j % 3 == 0 and j != 0:
print(" | ", end="")
if j == 8:
print(self.board[i][j])
else:
print(str(self.board[i][j]) + " ", end="")
return None
'''
Determines if num is contained in the specified row (horizontal) of the board
If num is already in the specified row, return False. Otherwise, return True
Parameters:
row is the index of the row we are checking
num is the value we are looking for in the row
Return: boolean
'''
def valid_in_row(self, row, num):
if num in self.board[row]:
# checks that num is in a certain row. If it is, return false, because num cannot be valid in that row
return False
else:
# no repeats of num so num can be added to row
return True
'''
Determines if num is contained in the specified column (vertical) of the board
If num is already in the specified col, return False. Otherwise, return True
Parameters:
col is the index of the column we are checking
num is the value we are looking for in the column
Return: boolean
'''
def valid_in_col(self, col, num):
valid = True
for i in range(0, self.row_length): # 0 to 9, excluded
if num == self.board[i][col]:
valid = False
return valid
'''
Determines if num is contained in the 3x3 box specified on the board
If num is in the specified box starting at (row_start, col_start), return False.
Otherwise, return True
Parameters:
row_start and col_start are the starting indices of the box to check
i.e. the box is from (row_start, col_start) to (row_start+2, col_start+2)
num is the value we are looking for in the box
Return: boolean
'''
def valid_in_box(self, row_start, col_start, num):
valid = True
# + 3 because need inclusive col_start + 2
for i in range(col_start, (col_start + 3)):
for j in range(row_start, (row_start + 3)):
if self.board[j][i] == num:
# checks if duplicate of num in 3x3 box
valid = False
return valid
'''
Determines if it is valid to enter num at (row, col) in the board
This is done by checking that num is unused in the appropriate, row, column, and box
Parameters:
row and col are the row index and col index of the cell to check in the board
num is the value to test if it is safe to enter in this cell
Return: boolean
'''
def is_valid(self, row, col, num):
valid = False
if self.valid_in_row(row, num) == True:
# checks that row is valid. If it is, continue.
if self.valid_in_col(col, num) == True:
# checks that col is valid. If it is, continue.
# finds row_start based on row
if row < 3:
row_start = 0
elif row < 6:
row_start = 3
else:
row_start = 6
# finds col_start based on col
if col < 3:
col_start = 0
elif col < 6:
col_start = 3
else:
col_start = 6
if self.valid_in_box(row_start, col_start, num) == True:
# checks that box is valid. If it is, valid = True.
valid = True
return valid
'''
Fills the specified 3x3 box with values
For each position, generates a random digit which has not yet been used in the box
Parameters:
row_start and col_start are the starting indices of the box to check
i.e. the box is from (row_start, col_start) to (row_start+2, col_start+2)
Return: None
'''
def fill_box(self, row_start, col_start):
for i in range(col_start, (col_start + 3)):
for j in range(row_start, (row_start + 3)):
found_valid_num = False
while found_valid_num == False:
# randint() function found via https://docs.python.org/3/library/random.html
# a <= int <= b
# returns a random number from 1-9 inclusive
rand_num = random.randint(1, 9)
# checks if rand_num exists in board
if self.is_valid(j, i, rand_num) == True:
self.board[j][i] = rand_num
found_valid_num = True
'''
Fills the three boxes along the main diagonal of the board
These are the boxes which start at (0,0), (3,3), and (6,6)
Parameters: None
Return: None
'''
def fill_diagonal(self):
self.fill_box(0, 0)
self.fill_box(3, 3)
self.fill_box(6, 6)
'''
DO NOT CHANGE
Provided for students
Fills the remaining cells of the board
Should be called after the diagonal boxes have been filled
Parameters:
row, col specify the coordinates of the first empty (0) cell
Return:
boolean (whether or not we could solve the board)
'''
def fill_remaining(self, row, col):
if (col >= self.row_length and row < self.row_length - 1):
row += 1
col = 0
if row >= self.row_length and col >= self.row_length:
return True
if row < self.box_length:
if col < self.box_length:
col = self.box_length
elif row < self.row_length - self.box_length:
if col == int(row // self.box_length * self.box_length):
col += self.box_length
else:
if col == self.row_length - self.box_length:
row += 1
col = 0
if row >= self.row_length:
return True
for num in range(1, self.row_length + 1):
if self.is_valid(row, col, num):
self.board[row][col] = num
if self.fill_remaining(row, col + 1):
return True
self.board[row][col] = 0
return False
'''
DO NOT CHANGE
Provided for students
Constructs a solution by calling fill_diagonal and fill_remaining
Parameters: None
Return: None
'''
def fill_values(self):
self.fill_diagonal()
self.fill_remaining(0, self.box_length)
'''
Removes the appropriate number of cells from the board
This is done by setting some values to 0
Should be called after the entire solution has been constructed
i.e. after fill_values has been called
NOTE: Be careful not to 'remove' the same cell multiple times
i.e. if a cell is already 0, it cannot be removed again
Parameters: None
Return: None
'''
def remove_cells(self):
# easy: 30; medium: 40; hard: 50; get with self.removed_cells
# selected row and column of user's generated board
for i in range(self.removed_cells):
# finding a row, col coord on board that isn't 0
row = random.randint(0, 8)
col = random.randint(0, 8)
while self.board[row][col] == 0:
row = random.randint(0, 8)
col = random.randint(0, 8)
# removing cell value
self.board[row][col] = 0
'''
DO NOT CHANGE
Provided for students
Given a number of rows and number of cells to remove, this function:
1. creates a SudokuGenerator
2. fills its values and saves this as the solved state
3. removes the appropriate number of cells
4. returns the representative 2D Python Lists of the board and solution
Parameters:
size is the number of rows/columns of the board (9 for this project)
removed is the number of cells to clear (set to 0)
Return: list[list] (a 2D Python list to represent the board)
'''
def generate_sudoku(size, removed):
sudoku = SudokuGenerator(size, removed)
sudoku.fill_values()
board = sudoku.get_board()
sudoku.remove_cells()
board = sudoku.get_board()
boolean_board = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]]
for i in range(9):
for j in range(9):
if board[i][j] != 0:
boolean_board[j][i] = "T"
else:
boolean_board[j][i] = 'F'
return board, boolean_board