Description
here you will have to use the functions done in lab for the other functions therefore please
upload them on Gradescope for further use. This assignment may seem slightly daunting at first
but the functions are fairly small so please manage your time efficiently as there will be no extensions.
Most functions would need less than 10-15 lines of code, if you find yourself writing more than 30-40
lines please rethink as you might be doing something wrong or you might do better in implementing them.
A Sudoku is a puzzle with 81 numbers which is the form of a 9×9 grid that is broken into rows,
columns and blocks with the constraint that each row, column and block has unique elements from 1 to
9 i.e. no row,column or block has a repeating element. Each cell has one number inside it and
there is only one valid solution for a Sudoku. Look at Figure 1 for a solved Sudoku.Figure 1: Solved Sudoku
If you look at fig. 1, each row, column and block have 9 values. All of them are unique and non
repeating. The task is that you will be given a partially filled Sudoku with only one valid solution.
Your task will be to solve the Sudoku using backtracking.
Figure 2: Row and Column indexing
Some keywords that we have used –
- Row: It is a row in the grid, it’s numbering starts from 1 and goes till 9. Refer to Figure 2 for
some more clarity.
- Column: It is a column in the grid, it’s numbering starts from 1 and goes till 9. Refer to Figure
2 for some more clarity.
- Block:
A Block is a 3 × 3 grid with 9 numbers. Each number inside the grid is unique. A
Sudoku is made of 9 blocks the numbering can be seen in Figure 3. B1 denotes the first block.
- Position: Denoted by pos in the skeleton code. It defines the position of a cell, it is a pair of
two integers i.e. (row, column). It starts with (1, 1) for the first cell and the last cell will have
position (9, 9). In fig. 1 the value at (2, 2) is 8.
- List: It is a list of 9 numbers. It can be a block, a row or a column.
2Figure 3: Block indexing
Figure 4: Element indexing inside block
A Sudoku is denoted by a list of lists, with each sub-list inside the outer list as a row of the Sudoku.
Each position inside the list of list is an integer. If there is a 0 present it means that position is
empty.
If you look at Figure 1 the representation of that Sudoku in python would be the following –
[[4,3,5,2,6,9,7,8,1],[6,8,2,5,7,1,4,9,3],[1,9,7,8,3,4,…],…] and the representation
of Figure 5 will be – [[5,3,0,0,7,0,0,0,0],[6,0,0,1,9,5,0,0,0],[0,9,8,0,0,0,…],…]
Note: The size of the outer list will be 9 and the size of all the inner lists will be 9 as well.
One way to solve a Sudoku is to list all the possible combinations and then check which of them satisfy
Figure 5: Unsolved Sudoku
3Figure 6: Before and After solving the Sudoku
the constraints. The other algorithm is using this paradigm called Backtracking. Backtracking is an
algorithmic technique for recursively solving problems by attempting to develop a solution progressively,
one piece at a time, and discarding any solutions that do not satisfy the problem’s criteria at any point
in time. The function Sudoku_solver() will use this backtracking algorithm
You only have to implement several functions given in the skeleton code provided to you. Please
download that from Gradescope and fill in the functions. Please read the comments of each function
very carefully before implementing it. You can’t change the name, return type and parameters of the
functions.
Important Note:
- All the indexing is from 1 to 9 but indexing in arrays, tuples and lists is from 0 to 8 so please
make sure you keep this in mind while implementing your code.
- You are not supposed to print any thing inside the functions.
- All functions will be graded separately but make sure the basic functions work because the later
ones will call them and if they have an error you will fail the later functions as well.
- For all of the functions only valid input will be given, no edge-cases or invalid inputs will be
checked.
- Each function has a level and a list of dependencies which include the functions which have to be
implemented before that particular function.
Here is the list of the functions along with their descriptions :
Functions to be implemented: The following functions are need to be implemented.
FUNCTIONS:
- get_block_num(sudoku:List[List[int]], pos:Tuple[int, int]) -> int:
This function takes two parameters position and sudoku and returns the block number of the
block which contains the position.
For example- If the position given is (4,6) then we return 5 as (4,6) is present in block
number 5. (See fig. 2 and 3 for indexing reference). For the input (1,1) the returned value is 1,
for (3,5) the returned value is 2 and for (1,4) the block is 2. Remember that the position is
4defined as (row,column) and indexing starts from 1.
Hint: Try using modulo operator instead of using if-else-statements
Level: Easy
- get_position_inside_block(sudoku:List[List[int]], pos:Tuple[int, int]) -> int
This function takes two parameters position and sudoku and will return the index of the position
inside the corresponding block.
For example, If the position is given as (4,6) then we return 3 as (4,6) position is at
the index 3 of the block 5 (See fig 2, 3 and 4 for indexing reference). For position (1,1)
the returned value is 1 as its at the 1 st place in the 1 st block, similarly (1,2) will return
2 and (1,3) will return 3. Note that (1,4) will again return 1 as its at the 1 st position of
the 2 nd block. Remember that the position is defined as (row,column) and indexing starts from 1.
Dependencies: get_block_num()
Level: Easy
- get_block(sudoku:List[List[int]], x: int) -> List[int]:
This function takes an integer argument i and then returns the i th block of the Sudoku. See fig. 1
for block indexing. Note that block indexing is from 1 to 9 and not 0-8 thus the input x will be
from 1 to 9.
For example If we call get_block(4) in figure 6 after solving Sudoku then it will return
[8, 5, 9, 4, 2, 6, 7, 1, 3] as it is the 4 th block of the Sudoku.
Level: Easy
- get_row(sudoku:List[List[int]], x: int) -> List[int]:
This function takes an integer argument i and then returns the i th row. Row indexing have been
shown above. Note that row indexing is from 1 to 9 and not 0-8 thus the input x will be from 1 to 9.
For example If we call get_row(4) on solved Sudoku of figure 6 then it will return [8, 5, 9, 7, 6, 1, 4, 2, 3]
as it the 4 th row of the solved Sudoku
Level: Basic
- get_column(sudoku:List[List[int]], x: int) -> List[int]:
This function takes an integer argument i and then returns the i th column. Column indexing have
been shown above. Note that block indexing is from 1-9 and not 0-8 thus the input x will be
from 1 to 9.
For example if we call get_column(4) in figure 6 after solving Sudoku then it will return
[6, 1, 3, 7, 8, 9, 5, 4, 2] as it is the 4 th column of the Sudoku.
Level: Basic
- find_first_unassigned_position(sudoku : List[List[int]]) -> Tuple[int, int]:
This function returns the first empty position in the Sudoku. If there are more than 1 position
which is empty then position with lesser row number should be returned. If two empty positions
5have same row number then the position with less column number is to be returned. If the Sudoku
is completely filled then return (-1,-1). The returned value is the position thus will be a tuple
of integers and will be equal to (row,column)
For example, when called on the Sudoku in fig. 5 will return (1,3)
Level: Easy
- valid_list(lst: List[int])->bool:
This function takes a lists as an input and returns true if the given list is valid. The list will be a
single block , single row or single column only. A valid list is defined as a list in which all non
empty elements doesn’t have a repeating element.
Note: A list may be valid even though it doesn’t satisfy the Sudoku or be completely filled. You
just have to check whether the provided list have repetitive non-empty elements or not. If the
list is valid and Sudoku is violated then also you have to return true. Also note that 0 can be
present any number of times as the cell containing 0 is empty. You are NOT allowed to use
dictionaries or hash-maps in this question.
For example: Valid list when called on [1,2,3,0,0,1,7,5,0] will return False due to
repeating number 1. Whereas when called on [5,3,0,0,7,0,0,0,0] will return True
Level: Medium
- valid_Sudoku(sudoku:List[List[int]])->bool:
This function returns True if the whole Sudoku is valid. You will have to check whether each
row, column and block has unique non-empty elements. As in the valid_list() the Sudoku
may have multiple 0s as they just indicate an empty position.
Dependencies: valid_list()
Level: Medium
- get_candidates(sudoku:List[List[int]], pos:Tuple[int, int]) -> List[int]:
This function takes the Sudoku and s position as arguments and returns a list of all the possible
values that can be assigned at that position so that the Sudoku remains valid at that instant.
What this means is that say the block which has this position has the number 5 then 5 is not a
candidate. If the number 3 does not appear in the row, column or block of the position it is a
valid candidate.
Dependencies: get_row(), get_column() and get_block()
Level: Medium
- make_move(sudoku:List[List[int]], pos:Tuple[int, int], num:int) -> List[List[int]]:
It takes the Sudoku, a position and a number as a parameter and returns the Sudoku after placing
the number at the position.
Level: Easy
- undo_move(sudoku:List[List[int]], pos:Tuple[int, int]):
This function fills 0 at position pos in the Sudoku and then returns the modified Sudoku. It will
6undo the move done and make the position empty again.
Level: Easy
- sudoku_solver(sudoku: List[List[int]]) -> Tuple[bool, List[List[int]]]::
This is the main Sudoku solver. This function solves the given incomplete Sudoku and returns
true if a Sudoku can be solved i.e. after filling all the empty positions the Sudoku remains valid
and also returns the solved Sudoku.
Algorithm 1 Solve Sudoku
Require: sudoku : List[List[int]]
while Unassigned position exists do
Get the candidates at that position
for Each candidate do
Make move
Recursively solve for the Sudoku after making move
if Sudoku not solved then
Undo Move
end if
end for
end while
Look at the above pseudo-code for the algorithm to solve a Sudoku. You have to keep on filling
unassigned positions. After finding one you make a guess based on the candidates and the try to solve
the Sudoku with this guess. If it is solved you’re done but if not you undo the move and make another
guess.
Dependencies: get_candidates(), find_first_unassigned_position(), make_move(), undo_move()
Level: Hard
You have been given a starter code which has all the functions with their descriptions written in
the doc-string along with type-hinting as well for your convenience. The starter code takes in the input
from stdin and tries to solve the Sudoku using the function sudoku_solver. It then prints whether
it was able to solve the Sudoku or not. Note that this input/output has been already done, you only
need to complete the functions that are given below.
You cannot have print statements inside the functions you may print while you are solving the
assignment but they have to be removed. Even though we would be importing your functions and
checking the returned values for the correctness, make sure you remove all such print statements from
your functions before you submit your code, since this can lead to undefined behaviour of the auto-grader.
The In-lab components are –
- get_block_num()
- get_block()
- get_row()
The marks breakdown is given in the table below –
7Function Marks
get_block_num
10
get_position_inside_block
10
get_block
5
get_row
5
get_column
5
find_first_unassigned_position
10
valid_list
10
valid_sudoku
10
get_candidates
15
make_move
5
undo_move
5
sudoku_solver
30
Total Marks 120
8
