Part B
Contents
Part B#
General introduction to part B
Part B concerns Sudoku puzzles. Your task will be to write a class Sudoku . Each task B1-B8 will be to implement some part of the class. You do not need to submit your answers separately. Instead, please submit the entire class in the field for the last task (task B8).
A Sudoku puzzle might look like the left figure below. The objective is to fill all fields in the 9 x 9 grid with digits so that each row, each column, and each of the nine 3 x 3 blocks contain all of the digits from 1 to 9. The right figure below shows the solution to the puzzle.
Source: Wikipedia
In all tasks that follow, the sudoku grid will be represented by a list of lists. The inner lists each correspond to a row and their elements are the digits currently on the grid. Empty fields are represented by the digit 0.
Example: The (unsolved) puzzle in the picture above would be represented by the list picture_grid:
# List-of-lists representation of the unsolved Sudoku puzzle above
picture_grid = [[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]]
B1 (1 point)#
Create a class Sudoku with a constructor that takes a parameter grid and stores its value in an attribute grid.
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
class Sudoku:
def __init__(self, grid):
self.grid = grid
B2 (2 points)#
Add another method in the Sudoku class so that Sudoku objects are printed in a readable way.
The following code:
picture_grid = [[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]]
my_sudoku = Sudoku(picture_grid)
print(my_sudoku)
should produce the printout
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
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
def __str__(self):
res = '\n'
for row in self.grid:
row_str = ' '.join([str(x) for x in row])
res += row_str + '\n'
return res
B3 (1 point)#
Complete the method get_column_as_list() and add it to your class.
def get_column_as_list(self, column_index):
"""Return a list of all entries in the input column.
"""
With picture_grid defined as in task B2, the following code
my_sudoku = Sudoku(picture_grid)
print(my_sudoku.get_column_as_list(0))
print(my_sudoku.get_column_as_list(4))
print(my_sudoku.get_column_as_list(8))
should produce the printout
[5, 6, 0, 8, 4, 7, 0, 0, 0]
[7, 9, 0, 6, 0, 2, 0, 1, 8]
[0, 0, 0, 3, 1, 6, 0, 5, 9]
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
def get_column_as_list(self, column_index):
"""Return a list of all entries in the input column.
"""
return [row[column_index] for row in self.grid]
B4 (3 points)#
Complete the method get_block_as_list() and add it to your class.
def get_block_as_list(self, row_index, column_index):
"""Return a list of all entries in the 3x3 block
that contains the field (row_index, column_index).
Examples:
--------
The following calls ALL return the same thing:
a list of all entries in the top-left block.
sudoku_object.get_block_as_list(0, 0)
sudoku_object.get_block_as_list(0, 1)
sudoku_object.get_block_as_list(0, 2)
sudoku_object.get_block_as_list(1, 0)
sudoku_object.get_block_as_list(1, 1)
sudoku_object.get_block_as_list(1, 2)
sudoku_object.get_block_as_list(2, 0)
sudoku_object.get_block_as_list(2, 1)
sudoku_object.get_block_as_list(2, 2)
The following calls ALL return the same thing:
a list of all entries in the top-middle block.
sudoku_object.get_block_as_list(0, 3)
sudoku_object.get_block_as_list(0, 4)
sudoku_object.get_block_as_list(0, 5)
sudoku_object.get_block_as_list(1, 3)
sudoku_object.get_block_as_list(1, 4)
sudoku_object.get_block_as_list(1, 5)
sudoku_object.get_block_as_list(2, 3)
sudoku_object.get_block_as_list(2, 4)
sudoku_object.get_block_as_list(2, 5)
etc.
"""
With picture_grid defined as in task B2, the following code
my_sudoku = Sudoku(picture_grid)
print(my_sudoku.get_block_as_list(0, 2))
print(my_sudoku.get_block_as_list(4, 8))
print(my_sudoku.get_block_as_list(7, 1))
should produce the printout
[5, 3, 0, 6, 0, 0, 0, 9, 8]
[0, 0, 3, 0, 0, 1, 0, 0, 6]
[0, 6, 0, 0, 0, 0, 0, 0, 0]
Note, however, that the order of the elements in the output list is not important! Your method may order the elements of the output list in any way. Therefore, you do not need to match the example printout element by element.
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
def get_block_as_list(self, row_index, column_index):
"""Return a list of all entries in the 3x3 block
that contains the field (row_index, column_index).
"""
# Find indices for top-left field in the block
row_index_top_left = (row_index//3)*3
col_index_top_left = (column_index//3)*3
block_list = []
for i in range(row_index_top_left, row_index_top_left + 3):
for j in range(col_index_top_left, col_index_top_left + 3):
block_list.append(self.grid[i][j])
return block_list
B5 (4 points)#
Complete the methods all_rows_complete(), all_columns_complete(), and all_blocks_complete() and add them to your class.
def all_rows_complete(self):
"""Check whether all rows contain the digits 1 through 9"""
return True #REPLACE THIS
def all_columns_complete(self):
"""Check whether all columns contain the digits 1 through 9"""
return True #REPLACE THIS
def all_blocks_complete(self):
"""Check whether all blocks contain the digits 1 through 9"""
return True #REPLACE THIS
The method all_rows_complete() should return True if all rows in the grid contain the digits 1 to 9, and False otherwise. The methods all_columns_complete() and all_blocks_complete() should work similarly, for columns and blocks.
NOTE: You may use methods from B1-B4 to solve this problem even if you did not implement them. You may assume that the methods exist and are working as they should.
If you wish, you may use the following function to check that your methods are working correctly:
function for testing
def test_solution_checks():
solved_sudoku_grid = [[4, 5, 3, 8, 2, 6, 1, 9, 7],
[8, 9, 2, 5, 7, 1, 6, 3, 4],
[1, 6, 7, 4, 9, 3, 5, 2, 8],
[7, 1, 4, 9, 5, 2, 8, 6, 3],
[5, 8, 6, 1, 3, 7, 2, 4, 9],
[3, 2, 9, 6, 8, 4, 7, 5, 1],
[9, 3, 5, 2, 1, 8, 4, 7, 6],
[6, 7, 1, 3, 4, 5, 9, 8, 2],
[2, 4, 8, 7, 6, 9, 3, 1, 5],
]
# Apply tests to a correctly completed sudoku
print('\n----------------------------------------------')
print('Running tests on a correctly solved sudoku...')
print('Incorrect methods will generate output below.')
print('No output indicates that your code passed the tests.')
solved_sudoku = Sudoku(solved_sudoku_grid)
rows_complete = solved_sudoku.all_rows_complete()
columns_complete = solved_sudoku.all_columns_complete()
blocks_complete = solved_sudoku.all_blocks_complete()
if not rows_complete:
print('TEST FAILED! all_rows_complete flagged a correctly solved sudoku as incorrect.')
if not columns_complete:
print('TEST FAILED! all_columns_complete flagged a correctly solved sudoku as incorrect.')
if not blocks_complete:
print('TEST FAILED! all_blocks_complete flagged a correctly solved sudoku as incorrect.')
# Apply tests to incorrect sudokus
print('\n----------------------------------------------')
print('Running tests on incorrect sudokus...')
print('Incorrect methods will generate output below.')
print('No output indicates that your code passed the tests.')
row_method_working = True
column_method_working = True
block_method_working = True
for i in range(9):
for j in range(9):
solved_sudoku_grid_copy = [[x for x in row] for row in solved_sudoku_grid]
solved_sudoku_grid_copy[i][j] += 1
sudoku_test = Sudoku(solved_sudoku_grid_copy)
rows = sudoku_test.all_rows_complete()
columns = sudoku_test.all_columns_complete()
blocks = sudoku_test.all_blocks_complete()
if rows:
row_method_working = False
if columns:
column_method_working = False
if blocks:
block_method_working = False
if not row_method_working:
print('TEST FAILED! all_rows_complete flagged one or more incorrect sudokus as correct.')
if not column_method_working:
print('TEST FAILED! all_columns_complete flagged one or more incorrect sudokus as correct.')
if not block_method_working:
print('TEST FAILED! all_blocks_complete flagged one or more incorrect sudokus as correct.')
print('\n----------------------------------------------')
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
def contains_1to9(self, lst):
"""Check whether lst contains 1, 2, 3, ..., 9."""
return sorted(lst) == list(range(1, 10))
def all_rows_complete(self):
"""Check whether all rows contain the digits 1 through 9"""
for row in self.grid:
if not self.contains_1to9(row):
return False
return True
def all_columns_complete(self):
"""Check whether all columns contain the digits 1 through 9"""
for column_index in range(9):
column = self.get_column_as_list(column_index)
if not self.contains_1to9(column):
return False
return True
def all_blocks_complete(self):
"""Check whether all blocks contain the digits 1 through 9"""
row_indices = [0, 3, 6]
column_indices = [0, 3, 6]
for row_index in row_indices:
for col_index in column_indices:
block = self.get_block_as_list(row_index, col_index)
if not self.contains_1to9(block):
return False
return True
B6 (1 point)#
Complete the method is_solved() and add it to your class. The method shall return True if all rows, columns and blocks contain the digits 1 to 9. Otherwise, the method shall return False.
def is_solved(self):
"""Check whether the current grid is a solved sudoku"""
NOTE: You may use methods from B1-B5 to solve this problem even if you did not implement them. You may assume that the methods exist and are working as they should.
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
def is_solved(self):
"""Check whether the current grid is a solved sudoku"""
rows = self.all_rows_complete()
columns = self.all_columns_complete()
blocks = self.all_blocks_complete()
return rows and columns and blocks
B7 (4 points)#
Complete the method candidate_digits() and add it to your class.
def candidate_digits(self):
"""Return a dict of candidate digits for
all of the currently empty fields.
All digits that are not yet in the same
row, column or box as the empty field
are considered candidate digits.
The returned dict has tuples of field
coordinates ((row_index, column_index))
as keys and lists of candidate digits
as values.
Example:
--------
For the grid below, which has only
3 empty fields, the method returns
{(0, 0): [8, 9], (0, 8): [9], (1, 0): [9]}
0 1 2 7 5 3 6 4 0
0 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2
"""
The following code
nearly_solved_grid = [[4, 5, 0, 8, 2, 6, 1, 9, 7],
[8, 0, 2, 5, 7, 1, 6, 3, 4],
[1, 6, 0, 4, 9, 3, 5, 2, 0],
[7, 1, 4, 9, 5, 0, 0, 6, 0],
[5, 0, 6, 1, 0, 7, 0, 4, 0],
[3, 0, 9, 0, 8, 4, 7, 5, 1],
[0, 0, 0, 2, 1, 0, 4, 7, 0],
[6, 0, 1, 3, 4, 5, 9, 8, 2],
[0, 4, 0, 7, 6, 0, 3, 1, 5]]
nearly_solved_sudoku = Sudoku(nearly_solved_grid)
print(nearly_solved_sudoku.candidate_digits())
should produce the printout
{(0, 2): [3], (1, 1): [9], (2, 2): [7], (2, 8): [8], (3, 5): [2], (3, 6): [2, 8],
(3, 8): [3, 8], (4, 1): [2, 8], (4, 4): [3], (4, 6): [2, 8], (4, 8): [3, 8, 9],
(5, 1): [2], (5, 3): [6], (6, 0): [9], (6, 1): [3, 8, 9], (6, 2): [3, 5, 8],
(6, 5): [8, 9], (6, 8): [6], (7, 1): [7], (8, 0): [2, 9], (8, 2): [8], (8, 5): [8, 9]}
NOTE: You may use methods from B1-B6 to solve this problem even if you did not implement them. You may assume that the methods exist and are working as they should.
No submission here. Please submit the entire Sudoku class in the field for task B8. Include your best attempts at all the methods in B1-B8 in that submission.
Example solution
def candidate_digits(self):
"""Return a dict of candidate digits for
all of the currently empty fields.
"""
candidate_digits = {}
for row_index in range(9):
for column_index in range(9):
# Check if this box is empty
if self.grid[row_index][column_index] == 0:
# Check which digits are already in this row, column, and block
row = self.grid[row_index]
column = self.get_column_as_list(column_index)
block = self.get_block_as_list(row_index, column_index)
all_digits = row + column + block
# Construct list of candidates for this box
local_candidates = [x for x in range(1, 10) if x not in all_digits]
# Add list of candidates to dictionary
candidate_digits[(row_index, column_index)] = local_candidates
return candidate_digits
B8 (4 points)#
Complete the method random_solve() and add it to your class.
def random_solve(self):
"""Solve the sudoku by selecting one of the candidate digits
at random until a solution is found"""
The method’s objective is to solve the Sudoku by adding nonzero digits to the empty fields in the grid attribute. The method shall use the following algorithm:
Determine the candidate digits for all empty fields.
For every empty field, randomly select one of the candidate digits for that field and write it in the field.
Check if the full grid that you ended up with meets all the criteria for a solved sudoku. If it does, you are done. Otherwise, go back to step 2 and repeat.
This algorithm is not optimal and is therefore only able to solve sudokus with relatively few empty fields in reasonable time. You may use the puzzle defined by nearly_solved_grid to test it. If random_solve() is correctly implemented it should solve this puzzle within a second.
# Test your method on this grid
nearly_solved_grid = [[4, 5, 0, 8, 2, 6, 1, 9, 7],
[8, 0, 2, 5, 7, 1, 6, 3, 4],
[1, 6, 0, 4, 9, 3, 5, 2, 0],
[7, 1, 4, 9, 5, 0, 0, 6, 0],
[5, 0, 6, 1, 0, 7, 0, 4, 0],
[3, 0, 9, 0, 8, 4, 7, 5, 1],
[0, 0, 0, 2, 1, 0, 4, 7, 0],
[6, 0, 1, 3, 4, 5, 9, 8, 2],
[0, 4, 0, 7, 6, 0, 3, 1, 5]]
NOTE: You may use methods from B1-B7 to solve this problem even if you did not implement them. You may assume that the methods exist and are working as they should.
If you did not solve B7, note that the candidate digits corresponding to nearly_solved_grid are provided in B7. You can use those candidate digits in random_solve() to verify that random_solve() is working correctly.
Example solution
def random_solve(self):
"""Solve the sudoku by selecting one of the candidate digits
at random until a solution is found"""
import random # Can/should be placed outside class
candidate_digits = self.candidate_digits()
while not self.is_solved():
# Choose one of the candidate digits at random, for each empty field
for row_index, column_index in candidate_digits.keys():
local_candidates = candidate_digits[(row_index, column_index)]
random_index = random.randint(0, len(local_candidates)-1)
self.grid[row_index][column_index] = local_candidates[random_index]