MT2500/3500 Final Assignment D:
FP07 - Sudoku
(taken from Project Euler Problem 96)
No prerequisites. Available to all.
Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid. Start:
|
0 0 3 9 0 0 0 0 1 |
0 2 0 3 0 5 8 0 6 |
6 0 0 0 0 1 4 0 0 |
|
0 0 8 7 0 0 0 0 6 |
1 0 2 0 0 0 7 0 8 |
9 0 0 0 0 8 2 0 0 |
|
0 0 2 8 0 0 0 0 5 |
6 0 9 2 0 3 0 1 0 |
5 0 0 0 0 9 3 0 0 |
Your main aim is to write two functions (which may also include further helper functions as you wish).
SolveSudoku(grid,layer)
doTests()
SolveSudoku should accept a single parameter defining your grid to solve. This will be a string, with 0s used to represent cells that need to be completed. The function should return an equivalent string, but of course, there should not be any 0s! The second parameter, layer, may be used to keep track of any recursion that you might use (if you choose not to use it, that's fine, but it must be part of the definition).
The function doTests() does not accept any inputs. It should be used to hold all your tests for the functions you have specified, and should return True if every test passes. This will enable us to check that the final code is working as expected simply by calling assert doTests().
You have also been provided with a function ViewGrid which will assist in displaying a grid, again provided as a string.
Planning
Set up the described functions. Do not write the code for them at this point. You must simply provide the def statements, doc string, and a return statement. You may also give any import commands that you expect to be appropriate.
Start to plan how you will construct these functions. Again, do not write the code, but at a higher level, what functions will your main algorithm need to call? Define those functions carefully in terms of inputs and outputs. (Of course, these may change when you come to program it later, that's fine, but the better you plan now, the less will have to change later.)
Both for the main functions and any sub-functions that you write, include appropriate pre- and post-conditions that verify the input and output. Write some tests that verify the correct operation of these functions. Remember that these tests will fail at the moment because you haven't written the functions!
from textwrap import wrap
from IPython.core.display import display, HTML
#Used for counting the amount of each character in strings
from collections import Counter
def ViewGrid(grid):
""""nice visual output of a sudoku grid. grid provided as single string"""
htmlstr="<style>tr.myContainer :nth-child(3n+0) {border-right:1px solid black} tr.myContainer :last-child {border-right: 0px}</style><table>"
rows = 'ABCDEFGHI'
for row,rowdata in zip(rows,wrap(grid,9)):
if row in "CF":
htmlstr+="<tr class='myContainer' style='border-bottom:1px solid black'><td>"
else:
htmlstr+="<tr class='myContainer'><td>"
htmlstr+="</td><td>".join(list(rowdata))+"</td></tr>"
htmlstr+="</table>"
display(HTML(htmlstr))
#Insert your function def statements, preconditions, postconditions and tests here
def GridToList(grid):
'''
Inputs:
grid: A string of length 81 containing integers from 0 to 9 representing a sudoku grid.
Outputs:
gridL: A lists of lists of rows of grid.
Used to get the grid string into a format which is easier to use for the algorithm.
'''
gridL = []
for i in wrap(grid, 9):
row = []
for char in i:
row.append(int(char))
gridL.append(row)
return gridL
def ListToGrid(gridL):
'''
Inputs:
gridL: A list of lists of rows of a sudoku grid.
Outputs:
test_grid: A string of length 81 containing integers 0 to 9 representing a sudoku grid.
Used to get gridL into the form required for testing post conditions.
'''
test_grid = ''
for row in gridL:
for i in row:
test_grid = test_grid + str(i)
return test_grid
def SolveSudoku(grid, layer = 0):
'''
Inputs:
grid: A string of length 81 representing the sudoku grid containing only integers.
No repeating integers other than 0 in the coloumns, rows or blocks.
Only allowed integers are from 0 to 9.
layer: An integer representing recursion depth, default is zero.
Outputs:
result: A string of length 81 representing the solved grid containing only integers.
No repeating integers in the coloumns, rows or blocks.
0 should not appear.
Also returns ViewGrid(result)
Function to solve sudoku grids using x algorithm.
'''
#Pre-conditions
#Check data types of inputs
assert isinstance(grid,str), 'Grid should be a single string'
assert isinstance(layer,int), 'Layer should be an integer'
#Remove spaces from grid, check length, and check all characters are integers
grid = grid.replace(' ','')
2019-12-06