Solving Sudoku¶
The primary description of this coursework is available on the CM20252 Moodle page. This is the Jupyter notebook you must complete and submit to receive marks.
You must follow all instructions given in this notebook.
Restart the kernel and run all cells before submitting the notebook. This will guarantee that we will be able to run your code for testing.
Remember to save your work regularly.
Getting Started¶
You already know that you will be writing a Sudoku solver. You need to implement your solver in Python in this notebook. You can use any of the appropriate problem-solving techniques discussed in the lectures. You are encouraged to modify the basic algorithms. Be creative.
You will be given Sudoku puzzles that either have a single solution or no solution. You will need to identify the solution, if there is one.
Below is a sample puzzle along with its solution.


Sample Sudokus¶
You can test your code on a set of 20 sample Sudoku puzzles. This set is similar to the test set that will be used to assess your work.
The following code will load 20 Sudoku puzzles and their solutions into two 20x9x9 numpy arrays. Empty cells are designated by zeros.
In [1]:
import numpy as np
# Load sudokus
sudokus = np.load(“data/sudokus.npy”)
print(“Shape of one sudoku array:”, sudokus[0].shape, “. Type of array values:”, sudokus.dtype)
# Load solutions
solutions = np.load(“data/sudoku_solutions.npy”)
print(“Shape of one sudoku solution array:”, solutions[0].shape, “. Type of array values:”, solutions.dtype, “\n”)
# Print the first sudoku…
print(“Sudoku #1:”)
print(sudokus[0], “\n”)
# …and its solution
print(“Solution of Sudoku #1:”)
print(solutions[0])
Shape of one sudoku array: (9, 9) . Type of array values: float64
Shape of one sudoku solution array: (9, 9) . Type of array values: float64
Sudoku #1:
[[0. 0. 4. 0. 8. 3. 0. 0. 2.]
[0. 5. 1. 0. 0. 4. 3. 0. 0.]
[0. 0. 0. 0. 9. 6. 7. 1. 0.]
[1. 2. 0. 8. 0. 0. 0. 0. 6.]
[0. 4. 0. 0. 0. 0. 5. 0. 0.]
[8. 3. 0. 6. 0. 7. 9. 0. 0.]
[0. 6. 0. 3. 0. 9. 0. 4. 0.]
[0. 0. 7. 0. 0. 0. 2. 0. 5.]
[0. 9. 0. 0. 5. 0. 8. 0. 3.]]
Solution of Sudoku #1:
[[9. 7. 4. 1. 8. 3. 6. 5. 2.]
[6. 5. 1. 2. 7. 4. 3. 8. 9.]
[2. 8. 3. 5. 9. 6. 7. 1. 4.]
[1. 2. 9. 8. 3. 5. 4. 7. 6.]
[7. 4. 6. 9. 1. 2. 5. 3. 8.]
[8. 3. 5. 6. 4. 7. 9. 2. 1.]
[5. 6. 8. 3. 2. 9. 1. 4. 7.]
[3. 1. 7. 4. 6. 8. 2. 9. 5.]
[4. 9. 2. 7. 5. 1. 8. 6. 3.]]
Your code¶
Define a function called sudoku_solver() that takes one Sudoku puzzle (a $9 \times 9$ numpy array) as input and returns the solved Sudoku as a $9 \times 9$ numpy array. Note that the test set may contain invalid Sudokus, that is, Sudokus with no solution. In such a case, your function should return a $9 \times 9$ numpy array whose values are all equal to -1.
You may use more than one cell to write your code (but this is not necessary).
In [ ]:
def sudoku_solver(sudoku):
“””
Solves a Sudoku puzzle and returns its unique solution.
Input
sudoku : 9×9 numpy array
Empty cells are designated by 0.
Output
9×9 numpy array of integers
It contains the solution, if there is one. If there is no solution, all array entries should be -1.
“””
### YOUR CODE HERE
return solved_sudoku
Testing your code¶
You can test your code on the sudoku puzzles that we have provided in the following cell. This will work only if all of your code is above the test cell. Otherwise, the test cell does not have access to the sudoku_solver() function. Before you submit, please comment out any code that you used to test your function on the training puzzles.
In [ ]:
# Uncomment the following block to test your code. Comment it out again before submitting.
# for i in range(len(sudokus)):
# sudoku = sudokus[i].copy()
# print(“This is sudoku number”, i)
# print(sudoku)
# your_solution = sudoku_solver(sudokus[i])
# print(“This is your solution for sudoku number”, i)
# print(your_solution)
# print(“Is your solution correct?”)
# print(np.array_equal(your_solution, solutions[i]))
How we will test your code¶
We will test your code using the hidden tests in the following cell. Specifically, the hidden tests will test your sudoku_solver() function on a different set of 20 sudoku puzzles of similar difficulty. Make sure all of your code is above our test cell. Otherwise, the test cell will not have access to the sudoku_solver() function and you will receive zero marks.
IMPORTANT: How to submit¶
If any of the following instructions is not clear, please ask your tutors well ahead of the submission deadline.
Before you submit¶
• Restart the kernel (Kernel $\rightarrow$ Restart & Run All) and make sure that you can run all cells from top to bottom without any errors.
• Make sure that the test cell has access to the sudoku_solver() function that you defined and make sure that this function returns the solved Sudoku in the correct data type and shape.
• Please comment out any code that you used to test your function on the training puzzles.
• Make sure that your code is written in Python 3 (and not in Python 2!). You can check the Python version of the current session in the top-right corner below the Python logo.
Submission file¶
• Please upload to Moodle a single Jupyter notebook file called “ai4_sudoku.ipynb”. Do not compress/zip your Jupyter notebook file.
• Do not include any identifying information. Marking is anonymous.
In [ ]:
# This is a TEST CELL. Do not delete or change. All of your code must be written above this cell.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.
In [ ]:
# This is a TEST CELL. Do not delete or change.