“””
Template for Programming Assignment FIT1045 – S2 2021
Sudoku
Version 2 (2021-08-13)
Sudoku boards partially retrieved from
– https://puzzlemadness.co.uk
– https://sudokudragon.com
“””
########### Sudoku boards ##############################
small = [[1, 0, 0, 0],
[0, 4, 1, 0],
[0, 0, 0, 3],
[4, 0, 0, 0]]
small2 = [[0, 0, 1, 0],
[4, 0, 0, 0],
[0, 0, 0, 2],
[0, 3, 0, 0]]
big = [[0, 0, 0, 0, 0, 0, 0, 0, 0],
[4, 0, 0, 7, 8, 9, 0, 0, 0],
[7, 8, 0, 0, 0, 0, 0, 5, 6],
[0, 2, 0, 3, 6, 0, 8, 0, 0],
[0, 0, 5, 0, 0, 7, 0, 1, 0],
[8, 0, 0, 2, 0, 0, 0, 0, 5],
[0, 0, 1, 6, 4, 0, 9, 7, 0],
[0, 0, 0, 9, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 3, 0, 0, 0, 2]]
big2 = [[7, 0, 0, 0, 0, 0, 0, 1, 0],
[0, 5, 0, 0, 0, 9, 0, 0, 0],
[8, 0, 0, 0, 3, 0, 0, 4, 0],
[0, 0, 0, 7, 6, 0, 0, 0, 8],
[6, 2, 0, 0, 5, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 3, 0, 7, 0],
[0, 0, 0, 6, 0, 0, 9, 8, 0],
[0, 0, 0, 0, 2, 7, 3, 0, 0],
[0, 0, 2, 0, 8, 0, 0, 5, 0]]
big3 = [[0, 0, 8, 1, 9, 0, 0, 0, 6],
[0, 4, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 7, 6, 0, 0, 1, 3, 0],
[0, 0, 6, 0, 1, 0, 0, 0, 0],
[0, 0, 0, 0, 8, 0, 0, 0, 0],
[4, 0, 0, 0, 0, 2, 0, 0, 5],
[0, 0, 0, 0, 3, 0, 9, 0, 0],
[0, 1, 0, 4, 0, 0, 0, 0, 2],
[0, 0, 0, 0, 0, 0, 0, 5, 7]]
big4 = [[0, 0, 0, 6, 0, 0, 2, 0, 0],
[8, 0, 4, 0, 3, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 9, 0, 0, 0],
[4, 0, 5, 0, 0, 0, 0, 0, 7],
[7, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 0, 5, 0, 0, 0, 8],
[3, 0, 0, 0, 7, 0, 0, 0, 4],
[0, 0, 0, 0, 0, 1, 9, 0, 0],
[0, 0, 0, 2, 0, 0, 0, 6, 0]]
giant = [[ 0, 0, 13, 0, 0, 0, 0, 0, 2, 0, 8, 0, 0, 0, 12, 15],
[ 7, 8, 12, 2, 10, 0, 0, 13, 0, 0, 14, 11, 6, 9, 0, 4],
[11, 10, 0, 0, 0, 6, 12, 5, 0, 3, 0, 0, 0, 14, 0, 8],
[ 1, 0, 0, 0, 14, 0, 2, 0, 0, 4, 6, 0, 16, 3, 0, 13],
[12, 6, 0, 3, 0, 0, 16, 11, 0, 10, 1, 7, 13, 15, 0, 0],
[ 0, 13, 0, 0, 0, 15, 8, 0, 14, 0, 0, 0, 0, 16, 5, 11],
[ 8, 0, 11, 9, 13, 0, 7, 0, 0, 0, 0, 3, 2, 4, 0, 12],
[ 5, 0, 0, 16, 12, 9, 0, 10, 11, 2, 13, 0, 0, 0, 8, 0],
[ 0, 0, 0, 0, 16, 8, 9, 12, 0, 0, 0, 0, 0, 6, 3, 0],
[ 2, 16, 0, 0, 0, 11, 0, 0, 7, 0, 12, 6, 0, 13, 15, 0],
[ 0, 0, 4, 0, 0, 13, 0, 7, 3, 15, 0, 5, 0, 0, 0, 0],
[ 0, 7, 0, 13, 4, 5, 10, 0, 1, 0, 11, 16, 9, 0, 14, 2],
[ 0, 2, 8, 0, 9, 0, 0, 0, 4, 0, 7, 0, 0, 5, 0, 0],
[14, 0, 0, 0, 15, 2, 11, 4, 9, 13, 3, 0, 12, 0, 0, 0],
[ 0, 1, 9, 7, 0, 0, 5, 0, 0, 11, 15, 12, 0, 0, 0, 0],
[16, 3, 15, 0, 0, 14, 13, 6, 10, 1, 0, 2, 0, 8, 4, 9]]
giant2 = [[ 0, 5, 0, 0, 0, 4, 0, 8, 0, 6, 0, 0, 0, 0, 9, 16],
[ 1, 0, 0, 0, 0, 0, 0, 13, 4, 0, 0, 7, 15, 0, 8, 0],
[13, 0, 0, 0, 0, 7, 3, 0, 0, 0, 0, 9, 5, 10, 0, 0],
[ 0, 11, 12, 15, 10, 0, 0, 0, 0, 0, 5, 0, 3, 4, 0, 13],
[15, 0, 1, 3, 0, 0, 7, 2, 0, 0, 0, 0, 0, 5, 0, 0],
[ 0, 0, 0, 12, 0, 3, 0, 5, 0, 11, 0, 14, 0, 0, 0, 9],
[ 4, 7, 0, 0, 0, 0, 0, 0, 12, 0, 15, 16, 0, 0, 0, 0],
[ 0, 0, 0, 0, 14, 0, 15, 0, 6, 9, 0, 0, 0, 0, 12, 0],
[ 3, 0, 15, 4, 0, 13, 14, 0, 0, 0, 0, 1, 0, 0, 7, 8],
[ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 10, 0, 0, 0, 0],
[11, 0, 16, 10, 0, 0, 0, 0, 0, 7, 0, 0, 0, 3, 5, 0],
[ 0, 0, 13, 0, 0, 0, 0, 0, 14, 0, 16, 15, 0, 9, 0, 1],
[ 9, 0, 2, 0, 0, 14, 0, 4, 8, 0, 0, 0, 0, 0, 0, 0],
[ 0, 14, 0, 0, 0, 0, 0, 10, 9, 0, 3, 0, 0, 0, 1, 7],
[ 8, 0, 0, 0, 16, 0, 0, 1, 2, 14, 11, 4, 0, 0, 0, 3],
[ 0, 0, 0, 1, 0, 0, 5, 0, 0, 16, 0, 6, 0, 12, 0, 0]]
giant3 = [[ 0, 4, 0, 0, 0, 0, 0, 12, 0, 1, 0, 0, 9, 0, 8, 0],
[15, 14, 0, 0, 9, 0, 0, 13, 8, 0, 0, 10, 1, 0, 0, 0],
[ 0, 7, 0, 0, 0, 0, 0, 8, 16, 0, 14, 0, 0, 2, 0, 0],
[ 0, 0, 0, 9, 0, 0, 11, 0, 0, 0, 0, 0, 5, 0, 0, 15],
[ 3, 0, 12, 0, 7, 0, 10, 0, 0, 11, 2, 0, 0, 0, 0, 6],
[14, 8, 0, 0, 0, 12, 0, 6, 0, 0, 0, 16, 0, 0, 0, 10],
[ 0, 16, 0, 0, 13, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12, 0],
[ 6, 0, 0, 0, 0, 8, 0, 5, 1, 7, 13, 0, 11, 0, 0, 14],
[ 0, 0, 0, 2, 0, 0, 16, 0, 15, 12, 0, 3, 10, 7, 0, 0],
[ 0, 9, 0, 5, 11, 0, 3, 0, 4, 13, 16, 0, 0, 15, 6, 0],
[ 0, 0, 0, 0, 5, 4, 0, 0, 9, 6, 0, 2, 0, 0, 0, 0],
[ 1, 0, 0, 0, 0, 15, 12, 0, 0, 0, 5, 0, 0, 0, 9, 0],
[12, 10, 0, 15, 0, 1, 0, 0, 2, 9, 3, 4, 0, 0, 5, 0],
[ 0, 0, 0, 3, 10, 0, 4, 0, 0, 15, 0, 0, 0, 0, 0, 0],
[ 0, 0, 0, 0, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 10, 11],
[11, 6, 8, 0, 0, 0, 15, 0, 14, 0, 0, 0, 0, 13, 0, 2]]
sudokus = [[], [], [small, small2], [big, big2, big3, big4], [giant, giant2, giant3]]
########### Module functions ###########################
def print_board(board):
“””
Prints a given board to the console in a way that aligns the content of columns and makes
the subgrids visible.
Input : a Sudoku board (board) of size 4×4, 9×9, or 16×16
Effect: prints the board to the console
For example:
>>> print_board(small2)
——-
| |1 |
|4 | |
——-
| | 2|
| 3| |
——-
>>> print_board(big)
————-
| | | |
|4 |789| |
|78 | | 56|
————-
| 2 |36 |8 |
| 5| 7| 1 |
|8 |2 | 5|
————-
| 1|64 |97 |
| |9 | |
| | 3 | 2|
————-
>>> print_board(giant2)
———————
| 5 | 4 8| 6 | 9G|
|1 | D|4 7|F 8 |
|D | 73 | 9|5A |
| BCF|A | 5 |34 D|
———————
|F 13| 72| | 5 |
| C| 3 5| B E| 9|
|47 | |C FG| |
| |E F |69 | C |
———————
|3 F4| DE | 1| 78|
| | | 9A| |
|B GA| | 7 | 35 |
| D | |E GF| 9 1|
———————
|9 2 | E 4|8 | |
| E | A|9 3 | 17|
|8 |G 1|2EB4| 3|
| 1| 5 | G 6| C |
———————
“””
print(board)
def subgrid_values(board, r, c):
“””
Input : Sudoku board (board), row index (r), and column index (c)
Output: list of all numbers that are present in the subgrid of the board related to the
field (r, c)
For example:
>>> subgrid_values(small2, 1, 3)
[1]
>>> subgrid_values(big, 4, 5)
[3, 6, 7, 2]
>>> subgrid_values(giant2, 4, 5)
[7, 2, 3, 5, 14, 15]
“””
pass
def options(board, i, j):
“””
Input : Sudoku board (board), row index (r), and column index (c)
Output: list of all numbers that player is allowed to place on field (r, c),
i.e., those that are not already present in row r, column c,
and subgrid related to field (r, c)
For example:
>>> options(small2, 0, 0)
[2, 3]
>>> options(big, 6, 8)
[3, 8]
>>> options(giant2, 1, 5)
[2, 5, 6, 9, 11, 12, 16]
“””
pass
def play(board):
“””
Input : Sudoku board
Effect: Allows user to play board via console
“””
print_board(board)
while True:
inp = input().split(‘ ‘)
if len(inp) == 3 and inp[0].isdecimal() and inp[1].isdecimal() and inp[2].isdecimal():
i = int(inp[0])
j = int(inp[1])
x = int(inp[2])
board[i][j] = x
print_board(board)
elif len(inp)==3 and (inp[0] == ‘n’ or inp[0] == ‘new’) and inp[1].isdecimal() and inp[2].isdecimal():
k = int(inp[1])
d = int(inp[2])
if k < len(sudokus) and 0 < d <= len(sudokus[k]):
board = sudokus[k][d-1]
print_board(board)
else:
print('board not found')
elif inp[0] == 'q' or inp[0] == 'quit':
return
else:
print('Invalid input')
########### Functions only relevant for Part II ########
def value_by_single(board, i, j):
"""
Input : board, row, and column index
Output: The correct value for field (i, j) in board if it can be inferred as
either a forward or a backward single; or None otherwise.
For example:
>>> value_by_single(small2, 0, 1)
2
>>> value_by_single(small2, 0, 0)
3
>>> value_by_single(big, 0, 0)
“””
pass
def inferred(board):
“””
Input : Sudoku board
Output: new Soduko board with all values field from input board plus
all values that can be inferred by repeated application of
forward and backward single rule
For example board big can be completely inferred:
>>> inferred(big) # doctest: +NORMALIZE_WHITESPACE
[[2, 1, 3, 4, 5, 6, 7, 8, 9],
[4, 5, 6, 7, 8, 9, 1, 2, 3],
[7, 8, 9, 1, 2, 3, 4, 5, 6],
[1, 2, 4, 3, 6, 5, 8, 9, 7],
[3, 6, 5, 8, 9, 7, 2, 1, 4],
[8, 9, 7, 2, 1, 4, 3, 6, 5],
[5, 3, 1, 6, 4, 2, 9, 7, 8],
[6, 4, 2, 9, 7, 8, 5, 3, 1],
[9, 7, 8, 5, 3, 1, 6, 4, 2]]
But function doesn’t modify input board:
>>> big # doctest: +NORMALIZE_WHITESPACE
[[0, 0, 0, 0, 0, 0, 0, 0, 0],
[4, 0, 0, 7, 8, 9, 0, 0, 0],
[7, 8, 0, 0, 0, 0, 0, 5, 6],
[0, 2, 0, 3, 6, 0, 8, 0, 0],
[0, 0, 5, 0, 0, 7, 0, 1, 0],
[8, 0, 0, 2, 0, 0, 0, 0, 5],
[0, 0, 1, 6, 4, 0, 9, 7, 0],
[0, 0, 0, 9, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 3, 0, 0, 0, 2]]
In board big4 there is nothing to infer:
>>> inferred(big4) # doctest: +NORMALIZE_WHITESPACE
[[0, 0, 0, 6, 0, 0, 2, 0, 0],
[8, 0, 4, 0, 3, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 9, 0, 0, 0],
[4, 0, 5, 0, 0, 0, 0, 0, 7],
[7, 1, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 3, 0, 5, 0, 0, 0, 8],
[3, 0, 0, 0, 7, 0, 0, 0, 4],
[0, 0, 0, 0, 0, 1, 9, 0, 0],
[0, 0, 0, 2, 0, 0, 0, 6, 0]]
“””
pass
########### Driver code (executed when running module) #
import doctest
doctest.testmod()
play(big)