A Sudoku Solver

For quite sometime Sudoku has become a one of the most enjoyable pass time for many people and they are visible every where. We are having daily Sudoku in newspaper, several online website where we can play Sudoku and several apps for hand held devices on android and Apple app store.  In principle I knew how to solve a Sudoku and have tried several of them as well. But I wanted to code my thought process for a computer to do the job for me. Hence I ended up writing my own Sudoku solver.

The solver employs back tracking algorithm to solve a given Sudoku. Moreover if the Sudoku is not a valid one or if it cannot be solved then this programs reports that as well and exits. The idea of sharing this post is to let the users understand how a back tracking algorithm works and how it can be put in code using a stack. The pseudo code for the algorithm is as below:


[Pseudo Code]

1. Input a Sudoku matrix in a 2D Array.
2. Create an empty list from the given problem.
3. Iterate through each entry in the empty list untill we reach the end of list or we end up at no solution.
• At the current place under consideration find a possible value.
• If found then fill that value and add that entry to a "FillStack" 
• If not found then add this value to a reject list and pop the last filled entry and try out a new value.
• Continue the process 
• If we reach the end of empty list, then a valid solution is found. 
• If we reach back at the beginning of the empty list and no valid solution exists

[Source Code] sudoku_solver.cpp