Sudoku Solver

A Sudoku game and solver that uses a backtracking algorithm to find a solution to any solvable game. Added functionality to play the game as well as manually input your own board. Built in Python using the Pygame library.

The Solving Method

The solving method that I chose to implement uses backtracking. Backtracking is when you revert back to the previous step or solution as soon as it is determined that the current solution cannot be continued into a complete one. The algorithm starts by finding an empty spot on the board and attempts to put all numbers (1-9) in that spot. It then checks each number to see if it is possible to put it in that spot by seeing if there is already the same number in that row, column, or box. If a possible number is found, then put that number in the spot, and recursively attempt to fill the next empty spot of the board. If a possible number is not found, then backtrack to the previous spot, reset it, and continue to look for a different possible number. When there are no empty spots left on the board, then the algorithm arrives at the base case, and the board is solved.