sudoku-sokver-by-Backtracking

The Problem

We are going to explore the principle of backtracking by using it to solve a game of Sudoku. If you have never heard of Sudoku before, it is a logic-based puzzle game that requires you to combine numbers to come completely fill the board. The objective is for you to fill a 9x9 grid so that each column, each row, and each of the nine 3x3 subgrids that compose the grid contain all the digits from 1–9. When starting, some of the grids are partially filled in.

Here is an example of a starting board.

Backtracking

Backtracking is a general algorithm for finding all (or some) solutions to a problem that incrementally builds candidates to the solution. As soon as it determines that a candidate can not possibly be the solution to the problem, it abandons it (“backtracks”).

When the algorithm abandons a candidate, it will typically return to a previous stage in the problem-solving process. This is the key to the algorithm and also where it gets its name.