Assignment - Building a Sudoku Solver in Python

As you go through this notebook, you will find the symbol ??? in certain places. To complete this assignment, you must replace all the ??? with appropriate values, expressions or statements to ensure that the notebook runs properly end-to-end.

Guidelines

1. Make sure to run all the code cells, otherwise you may get errors like NameError for undefined variables.
2. Do not change variable names, delete cells or disturb other existing code. It may cause problems during evaluation.
3. In some cases, you may need to add some code cells or new statements before or after the line of code containing the ???.
4. Since you'll be using a temporary online service for code execution, save your work by pressing CTRL+S to save your work at regular intervals.
5. Questions marked (Optional) will not be considered for evaluation, and can be skipped. They are for your learning. You can crosscheck your solutions for optional questions here: https://jovian.ai/samanvitha/solutions-to-sudoku-solver-assignment-optional-questions
6. If you are stuck, you can ask for help on the bootcamp Slack group. Post errors, ask for hints and help others, but please don't share the full solution answer code to give others a chance to write the code themselves.
7. There are some tests included with this notebook to help you test your implementation. However, after submission your code will be tested with some hidden test cases. Make sure to test your code exhaustively to cover all edge cases.
8. Please DON'T add any print statements in the notebook

How to Run the Code and Save Your Work

Option 1: Running using free online resources (1-click, recommended): Click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

Option 2: Running on your computer locally: To run the code on your computer locally, you'll need to set up Python & Conda, download the notebook and install the required libraries. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Saving your work: You can save/sync your assignment notebook by pressing CTRL+S to your Jovian profile, so that you can access it later and continue your work. Keep saving your work from time to time.

Introduction

In this assignment, we'll write a Python program which can solve a Sudoku, a popular Japanese puzzle you may have seen in newspapers. Here's what a Sudoku looks like:

It's a 9x9 grid containing several blank spaces and some numbers (between 1 and 9). There are also nine 3x3 subgrids (indicated by the dark lines).

Solving a Sudoku: To solve a Sudoku, you must fill all the blank spaces in the above 9x9 grid with digits so that each column, each row and each of the nine 3x3 subgrids (also called "boxes") contain all of the digits from 1 to 9, without repetition.

Here's the solution to the above puzzle:

Can you verify that this solution matches the criteria mentioned above?

Sudoku World Record: In 2018, China's Wang Shiyao set a new world record in Sudoku on Wednesday when she managed to solve a 9x9 sudoku grid in 54.44 seconds at the World Sudoku & Puzzle Championship held in Prague.

Let's see if we can beat that record with a Python program, without solving even a single Sudoku by hand.

Here are the steps we'll follow to create a Sudoku solver in Python:

1. Represent a Sudoku as a list of lists in Python
2. Create helper functions to extract rows, columns and boxes from the Sudoku
3. Create functions to check if a Sudoku is valid or complete
4. Use a recursive strategy to solve a Sudoku by trial & error
5. Read 100 Sudokus from a file and solve them all together

1. Puzzle Representation

The first step for solving any real-world problem is to figure out the representation for the inputs and outputs of the problem. In this case, the input is an unsolved Sudoku puzzle and the output is the solved version of the input puzzles

We'll use a list of lists of numbers to represent a Sudoku puzzle.

Here's how we can represent the above puzzle: