Python Sudoku Solver

Background

The goal of this project was to develop a Sudoku Solver in Python to further my Python programming abilities. I made use of a backtracking algorithm for this program. It is verified to work for any standard 9x9 Sudoku puzzle.

Backtracking Algorithm

Backtracking is an algorithm which works by recursively trying to solve the problem by incrementally trying solutions and then going backwards and removing the solutions which fail to satisfy the constraints of the problem.

Steps:

  1. Find next empty space.

  2. Attempt to place digits 1-9 in the empty space

  3. Check if digit is valid in the current space based on current board

  4. a) if digit is valid, recursively attempt to fill board using steps 1-3

    b) if digit is not valid, reset the square you just filled and go back to previous step

  5. Once the board is full we have found a solutions.

Future Modifications

Create a GUI that makes it easy to try different boards and find solutions for those boards.