Python Sudoku

Overview

This project features a Python based Sudoku game, complete with a backtracking solver and puzzle generation.

Solver

A human might solve a Sudoku puzzle by looking for obvious number placements, and some trial and error. We could build a solver that could work in a similar way using some sort of heuristic to figure out optimal placements, but this is complicated and we have a secret weapon we can use here.

Computers are really fast

Backtracking is a brute force algorithmic approach that tries all possible solutions until a valid one is found. For a human, a backtracking approach is not feasible due to the sheer number of possibilities. But for a computer it is trivial. A backtracking Sudoku solver follows the following procedure:

1. Place a number in an empty cell.
2. Move to the next empty cell and repeat step 1.
3. If a conflict arises (i.e., the number violates Sudoku rules), backtrack to the previous cell and try the next possible number.
4. Continue this process until the entire grid is filled correctly or all possibilities have been exhausted.

Generator

The puzzle generator works by the following process:

1. Randomly fill the first row of the Grid with numbers 1 to 9, in a valid fashion.
2. Use the backtracking solver to fill the rest of the grid with a valid solution.
3. Remove numbers from the grid randomly. Using the solver to ensure that the puzzle remains solvable, and only has a single solution.

Randomness can be increased further by "blending" the rows and columns of the Sudoku grid. This blending can only be done in groups of 3, as each Sudoku sub-grid must contain all numbers from 1 to 9 in addition to the rows in order to be valid

Using this method, you can tweak the difficulty of the generated puzzles by adjusting how many numbers are removed from the grid. The minimum number of numbers (clues) required for a valid Sudoku puzzle is 17, so removing all but 17 numbers will result in the hardest puzzles.

The puzzles generated by this generator and used in this project are stored in the puzzles.json file in the repository. With each seed containing a puzzle configuration for easy, medium, and hard difficulty levels.