Sudoku Master

    

This program can be used to efficiently solve ANY 9x9 Sudoku puzzle, via the backtracking algorithm paired with four candidate elimination techniques: 'Naked Singles', 'Hidden Singles', 'Obvious Pairs' (AKA 'Naked Pairs'), 'Pointing Pairs/Triples'.

The codebase & report contained in this repository was submitted in fulfillment of the coursework assignment detailed in assignment.md. The purpose of this project was to demonstrate proper software development best practices by utilising: Git, Docker, Conda, Unit testing, Error trapping, Profiling, Doxygen, Pre-commit hooks, Linting, Modularity, Prototyping etc.

This submission recieved a grade of 83% (may be subject to moderation in Final Examiners' Meeting in September 2024).

View Project Structure

├── docs
│   └── Doxyfile            # auto-documentation configuration
├── src
│   ├── engine              # core solving algorithms
│   │   ├── __init__.py
│   │   ├── backtracking.py # backtracking algorithm
│   │   ├── basics.py       # basic tools core to the solvers
│   │   └── elimination.py  # candidate elimination techniques
│   ├── toolkit             # utilities for loading, saving & manipulating puzzles
│   │   ├── __init__.py
│   │   ├── generation.py   # generating puzzles
│   │   ├── input.py        # handling inputs to program
│   │   ├── output.py       # handle outputs of program (including visualisation)
│   │   └── validation.py   # validation tools
│   └── solve_sudoku.py     # main executable script
└── tests                   # testing suite
│   ├── test_puzzles/       # puzzle examples used in testing
│   ├── __init__.py
│   ├── test_backtracking.py
│   ├── test_basics.py
│   ├── test_elimination.py
│   ├── test_generation.py
│   ├── test_io.py
│   ├── test_solver.py
│   └── test_validation.py
├── .gitignore              # specifies untracked files to ignore
├── .pre-commit-config.yaml # config for pre-commit hooks
├── assignment.md           # coursework assignment
├── Dockerfile              # containerisation instructions
├── LICENSE                 # license for project
├── README.md               # this file
├── convert_data.py         # script for data conversion
└── environment.yml         # environment specifications

Table of Contents

• Features
• Installation
• Usage
  • Solving Puzzles
  • Visualisation
  • Puzzle Generation
• Frameworks
• Credits

Features

1. Efficient Sudoku Solving Engine

   • Four candidate elimination techniques ('Naked Singles', 'Hidden Singles', 'Obvious Pairs', 'Pointing Pairs/Triples')
   • Backtracking algorithm (enhanced with candidate elimination to reduce search space)

2. Ability to find multiple solutions

   • Option to specify how many solutions to a provided puzzle are desired.

3. Input/Output handling and visualisation

   • Loading puzzles from text files
   • Saving puzzles as text files
   • Intuitive visualisation of puzzles and candidate grids (printed to console)

4. Extensive Validation and Testing

   • Validating puzzles and solutions to puzzles
   • Rigorous tests of all core components to ensure reliability

5. Puzzle Generation

   • Generation of example puzzles which can solved by repeatedly filling in 'Naked Singles'

Installation

First, clone the repository:

$ git clone https://gitlab.developers.cam.ac.uk/phy/data-intensive-science-mphil/c1_assessment/wdk24.git
$ cd wdk24

Method 1: Using Docker

Simply build the docker image (using Dockerfile) and run a container:

$ docker build -t <image-name> .
$ docker run -ti <image-name>

Method 2: Using Conda

Set up the environment using the environment.yml file:

$ conda env create -f environment.yml -n <environment-name>
$ conda activate <environment-name>

To access all puzzles used for evaluation of algorithms during development, run the following commands from the root directory (the output names must be exactly what is given below, otherwise the convert_data.py script will fail):

$ mkdir puzzles/
$ curl https://norvig.com/top95.txt --output puzzles/hard.txt
$ curl https://norvig.com/hardest.txt --output puzzles/hardest.txt
$ curl https://projecteuler.net/project/resources/p096_sudoku.txt --output puzzles/easy.txt
$ python convert_data.py

This is not needed when using method 1 since Dockerfile will do this automatically.

Test Installation (recommended)

After installation, check everything is working by running the testing suite:

$ pytest

Usage

Warning Running the tests in tests/test_solver.py may overwrite solutions saved in solutions/. Backup your solutions before running tests.

Warning If you checkout early commits of the project, ensure that you have a puzzles/ directory in the root of the project before running the testing suite (some tests originally depended on this). The Dockerfile will create this directory automatically.

Solving Puzzles

To solve a Sudoku puzzle, navigate to the root project directory and use the following command:

$ python src/solve_sudoku.py <file-containing-puzzle> [<num-solutions>]

Arguments:

• <file-containing-puzzle>: Specify the path to a text file containing the Sudoku puzzle you want to solve. The file should have a valid Sudoku puzzle format.

• <num-solutions> (optional): Specify the number of solutions you want to find. If not provided, the default value is 1. If you specify more solutions than are possible, then all available solutions will be found.

After running the command, the program will process the Sudoku puzzle provided. If solutions are found, they will be printed to the console and saved in solutions/.

View valid Sudoku puzzle format

003|020|600
900|305|001
001|806|400
---+---+---
008|102|900
700|000|008
006|708|200
---+---+---
002|609|500
800|203|009
005|010|300

View example usage 1

Finding a single solution:

$ python src/solve_sudoku.py puzzles/worlds_hardest_2010.txt
Solution Found in  1.09s

Using candidate elimination and backtracking

1 4 5 |3 2 7 |6 9 8
8 3 9 |6 5 4 |1 2 7
6 7 2 |9 1 8 |5 4 3
------+------+------
4 9 6 |1 8 5 |3 7 2
2 1 8 |4 7 3 |9 5 6
7 5 3 |2 9 6 |4 8 1
------+------+------
3 6 7 |5 4 2 |8 1 9
9 8 4 |7 6 1 |2 3 5
5 2 1 |8 3 9 |7 6 4

Solution saved in ./solutions/worlds_hardest_2010_solution.txt

View example usage 2

Finding multiple solutions:

$ python src/solve_sudoku.py tests/test_puzzles/10_solutions.txt 3
3 Solution(s) Found in  0.262s

Using candidate elimination and backtracking

5 9 4 |1 6 7 |8 3 2
6 1 8 |2 3 9 |5 7 4
3 2 7 |8 5 4 |1 6 9
------+------+------
2 8 9 |7 1 6 |3 4 5
1 7 5 |3 4 8 |2 9 6
4 3 6 |5 9 2 |7 8 1
------+------+------
7 6 2 |4 8 1 |9 5 3
8 4 3 |9 2 5 |6 1 7
9 5 1 |6 7 3 |4 2 8

Solution saved in ./solutions/10_solutions_solution1.txt

5 9 4 |1 6 7 |8 3 2
6 1 8 |2 3 9 |5 7 4
3 2 7 |8 5 4 |1 6 9
------+------+------
2 8 9 |7 1 6 |3 4 5
1 7 5 |3 4 8 |2 9 6
4 3 6 |5 9 2 |7 8 1
------+------+------
7 6 2 |4 8 5 |9 1 3
8 4 3 |9 2 1 |6 5 7
9 5 1 |6 7 3 |4 2 8

Solution saved in ./solutions/10_solutions_solution2.txt

5 9 4 |1 6 7 |8 3 2
6 1 8 |2 3 9 |5 7 4
2 3 7 |4 5 8 |1 6 9
------+------+------
1 8 9 |7 2 6 |3 4 5
3 7 5 |8 4 1 |2 9 6
4 2 6 |3 9 5 |7 8 1
------+------+------
7 6 2 |5 8 4 |9 1 3
8 4 3 |9 1 2 |6 5 7
9 5 1 |6 7 3 |4 2 8

Solution saved in ./solutions/10_solutions_solution3.txt

Visualisation

Print intuitive visualisations of puzzles and their respective candidate grids to the console.

View example usage

$ python
>>> from src.toolkit.input import load_puzzle
>>> from src.toolkit.output import print_puzzle, print_candidates
>>> puzzle = load_puzzle('puzzles/worlds_hardest_2010.txt')
>>> print_puzzle(puzzle)
0 0 5 |3 0 0 |0 0 0
8 0 0 |0 0 0 |0 2 0
0 7 0 |0 1 0 |5 0 0
------+------+------
4 0 0 |0 0 5 |3 0 0
0 1 0 |0 7 0 |0 0 6
0 0 3 |2 0 0 |0 8 0
------+------+------
0 6 0 |5 0 0 |0 0 9
0 0 4 |0 0 0 |0 3 0
0 0 0 |0 0 9 |7 0 0

>>> from src.engine.basics import init_candidates
>>> candidates = init_candidates(puzzle)
>>> print_candidates(candidates)
1269      249       5         | 3         24689     24678     | 14689     14679     1478
8         349       169       | 4679      4569      467       | 1469      2         1347
2369      7         269       | 4689      1         2468      | 5         469       348
----------------------------------------------------------------------------------------------
4         289       26789     | 1689      689       5         | 3         179       127
259       1         289       | 489       7         348       | 249       459       6
5679      59        3         | 2         469       146       | 149       8         1457
----------------------------------------------------------------------------------------------
1237      6         1278      | 5         2348      123478    | 1248      14        9
12579     2589      4         | 1678      268       12678     | 1268      3         1258
1235      2358      128       | 1468      23468     9         | 7         1456      12458

Puzzle generation

You can generate puzzles using the functionality in toolkit/generation.py. These puzzles can be solved by repeatedly filling in 'Naked Singles'. There is no option to generate more challenging puzzles.

View example usage

$ python
>>> from src.toolkit.generation import generate_singles
>>> from src.toolkit.output import save_puzzle
>>> puzzle = generate_singles()
>>> save_puzzle('puzzles/my_puzzle.txt', puzzle)

Frameworks

• Programming Languages: Python was the primary language used for development. Ensure you have Python version 3.11.5 or higher installed on your system.

• Testing Framework: pytest was used for writing and running tests.

• Continuous Integration (CI): Pre-commit hooks were configured using .pre-commit-config.yaml. Ensure you have pre-commit installed

• Containerization: Docker was used for creating a consistent development environment. The Dockerfile in the root directory contains instructions to build a Docker image for the project.

• Documentation: Doxygen used for auto-generated code documentation. Configured via the Doxyfile in the docs/ directory.

To generate documentation, ensure you have doxygen installed (Eg. brew install doxygen). Navigate to docs/ directory and run the following commands:

$ doxygen
$ cd latex
$ make
$ open refman.pdf

Credits

This project was developed by William Knottenbelt. Special thanks to sudoku.com and computerphile for guidance on Sudoku solving techniques.

Sources of Testing Puzzles

• Peter Norvig's Sudoku Solver: Many of the testing puzzles for this project were sourced from Peter Norvig's famous essay on Sudoku solving.
• Project Euler: 50 puzzles were also sourced from Project Euler's Problem 96.
• World's Hardest Puzzles: The two "hardest" Sudoku puzzles in the world were also used for evaluation during development. These were devised by Dr Arto Inkala in 2010 and 2012

I extend my gratitude to these sources for providing high-quality, challenging puzzles that have been instrumental in testing and refining this Sudoku solver.