Jovian
⭐️
Sign In

Python Data Structures and Algorithms - Sudoku Solver

How to run the code and save your work

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to 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, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Saving your work

Before starting the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [1]:
project_name = 'sudoku-solver'
In [2]:
!pip install jovian --upgrade --quiet
In [ ]:
 
In [3]:
import jovian
In [4]:
# Execute this to save new versions of the notebook
jovian.commit(project="dsa-final-project")
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/dsa-final-project" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/dsa-final-project
In [ ]:
 

Problem Statement

For this project, I am going to implement a Sudoku solver. This is considered a hard problem on the LeetCode website. From my research into Sudoku, this is considered to be an NP-Complete problem. Being very brief, an NP-Complete problem is a problem which can be solved with a brute force algorithm, however there is no known way to find a solution quickly. This means that the way to approach the problem and solve quicker than brute force is to use heuristics and approximation algorithms. More information on NP-Completeness can be found at the Wikipedia link in the sources.

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

Each of the digits 1-9 must occur exactly once in each row. Each of the digits 1-9 must occur exactly once in each column. Each of the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid. The '.' character indicates empty cells.

For the sudoku solver, I will be given a string representing a Sudoku puzzle. The strings will look like: '5..91372.3...8.5.9.9.25..8.68.47.23...95..46.7.4.....5.2.......4..8916..85.72...3' which represents the Sudoku grid below:

5 9 1 3 7 2 3 8 5 9 9 2 5 8 6 8 4 7 2 3 9 5 4 6 7 4 5 2 4 8 9 1 6 8 5 7 2 3 I will then return a string of the same form representing the solution to the puzzle.'''

Sources:

https://leetcode.com/problems/sudoku-solver/ https://en.wikipedia.org/wiki/NP-completeness https://www.freecodecamp.org/learn/quality-assurance/quality-assurance-projects/sudoku-solver The Method Here's the systematic strategy we'll apply for solving problems:

State the problem clearly. Identify the input & output formats. Come up with some example inputs & outputs. Try to cover all edge cases. Come up with a correct solution for the problem. State it in plain English. Implement the solution and test it using example inputs. Fix bugs, if any. Analyze the algorithm's complexity and identify inefficiencies, if any. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6. This approach is explained in detail in Lesson 1 of the course. Let's apply this approach step-by-step.

Solution

  1. State the problem clearly. Identify the input & output formats. While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear for you.

Problem

For this problem I will be given a string that represents a valid Sudoku puzzle. I need to solve the puzzle and return a string representing the solved puzzle. A puzzle string will be a string containing 81 characters with valid characters being 1-9 and '.' where '.' represents a space. A valid sudoku puzzle is a puzzle that has one and only one solution and meets the constraints that each digit 1-9 must appear in each row, column, and box once and only once.

Each index of the puzzle string corresponds to the number in the Sudoku grid below.

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80

Input

The input will be a string representing a Sudoku puzzle.

'53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'

Output

The output will be a string representing the solution to the Sudoku puzzle.

'534678912672195348198342567859761423426853791713924856961537284287419635345286179' Based on the above, we can now create a signature of our function:

In [5]:
def solve_sudoku(puzzle):
    pass

Save and upload your work before continuing.

In [6]:
import jovian
In [7]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Creating a new project "naveenk-paymeindia/sudoku-solver" [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver
In [12]:
## 2. Come up with some example inputs & outputs. Try to cover all edge cases.
Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

### Input

To generate my puzzle inputs and outputs, I used the Microsoft Sudoku App and generated a puzzle at each level of difficulty, I then used an existing solver to generate the answer to the puzzle. Note: the difficulty level is considered the level of difficulty for a human to solve using heuristics and logic. It does not neccessarily coorespond to how long it will take a computer to solve.

1. Easy: '8264.95..9.526784343715..626.19427.87925.361434..7125916489532758372419627.316485'
2. Medium: '42....1833........6..3.4.257..15.4.69.2..75.8....6...75...16.422.6.4.8.18.4...76.'
3. Hard: '9...8...2.869..475.5...6.9..251..8..7.8.236...1..6..2.873....4...9.........35.78.'
4. Expert: '5.9...14....3.2.5...7....62394.85.....2.16........3..9..35...9...5..8.....6.39825'
5. Master: '9.64....8.4.6..72......9........24.5.5..761..1.7..4...395.61...........66.89..3..'
6. Grandmaster: '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71..'

#### Edge Cases

The brute force bad case is a valid puzzle that has been designed to cause a brute force algorithm to take a long time to solve.
The invalid puzzle layout is not a valid puzzle as it violates one or more constraints for a Sudoku.
The unsolvable puzzle has a valid layout that does not violate any constraints, but is not a valid puzzle because it does not have a valid solution.
The multiple solutions puzzle is a valid layout that has multiple valid solutions which makes it not be a valid Sudoku puzzle.
The other edge cases are self-explanatory.

7. Brute force bad case: '1..2......65..48...7...69....4.......5...87..7...3..4.......6...8.....57..65.7.89'
8. Invalid Characters: '826409500905267843437150062601942708792503614340071259164895327583724196270316485'
9. Invalid length: '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71'
10. Invalid puzzle layout: '..9..5.1.85.42...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..'
11. Unsolvable puzzle: '234967815758.423696.9381...5.26..4.7.....41......98.23.....3.8...5.1......7......'
12. Multiple Solutions: '..........1..2..3....................4..5..6....................7..8..9..........'

    Output

1. Easy: '826439571915267843437158962651942738792583614348671259164895327583724196279316485'
2. Medium: '429675183358291674671384925783152496962437518145968237597816342236749851814523769'
3. Hard: '937584162286931475451276398625197834798423651314865927873612549569748213142359786'
4. Expert: '529867143641392758837451962394785216752916384168243579283574691915628437476139825'
5. Master: '916427538543618729782359641869132475254876193137594862395761284471283956628945317'
6. Grandmaster: '284596731951783426376124859769258314813479265425361978638912547147835692592647183'
7. Brute Force bad case: '139285476265974813478316925894752361653148792712639548527891634981463257346527189'
8. Invalid Characters: 'invalid characters
9. Invalid Length: 'invalid length'
10. Invalid puzzle layout: 'invalid layout'
11. Unsolvable puzzle: 'unsolvable'
12. Multiple solutions: 'multiple solutions'

    We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).
File "<ipython-input-12-05875a449329>", line 2 Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter: ^ SyntaxError: invalid syntax
In [13]:
test = {
    'input': {
        'puzzle': '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
    },
    'output': '534678912672195348198342567859761423426853791713924856961537284287419635345286179'
}
In [14]:
from jovian.pythondsa import evaluate_test_case
In [15]:
evaluate_test_case(solve_sudoku, test)
Input: {'puzzle': '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'} Expected Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED
Out[15]:
(None, False, 0.003)
In [16]:
tests = []
In [17]:
tests.append(test)
In [18]:
tests.append({
    'input': {
        'puzzle': '8264.95..9.526784343715..626.19427.87925.361434..7125916489532758372419627.316485'
    },
    'output': '826439571915267843437158962651942738792583614348671259164895327583724196279316485'
})
In [19]:
tests.append({
    'input': {
        'puzzle': '42....1833........6..3.4.257..15.4.69.2..75.8....6...75...16.422.6.4.8.18.4...76.'
    },
    'output': '429675183358291674671384925783152496962437518145968237597816342236749851814523769'
})
In [20]:
tests.append({
    'input': {
        'puzzle': '9...8...2.869..475.5...6.9..251..8..7.8.236...1..6..2.873....4...9.........35.78.'
    },
    'output': '937584162286931475451276398625197834798423651314865927873612549569748213142359786'
})
In [21]:
tests.append({
    'input': {
        'puzzle': '5.9...14....3.2.5...7....62394.85.....2.16........3..9..35...9...5..8.....6.39825'
    },
    'output': '529867143641392758837451962394785216752916384168243579283574691915628437476139825'
})
In [22]:
tests.append({
    'input': {
        'puzzle': '9.64....8.4.6..72......9........24.5.5..761..1.7..4...395.61...........66.89..3..'
    },
    'output': '916427538543618729782359641869132475254876193137594862395761284471283956628945317'
})
In [23]:
tests.append({
    'input': {
        'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71..'
    },
    'output': '284596731951783426376124859769258314813479265425361978638912547147835692592647183'
})
In [24]:
tests.append({
    'input': {
        'puzzle': '1..2......65..48...7...69....4.......5...87..7...3..4.......6...8.....57..65.7.89'
    },
    'output': '139285476265974813478316925894752361653148792712639548527891634981463257346527189'
})
In [25]:
tests.append({
    'input': {
        'puzzle': '826409500905267843437150062601942708792503614340071259164895327583724196270316485'
    },
    'output': 'invalid characters'
})
In [26]:
tests.append({
    'input': {
        'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71'
    },
    'output': 'invalid length'
})
In [27]:
tests.append({
    'input': {
        'puzzle': '..9..5.1.85.42...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..'
    },
    'output': 'invalid layout'
})
In [28]:
tests.append({
    'input': {
        'puzzle': '234967815758.423696.9381...5.26..4.7.....41......98.23.....3.8...5.1......7......'
    },
    'output': 'unsolvable'
})
In [29]:
tests.append({
    'input': {
        'puzzle': '..........1..2..3....................4..5..6....................7..8..9..........'
    },
    'output': 'multiple solutions'
})

Evaluate your function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [30]:
from jovian.pythondsa import evaluate_test_cases
In [31]:
evaluate_test_cases(solve_sudoku, tests)
TEST CASE #0 Input: {'puzzle': '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'} Expected Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #1 Input: {'puzzle': '8264.95..9.526784343715..626.19427.87925.361434..7125916489532758372419627.316485'} Expected Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #2 Input: {'puzzle': '42....1833........6..3.4.257..15.4.69.2..75.8....6...75...16.422.6.4.8.18.4...76.'} Expected Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #3 Input: {'puzzle': '9...8...2.869..475.5...6.9..251..8..7.8.236...1..6..2.873....4...9.........35.78.'} Expected Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #4 Input: {'puzzle': '5.9...14....3.2.5...7....62394.85.....2.16........3..9..35...9...5..8.....6.39825'} Expected Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #5 Input: {'puzzle': '9.64....8.4.6..72......9........24.5.5..761..1.7..4...395.61...........66.89..3..'} Expected Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #6 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71..'} Expected Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #7 Input: {'puzzle': '1..2......65..48...7...69....4.......5...87..7...3..4.......6...8.....57..65.7.89'} Expected Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED TEST CASE #8 Input: {'puzzle': '826409500905267843437150062601942708792503614340071259164895327583724196270316485'} Expected Output: invalid characters Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #9 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71'} Expected Output: invalid length Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #10 Input: {'puzzle': '..9..5.1.85.42...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..'} Expected Output: invalid layout Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #11 Input: {'puzzle': '234967815758.423696.9381...5.26..4.7.....41......98.23.....3.8...5.1......7......'} Expected Output: unsolvable Actual Output: None Execution Time: 0.001 ms Test Result: FAILED TEST CASE #12 Input: {'puzzle': '..........1..2..3....................4..5..6....................7..8..9..........'} Expected Output: multiple solutions Actual Output: None Execution Time: 0.002 ms Test Result: FAILED SUMMARY TOTAL: 13, PASSED: 0, FAILED: 13
Out[31]:
[(None, False, 0.003),
 (None, False, 0.002),
 (None, False, 0.002),
 (None, False, 0.002),
 (None, False, 0.001),
 (None, False, 0.003),
 (None, False, 0.002),
 (None, False, 0.002),
 (None, False, 0.001),
 (None, False, 0.001),
 (None, False, 0.001),
 (None, False, 0.001),
 (None, False, 0.002)]

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

Let's save our work before continuing.

In [32]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver
  1. Come up with a correct solution for the problem. State it in plain English. Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution. Come with a correct solution and explain it in simple words below:

The solution will be a recursive brute force solution

1. Get a puzzle string and verify that it contains only valid characters and has the correct length
2. Create a matrix from the puzzle string
3. Verify that the matrix has a valid layout and doesn't violate any constraints
4. Solve the puzzle using the following
5. Get the first cell in the puzzle without a value, if all values are filled, return True (Recursion base case)
6. For each number from 1 - 9 do the following
7. Set the value of the cell to the number
8. Verify that the matrix is a valid sudoku layout
9. solve the puzzle with the added value
10. if we solved the puzzle return True
11. Otherwise undo the value that was entered and try again
12. If we try all numbers without solving the puzzle, return false
13. If we failed to solve the puzzle, return unsolvable
14. If the puzzle was solved, convert the matrix back to a string and return the string

Let's save and upload our work before continuing.

In [33]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver

4. Implement the solution and test it using example inputs. Fix bugs, if any.

Helper functions

In [34]:
import re
In [35]:
def is_valid_characters(puzzle):
    valid_characters = r'^[.1-9]+$'
    return re.match(valid_characters, puzzle)
In [36]:
def is_valid_length(puzzle):
    return len(puzzle) == 81
In [37]:
def string_to_board(sudoku_str):
    board = [[], [], [], [], [], [], [], [], []]
    for i in range(81):
        row = i // 9
        board[row].append(sudoku_str[i])

    return board
In [38]:
def board_to_string(board):
    board_str = ''
    for row in range(len(board)):
        for column in range(len(board[row])):
            board_str += board[row][column]
    return board_str
In [39]:
def is_valid_sudoku(board):
    rows = [[], [], [], [], [], [], [], [], []]
    columns = [[], [], [], [], [], [], [], [], []]
    regions = [[], [], [], [], [], [], [], [], []]

    for row in range(len(board)):
        for column in range(len(board[row])):
            value = board[row][column]
            if value == '.':
                continue
            region = row // 3 * 3 + column // 3
            if value in rows[row] or value in columns[column] or value in regions[region]:
                return False
            else:
                rows[row].append(value)
                columns[column].append(value)
                regions[region].append(value)
    return True
In [40]:
def get_unassigned_cell(grid):
    for row in range(len(grid)):
        for col in range(len(grid[row])):
            if grid[row][col] == '.':
                return row, col
    return len(grid), len(grid[0])

Recursive solving function

In [41]:
def brute_force_solve(grid):
    (row, col) = get_unassigned_cell(grid)
    if row == 9 and col == 9:
        return True

    # Try the values from 1 - 10
    for value in range(1, 10):
        grid[row][col] = str(value)
        if is_valid_sudoku(grid):
            if brute_force_solve(grid):
                return True
        grid[row][col] = '.'

    # If all values failed, return False
    return False
Main Function
In [42]:
def solve_sudoku(puzzle):
    if not is_valid_characters(puzzle):
        return 'invalid characters'

    if not is_valid_length(puzzle):
        return 'invalid length'
    
    board = string_to_board(puzzle)

    if not is_valid_sudoku(board):
        return 'invalid layout'

    if brute_force_solve(board):
        return board_to_string(board)
    else:
        return 'unsolvable'

Execute Test Cases

In [43]:
test_results = dict()
In [44]:
test_results['Brute Force'] = list(map(lambda x: x[2], evaluate_test_cases(solve_sudoku, tests)))
TEST CASE #0 Input: {'puzzle': '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'} Expected Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Actual Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Execution Time: 1047.81 ms Test Result: PASSED TEST CASE #1 Input: {'puzzle': '8264.95..9.526784343715..626.19427.87925.361434..7125916489532758372419627.316485'} Expected Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Actual Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Execution Time: 2.351 ms Test Result: PASSED TEST CASE #2 Input: {'puzzle': '42....1833........6..3.4.257..15.4.69.2..75.8....6...75...16.422.6.4.8.18.4...76.'} Expected Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Actual Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Execution Time: 225.044 ms Test Result: PASSED TEST CASE #3 Input: {'puzzle': '9...8...2.869..475.5...6.9..251..8..7.8.236...1..6..2.873....4...9.........35.78.'} Expected Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Actual Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Execution Time: 290.269 ms Test Result: PASSED TEST CASE #4 Input: {'puzzle': '5.9...14....3.2.5...7....62394.85.....2.16........3..9..35...9...5..8.....6.39825'} Expected Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Actual Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Execution Time: 276.945 ms Test Result: PASSED TEST CASE #5 Input: {'puzzle': '9.64....8.4.6..72......9........24.5.5..761..1.7..4...395.61...........66.89..3..'} Expected Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Actual Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Execution Time: 25.526 ms Test Result: PASSED TEST CASE #6 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71..'} Expected Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Actual Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Execution Time: 3585.865 ms Test Result: PASSED TEST CASE #7 Input: {'puzzle': '1..2......65..48...7...69....4.......5...87..7...3..4.......6...8.....57..65.7.89'} Expected Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Actual Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Execution Time: 11871.417 ms Test Result: PASSED TEST CASE #8 Input: {'puzzle': '826409500905267843437150062601942708792503614340071259164895327583724196270316485'} Expected Output: invalid characters Actual Output: invalid characters Execution Time: 0.01 ms Test Result: PASSED TEST CASE #9 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71'} Expected Output: invalid length Actual Output: invalid length Execution Time: 0.008 ms Test Result: PASSED TEST CASE #10 Input: {'puzzle': '..9..5.1.85.42...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..'} Expected Output: invalid layout Actual Output: invalid layout Execution Time: 0.031 ms Test Result: PASSED TEST CASE #11 Input: {'puzzle': '234967815758.423696.9381...5.26..4.7.....41......98.23.....3.8...5.1......7......'} Expected Output: unsolvable Actual Output: unsolvable Execution Time: 0.155 ms Test Result: PASSED TEST CASE #12 Input: {'puzzle': '..........1..2..3....................4..5..6....................7..8..9..........'} Expected Output: multiple solutions Actual Output: 234165789517829436689347125123476958748953261956218347361592874472681593895734612 Execution Time: 31.138 ms Test Result: FAILED SUMMARY TOTAL: 13, PASSED: 12, FAILED: 1

5. Analyze the algorithm's complexity and identify inefficiencies, if any.

Complexity

For our algorithm's time complexity, let n = number of digits allowed and m = number of blank cells

if we work backwards, when m=1 in the worst case we will try 1×n time. When m=2, in the worst case we will try (1×n)(1×n) and so on. So our worst case time complexity is O(nm)

In [48]:
brute_force_time_complexity = 'O(n ** m)'

For the space complexity, the brute force algorithm has a O(m) complexity. This is due to the fact that we are using recursion to solve the problem and will need to visit all m blank cells to solve the puzzle. Each recursive call will have a copy of the grid on the stack.

In [49]:
brute_force_space_complexity = 'O(m)'

Execution times

Let's develop a chart that shows the execution times for all of the test cases. We will use this chart as we improve our solving algorithms to see the differences in times.

In [50]:
!pip install --upgrade --quiet altair
In [51]:
import altair as alt
import pandas as pd
from io import StringIO
In [52]:
def results_to_dataframe(results):
    chart_data = 'Test Number,Algorithm,Time (ms)\n'
    for test_times in [zip(range(len(v)), [k] * len(v), v) for k,v in results.items()]:
        for test_number, algorithm, time in test_times:
            chart_data += '{},{},{}\n'.format(test_number, algorithm, time)
            
    df = pd.read_csv(StringIO(chart_data))

    return df

def display_chart(test_results):
    chart_data = results_to_dataframe(test_results)
    chart = alt.Chart(chart_data).mark_line().encode(
        x='Test Number',
        y='Time (ms)',
        color='Algorithm'
    ).interactive()

    chart.configure_view(
        continuousHeight=300,
        discreteWidth={'step': 500}
    )
    return chart
In [53]:
display_chart(test_results)
Out[53]:

We can see that test case 7 which was designed as bad case scenario for a brute force algorithm took around 20 seconds to solve. Test case 0 and 6 also had times that were in the seconds range instead of the millisecond range.

Inefficiencies

Due to the fact that solving a sudoku puzzle is an NP-complete problem, any algorithm used to solve a puzzle is going to have the O(n**m)

worst case time complexity. However, the algorithms can be sped up through the use of heuristics, memoization, reframing the problem, and other techniques. Each of these techniques can either prune branches of the search tree or store results so items don't have to be recalculated.

The basic brute force algorithm I wrote uses no heuristics at all and just methodically tries to solve the puzzle in a deterministic way. This does reveal one shortcoming of the algorithm, the algorithm as written cannot determine if there are multiple solutions to a puzzle string. Given a string with multiple solutions, it will always return the same answer. This means that this algorithm can never pass the last test case without introducing a non-deterministic method into the algorithm.

This means that in order to pass all of our test cases, we will need to come up with an algorithm that is non-deterministic so it can find multiple solutions and also potentially uses heuristics or other techniques to speed up the algorithm.

In [54]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver

6. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

In the brute force algorithm, we try every possible value and check if it is a valid value before moving on. Instead of brute forcing the possible values, let's determine the valid values up front and only try them. This reduces the number of choices that we are trying when solving. This also allows us to remove checking if the Sudoku grid is valid for every value as we know we are entering a valid value into the cell.

7. Come up with a correct solution for the problem. State it in plain English.

Come with the optimized correct solution and explain it in simple words below:

1. Get a puzzle string and verify that it contains only valid characters and has the correct length
2. Create a matrix from the puzzle string
3. Verify that the matrix has a valid layout and doesn't violate any constraints
4. Solve the puzzle using the following
5. Get the first cell in the puzzle without a value, if all cells have a value, return True (Recursion base case)
6. For the cell, get the possible values that are valid for that cell
7. For each value in the list of valid values, set the cell to that value
8. solve the puzzle with the added value
9. if we solved the puzzle return True
10. Otherwise undo the value that was entered and try again
11. If we try all numbers without solving the puzzle, return false
12. If we failed to solve the puzzle, return unsolvable
13. If the puzzle was solved, convert the matrix back to a string and return the string

Let's save and upload our work before continuing.

In [55]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver

8. Implement the solution and test it using example inputs. Fix bugs, if any.

Helper functions
In [56]:
def get_region(row, col, grid):
    region_rows = row // 3 * 3
    region_cols = col // 3 * 3
    result = []
    for row in range(region_rows, region_rows + 3):
        for col in range(region_cols, region_cols + 3):
            result.append(grid[row][col])
    return result
In [57]:
def get_row(row, grid):
    return grid[row]
In [58]:
def get_column(col, grid):
    result = []
    for row in range(len(grid)):
        result.append(grid[row][col])
    return result
Function to return a list of valid values
In [59]:
def get_possible_valid_values(row, col, grid):
    complete_set = {'1', '2', '3', '4', '5', '6', '7', '8', '9'}
    current_values = set(get_row(row, grid) + get_column(col, grid) + get_region(row, col, grid))
    current_values.discard('.')
    possible_values = current_values.symmetric_difference(complete_set)
    return list(possible_values)
Heuristic brute force function
In [60]:
def heuristic_solve(grid):
    (row, col) = get_unassigned_cell(grid)
    if row == 9 and col == 9:
        return True

    # Try the values from 1 - 10
    valid_values = get_possible_valid_values(row, col, grid)
    for value in valid_values:
        grid[row][col] = str(value)
        if heuristic_solve(grid):
            return True
        grid[row][col] = '.'

    # If all values failed, return False
    return False
Main solving function
In [61]:
def solve_sudoku(puzzle):
    if not is_valid_characters(puzzle):
        return 'invalid characters'

    if not is_valid_length(puzzle):
        return 'invalid length'
    
    board = string_to_board(puzzle)

    if not is_valid_sudoku(board):
        return 'invalid layout'

    if heuristic_solve(board):
        return board_to_string(board)
    else:
        return 'unsolvable'
Evaluate the test cases
In [62]:
test_results['Heuristic Brute Force'] = list(map(lambda x: x[2], evaluate_test_cases(solve_sudoku, tests)))
TEST CASE #0 Input: {'puzzle': '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'} Expected Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Actual Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Execution Time: 55.475 ms Test Result: PASSED TEST CASE #1 Input: {'puzzle': '8264.95..9.526784343715..626.19427.87925.361434..7125916489532758372419627.316485'} Expected Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Actual Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Execution Time: 0.224 ms Test Result: PASSED TEST CASE #2 Input: {'puzzle': '42....1833........6..3.4.257..15.4.69.2..75.8....6...75...16.422.6.4.8.18.4...76.'} Expected Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Actual Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Execution Time: 4.606 ms Test Result: PASSED TEST CASE #3 Input: {'puzzle': '9...8...2.869..475.5...6.9..251..8..7.8.236...1..6..2.873....4...9.........35.78.'} Expected Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Actual Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Execution Time: 3.872 ms Test Result: PASSED TEST CASE #4 Input: {'puzzle': '5.9...14....3.2.5...7....62394.85.....2.16........3..9..35...9...5..8.....6.39825'} Expected Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Actual Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Execution Time: 4.472 ms Test Result: PASSED TEST CASE #5 Input: {'puzzle': '9.64....8.4.6..72......9........24.5.5..761..1.7..4...395.61...........66.89..3..'} Expected Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Actual Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Execution Time: 5.822 ms Test Result: PASSED TEST CASE #6 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71..'} Expected Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Actual Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Execution Time: 108.44 ms Test Result: PASSED TEST CASE #7 Input: {'puzzle': '1..2......65..48...7...69....4.......5...87..7...3..4.......6...8.....57..65.7.89'} Expected Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Actual Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Execution Time: 2202.648 ms Test Result: PASSED TEST CASE #8 Input: {'puzzle': '826409500905267843437150062601942708792503614340071259164895327583724196270316485'} Expected Output: invalid characters Actual Output: invalid characters Execution Time: 0.01 ms Test Result: PASSED TEST CASE #9 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71'} Expected Output: invalid length Actual Output: invalid length Execution Time: 0.008 ms Test Result: PASSED TEST CASE #10 Input: {'puzzle': '..9..5.1.85.42...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..'} Expected Output: invalid layout Actual Output: invalid layout Execution Time: 0.039 ms Test Result: PASSED TEST CASE #11 Input: {'puzzle': '234967815758.423696.9381...5.26..4.7.....41......98.23.....3.8...5.1......7......'} Expected Output: unsolvable Actual Output: unsolvable Execution Time: 0.098 ms Test Result: PASSED TEST CASE #12 Input: {'puzzle': '..........1..2..3....................4..5..6....................7..8..9..........'} Expected Output: multiple solutions Actual Output: 526193874819724536734568219251679483948352167367841952182936745473285691695417328 Execution Time: 2.317 ms Test Result: FAILED SUMMARY TOTAL: 13, PASSED: 12, FAILED: 1

9. Analyze the algorithm's complexity and identify inefficiencies, if any.

Our overall worst case time complexity is still considered to be O(n**M) since we don't and can't know if there is puzzle than can be crafted to hit every worse case option, However, due to the fact that we are eliminating choosing invalid choices up front, this has the effect of pruning the search tree of branches that will lead to failure and improving our overall execution times.

In [63]:
heuristic_time_complexity = 'O(n ** m)'

Our overall space complexity is still O(m) since we are still using a recursive algorithm that has a copy of the grid in the stack for each function call.

In [65]:
heuristic_space_complexity = 'O(m)'

Let's compare our execution times between the brute force solution and the heuristic brute force solution.

In [66]:
display_chart(test_results)
Out[66]:

We can see that adding that one simple heuristic has caused all of our solving times to be in the millisecond range, although test case 7 is still taking the longest.

Finally, this version of the algorithm is still deterministic as it still solves the puzzle determinstically to return the same answer for a given puzzle. So this algorithm will continue to not be able to pass the last test.

In [68]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver

10. Apply the right technique to overcome the inefficiency. Repeat steps 3 to 6.

For our final solving algorithm we are going to reframe the problem and use an algrithm suited for those problems. A Sudoku puzzle is what is called an Exact Cover problem. We can use an algorithm devised by Donald Knuth called Algorithm X to solve exact cover problems. For this to work we are going to transform our data into a constraint problem that meets the definition of an exact cover problem and then use Algorithm X to solve the problem.

Exact Cover Problem What exactly is an Exact Cover Problem? This excerpt from GeeksForGeeks is an excellent description.

Given a collection S of subsets of set X, an exact cover is the subset S* of S such that each element of X is contained is exactly one subset of S*. It should satisfy following two conditions –

The Intersection of any two subsets in S* should be empty. That is, each element of X should be contained in at most one subset of S* Union of all subsets in S* is X. That means union should contain all the elements in set X. So we can say that S* covers X. Example (standard representation) –

Let S = { A, B, C, D, E, F } and X = {1, 2, 3, 4, 5, 6, 7} such that –

A = {1, 4, 7} B = {1, 4} C = {4, 5, 7} D = {3, 5, 6} E = {2, 3, 6 7} F = {2, 7} Then S* = {B, D, F} is an exact cover, because each element in X is contained exactly once in subsets {B, D, F} . If we union subsets then we will get all the elements of X –

B ⋃ D ⋃ F

{ 1 , 2 , 3 , 4 , 5 , 6 , 7 } The Exact cover problem is a decision problem to determine if exact cover exists or not. It is considered to be NP-Complete problem.

The problem can be represented in the form of a matrix where the row represents the subsets of S and columns represent the element of X. The above problem can be represented as –

Problem Matrix

In the context of matrix representation, our exact cover is the selection of rows such that each column contains only single 1 among selected rows. So we can see below that each column have only single 1 among selected rows B, D, F.

Solution

Source: https://www.geeksforgeeks.org/exact-cover-problem-algorithm-x-set-1/

Algorithm X In the Dancing Links paper, Donald Knuth outlined a solving algorithm that he named Algorithm X shown below.

If A is empty, the problem is solved; terminate successfully. Otherwise choose a column, c (deterministically). Choose a row, r, such that A[r, c] = 1 (nondeterministically). Include r in the partial solution. For each j such that A[r, j] = 1, delete column j from matrix A; for each i such that A[i, j] = 1, delete row i from matrix A. Repeat this algorithm recursively on the reduced matrix A. Source: Dancing Links - Donald E. Knuth, Stanford University

The paper then goes on to describe an implementation of Algorithm X utilizing doubly linked circular lists to implement a sparse matrix. The use of the doubly linked lists allows for quick removal and restoral of columns and rows in the matrix. Donald Knuth named this implementation Dancing Links or DLX for short.

Converting a puzzle to a form suited for Algorithm X. In order to solve a Sudoku puzzle with Algorithm X/Dancing Links we need to convert the puzzle grid into an Exact Cover problem. This is accomplished by creating a constraint matrix of a Sudoku board and then using Algorithm X to find the subsets that cover the matrix. Additionally the algorithm is designed to find all solutions to an exact cover problem, so if there are multiple solutions with a puzzle string, we will be able to determine that if we get more than one solution.

The sudoku constraint matrix A Sudoku puzzle has 4 constraints

A single number (1 - 9) must in a cell Each number must appear only once in a row Each number must appear only once in a column Each number must appear only once in a region To create the matrix, we need to enumerate our choices and each constraint.

Since we have 81 cells in the board, each of the 4 constraints will take 81 columns to enumerate each constraint. This gives us a matrix with 324 columns. Each of our rows needs to enumerate our possible choices. Since we have 81 cells and 9 distinct values, we have 729 rows in our matrix.

We can programatically build the matrix by enumerating through each of the choices and setting the appropriate columns to a value and leaving the other columns empty.

In order to save space we will be building the matrix as a sparse matrix using doubly-linked lists.

Once we have the matrix, we can solve the puzzle by 'covering' the existing columns and rows that have already been selected by the puzzle and then calling the Algorithm X solve function to solve the problem.

  1. Come up with a correct solution for the problem. State it in plain English. Come with the optimized correct solution and explain it in simple words below:

Get a puzzle string and verify that it contains only valid characters and has the correct length Create a sparse matrix representing the constraints of a Sudoku puzzle. Create a matrix from the puzzle string Verify that the matrix has a valid layout and doesn't violate any constraints Use the Sudoku matrix to cover the constraint columns and rows in the sparse matrix Call the Algorithm X solve function passing in the sparse matrix. If the solve function returns multiple answers, return multiple solutions If the solve function return no answers, return unsolvable If the solve function returned 1 answer, iterate through the returned constraints and update the Sudoku matrix with the answers. Convert the matrix to a puzzle string and return the string. Let's save and upload our work before continuing.

In [69]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver

12. Implement the solution and test it using example inputs. Fix bugs, if any.

Classes for the nodes in the sparse matrix

In [70]:
class Node:
    def __init__(self, header_node=None):
        self.value = None
        self.left = self
        self.right = self
        self.up = self
        self.down = self
        self.column = header_node

    def __repr__(self):
        return "Node: {}:{}".format(self.column.value, self.value)
In [71]:
class HeaderNode(Node):
    def __init__(self, column_id):
        super().__init__(header_node=self)
        self.value = column_id
        self.node_count = 0

    def __repr__(self):
        return "HeaderNode: {} Node Count: {}".format(self.value, self.node_count)
In [72]:
class RootNode(Node):
    def __init__(self, value='root'):
        super().__init__()
        self.value = value

    def __repr__(self):
        return "RootNode"
Create the sparse matrix representing the constraints of a Sudoku puzzle
In [73]:
from itertools import product
In [74]:
def create_sparse_matrix():
    # Create our root node for accessing the matrix
    root = RootNode()

    # Create the column header nodes
    for i in range(4 * 9 * 9):
        new_node = HeaderNode(i)
        last = root.left
        new_node.right = root
        root.left = new_node
        new_node.left = last
        last.right = new_node

    # Create the rows
    for row, column, value in [rcv for rcv in product(range(9), range(9), range(1, 10))]:
        row_start = None
        for offset in range(4):
            node_value = (row, column, value)
            if offset == 0:
                column_id = row * 9 + column
            elif offset == 1:
                column_id = offset * 81 + row * 9 + value - 1
            elif offset == 2:
                column_id = offset * 81 + column * 9 + value - 1
            elif offset == 3:
                region = row // 3 * 3 + column // 3
                column_id = offset * 81 + region * 9 + value - 1
            else:
                raise Exception('Too many offsets')

            # Link new node up/down
            header = root.right
            for x in range(column_id):
                header = header.right
            new_node = Node(header)
            new_node.value = node_value
            last = header.up
            new_node.down = header
            header.up = new_node
            new_node.up = last
            last.down = new_node
            header.node_count += 1

            # Link new node left/right
            if row_start:
                last = row_start.left
                new_node.right = row_start
                row_start.left = new_node
                new_node.left = last
                last.right = new_node
            else:
                row_start = new_node
    return root
Utility function to print the sparse matrix
In [75]:
def print_matrix(root_node):
    root = root_node
    node = root
    while node.right != root:
        node = node.right
        column = node
        print(node)
        while node.down != column:
            node = node.down
            print('\t{} Right{} Left{}'.format(node, node.right, node.left))
        node = node.down
Function to cover the nodes in the sparse matrix from the Sudoku matrix
In [76]:
def cover_values(board, root_node):
    root = root_node
    start = []

    for row in range(len(board)):
        for column in range(len(board[row])):
            if board[row][column] == '.':
                continue

            value = (row, column, int(board[row][column]))
            column_id = row * 9 + column

            column = root.right
            while column != root:
                if column.value == column_id:
                    break
                column = column.right

            cover(column)

            row_node = column.down
            while row_node != column:
                if row_node.value == value:
                    break
                row_node = row_node.down

            start.append(row_node)
            right_node = row_node.right
            while right_node != row_node:
                cover(right_node)
                right_node = right_node.right

    return start
Functions to get the column with the minimum number of nodes and to cover and uncover nodes
In [77]:
# get_min_column implements Heuristic S from Donald Knuth's Dancing Links paper. The Heuristic is to
# choose the column with the least number of nodes.

def get_min_column(root_node):
    root = root_node
    node = root.right
    min_column = node
    while node.right != root:
        node = node.right
        if node.node_count < min_column.node_count:
            min_column = node
    return min_column
In [78]:
def cover(node):
    column = node.column

    column.right.left = column.left
    column.left.right = column.right

    row = column.down
    while row != column:
        right_node = row.right
        while right_node != row:
            right_node.up.down = right_node.down
            right_node.down.up = right_node.up
            right_node.column.node_count -= 1
            right_node = right_node.right
        row = row.down
In [79]:
def uncover(node):
    column = node.column

    row = column.up
    while row != column:
        left_node = row.left
        while left_node != row:
            left_node.up.down = left_node
            left_node.down.up = left_node
            left_node.column.node_count += 1
            left_node = left_node.left
        row = row.up

    column.right.left = column
    column.left.right = column
Implementation of Algorithm X using the sparse matrix
In [80]:
def solve(k, root, solutions=[]):
    global answers

    if root.right == root:
        answers.append(solutions[:])
        if len(answers) > 1:
            raise Exception('multiple solutions found')
        return

    column = get_min_column(root)
    cover(column)

    row_node = column.down
    while row_node != column:
        solutions.append(row_node)

        right_node = row_node.right
        while right_node != row_node:
            cover(right_node)
            right_node = right_node.right

        solve(k + 1, root, solutions)

        solutions.pop()

        column = row_node.column
        left_node = row_node.left
        while left_node != row_node:
            if left_node != root:
                uncover(left_node)
            left_node = left_node.left
        row_node = row_node.down

    uncover(column)
Function to convert a solution from Algorithm X to a Sudoku matrix
In [82]:
def solution_to_board():
    global answers
    if not answers:
        return [[]]

    boards = []

    for answer in answers:
        board = [
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None],
            [None, None, None, None, None, None, None, None, None]
        ]
        for node in answer:
            row, col, value = node.value
            board[row][col] = str(value)
        boards.append(board)
    return boards
Main function
In [83]:
def solve_sudoku(puzzle):
    global answers
    
    if not is_valid_characters(puzzle):
        return 'invalid characters'

    if not is_valid_length(puzzle):
        return 'invalid length'

    board = string_to_board(puzzle)

    if not is_valid_sudoku(board):
        return 'invalid layout'

    root = create_sparse_matrix()

    start = cover_values(board, root)

    answers = []
    try:
        solve(0, root, start)
    except Exception:
        return 'multiple solutions'

    if not answers:
        return 'unsolvable'

    results = solution_to_board()
    return board_to_string(results[0])
Global answers list
In [84]:
answers = []
Evaluate test cases
In [85]:
test_results['Algorithm X'] = list(map(lambda x: x[2], evaluate_test_cases(solve_sudoku, tests)))
TEST CASE #0 Input: {'puzzle': '53..7....6..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'} Expected Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Actual Output: 534678912672195348198342567859761423426853791713924856961537284287419635345286179 Execution Time: 33.501 ms Test Result: PASSED TEST CASE #1 Input: {'puzzle': '8264.95..9.526784343715..626.19427.87925.361434..7125916489532758372419627.316485'} Expected Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Actual Output: 826439571915267843437158962651942738792583614348671259164895327583724196279316485 Execution Time: 32.678 ms Test Result: PASSED TEST CASE #2 Input: {'puzzle': '42....1833........6..3.4.257..15.4.69.2..75.8....6...75...16.422.6.4.8.18.4...76.'} Expected Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Actual Output: 429675183358291674671384925783152496962437518145968237597816342236749851814523769 Execution Time: 38.497 ms Test Result: PASSED TEST CASE #3 Input: {'puzzle': '9...8...2.869..475.5...6.9..251..8..7.8.236...1..6..2.873....4...9.........35.78.'} Expected Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Actual Output: 937584162286931475451276398625197834798423651314865927873612549569748213142359786 Execution Time: 94.743 ms Test Result: PASSED TEST CASE #4 Input: {'puzzle': '5.9...14....3.2.5...7....62394.85.....2.16........3..9..35...9...5..8.....6.39825'} Expected Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Actual Output: 529867143641392758837451962394785216752916384168243579283574691915628437476139825 Execution Time: 28.364 ms Test Result: PASSED TEST CASE #5 Input: {'puzzle': '9.64....8.4.6..72......9........24.5.5..761..1.7..4...395.61...........66.89..3..'} Expected Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Actual Output: 916427538543618729782359641869132475254876193137594862395761284471283956628945317 Execution Time: 29.049 ms Test Result: PASSED TEST CASE #6 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71..'} Expected Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Actual Output: 284596731951783426376124859769258314813479265425361978638912547147835692592647183 Execution Time: 43.865 ms Test Result: PASSED TEST CASE #7 Input: {'puzzle': '1..2......65..48...7...69....4.......5...87..7...3..4.......6...8.....57..65.7.89'} Expected Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Actual Output: 139285476265974813478316925894752361653148792712639548527891634981463257346527189 Execution Time: 53.712 ms Test Result: PASSED TEST CASE #8 Input: {'puzzle': '826409500905267843437150062601942708792503614340071259164895327583724196270316485'} Expected Output: invalid characters Actual Output: invalid characters Execution Time: 0.009 ms Test Result: PASSED TEST CASE #9 Input: {'puzzle': '2.4.....1......4.63...2.8..7..2.831.....7.2...25.....86..9.....1..8.5.92.92..71'} Expected Output: invalid length Actual Output: invalid length Execution Time: 0.014 ms Test Result: PASSED TEST CASE #10 Input: {'puzzle': '..9..5.1.85.42...2432......1...69.83.9.....6.62.71...9......1945....4.37.4.3..6..'} Expected Output: invalid layout Actual Output: invalid layout Execution Time: 0.038 ms Test Result: PASSED TEST CASE #11 Input: {'puzzle': '234967815758.423696.9381...5.26..4.7.....41......98.23.....3.8...5.1......7......'} Expected Output: unsolvable Actual Output: unsolvable Execution Time: 30.1 ms Test Result: PASSED TEST CASE #12 Input: {'puzzle': '..........1..2..3....................4..5..6....................7..8..9..........'} Expected Output: multiple solutions Actual Output: multiple solutions Execution Time: 33.879 ms Test Result: PASSED SUMMARY TOTAL: 13, PASSED: 13, FAILED: 0
13. Analyze the algorithm's complexity and identify inefficiencies, if any.

Even the Algorithm X/Dancing links algorithm still has the O(nM) time complexity. However, it has been shown to be very fast in solving exact cover problems and is the preferred algorithm used for both generating and solving Sudoku puzzles.

In [86]:
algorithm_X_time_complexity = 'O(n ** m)'

The space complexity for Algorithm X is constant based off of n. In the sparse matrix, each column can have n entries, one for each value that can satisfy the constraint. This turns out to be n×n×4×n which is equal to 4n3, so the space complexity in Big O notation would be O(n**3) since Big O notation ignores constants.

In [87]:
algorithm_X_space_complexity = 'O(n ** 3)'

Finally, let's compare our execution times from all three algorithms

In [89]:
display_chart(test_results)
Out[89]:

As we can see from the timing results all of the test cases was were consistently around 100ms. Overall using Algorithm X appears to be the best algorithm for solving the problem of Sudoku puzzles. Due to the non-determinism in the algorithm, we were also able to pass test case 12 and determine that it had multiple solutions.

In [90]:
jovian.commit(project=project_name, environment=None)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "naveenk-paymeindia/sudoku-solver" on https://jovian.ai [jovian] Uploading notebook.. [jovian] Uploading additional files... [jovian] Committed successfully! https://jovian.ai/naveenk-paymeindia/sudoku-solver

Submit the Project

In [ ]:
jovian.submit(assignment="pythondsa-project")
[jovian] Attempting to save notebook..
In [ ]: