-
Notifications
You must be signed in to change notification settings - Fork 1k
/
sudoku_generator.py
194 lines (157 loc) · 5.52 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
import math,random
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):
pass
"""
Returns a 2D python list of numbers which represents the board
Parameters: None
Return: list[list]
"""
def get_board(self):
pass
"""
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):
pass
"""
Determines if num is contained in the specified row (horizontal) of the board
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 unused_in_row(self, row, num):
pass
"""
Determines if num is contained in the specified column (vertical) of the board
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 unused_in_col(self, col, num):
pass
"""
Determines if num is contained in the 3x3 box specified on the board
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 unused_in_box(self, row_start, col_start, num):
pass
"""
Determines if it is safe to enter num at coordinates (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 coordinates 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 check_if_safe(self, row, col, num):
pass
"""
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):
pass
"""
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):
pass
"""
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:
row += 1
col = 0
if row >= self.row_length:
return True
if self.board[row][col] != 0:
return self.fill_remaining(row, col+1)
for num in range(1, self.row_length + 1):
if self.check_if_safe(row, col, num):
self.board[row][col] = num
if self.fill_remaining(row, col + 1):
return True
self.board[row][col] = 0
return False
"""
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):
count = self.removed_cells
while count != 0:
cell_num = random.randint(0, self.row_length * self.row_length - 1)
row = cell_num // self.row_length
col = cell_num % self.row_length
if self.board[row][col] != 0:
count -= 1
self.board[row][col] = 0
"""
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()
return board