# CMU 15-112 Summer 2018: Fundamentals of Programming and Computer Science Homework 11 (Due Thurs 14-Jun, at 5pm)

• This assignment is SOLO. This means you may not look at other student's code or let other students look at your code for these problems. See the syllabus for details.

• To start:
1. Create a folder named 'week4'
2. Edit hw11.py using Pyzo
3. When you are ready, submit hw11.py to Autolab. For this homework you will have 20 submission.
• This homework is fully autograded.
• Do not hardcode the test cases in your solutions.
• This homework may be graded for style.

1. solveSudoku(board) [100 pts]
Write the function solveSudoku(board) that takes a partially-completed Sudoku board (a 2d list with 0's representing empty cells), and returns a solved version of the same puzzle, or None if no such solution exists. You may want to make use of code from hw5. If you never completed that code, you should meet with a TA as soon as possible to help you get that code working.

Here is a very simple testing function to help get you started. You will need to test more than this.

def testSolveSudoku(): print('Testing solveSudoku()...', end='') board = [ [ 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 ] ] solved = solveSudoku(board) solution = [ [5, 3, 4, 6, 7, 8, 9, 1, 2], [6, 7, 2, 1, 9, 5, 3, 4, 8], [1, 9, 8, 3, 4, 2, 5, 6, 7], [8, 5, 9, 7, 6, 1, 4, 2, 3], [4, 2, 6, 8, 5, 3, 7, 9, 1], [7, 1, 3, 9, 2, 4, 8, 5, 6], [9, 6, 1, 5, 3, 7, 2, 8, 4], [2, 8, 7, 4, 1, 9, 6, 3, 5], [3, 4, 5, 2, 8, 6, 1, 7, 9] ] assert(solved == solution) print('Passed!')

Notes/Hints:
• You must use recursion and backtracking to solve this problem. You may use loops to assist your approach, but your overall approach must still be recursive backtracking.
• This is a backtracking problem. Study the backtracking template and backtracking examples; they will help.
• Make sure to return None as soon as you determine that a step has no solutions! Otherwise, the code might take a very long time to run.