Project Examples: A Sudoku Solver Implementation

While on vacation in Florida, I got a bit restless during some downtime and broke out Visual Studio in order to see if there was anything I wanted to try and program. One of the ideas that came up was a Sudoku solver.

The project took a day or so to code. The goals of this implementation were, to establish a proof-of-concept:

1. Store a Sudoku puzzle in computer memory.

2. Access the Sudoku puzzle and display it on the screen.

3. Create and implement an algorithm to solve a Sudoku puzzle that a user inputs.

These goals were all met with the project. The implementation was written in C++ and uses a command-line interface to interact with the user.

In order to show off what this implementation can do, I took some screenshots. The puzzle used in this example is located here: http://www.sudoku.ws/extreme-20.htm

Here is what the user sees when the program is started. There is a blank Sudoku grid and a menu of options. The user can input a puzzle either 1 number at a time, or iterate through each spot and input the entire puzzle. I prefer option 1 to enter my puzzles.

When option 1 is selected, you are prompted to enter a value for each spot at (x, y) on the coordinate system. At any time, the user may stop entering new numbers, which will take him back to the main menu.

Here is my screen after I finished entering the puzzle. The puzzle values are displayed along with the main menu. From here, if we were trying to solve the puzzle manually, we can use option 4 to view a list of candidate numbers for a certain spot.

In this screen, I elected to view the candidate list for spot (1,1) on the Sudoku grid. The program calculates the valid candidates and returns the list for display. This information is helpful for those trying to manually solve the puzzle.

Finally, the option that is the backbone of the entire project, is the automated solver. I selected the automated solver and it returned 1 solution. This solution matches exactly with the posted solution on the web-site that provided the test puzzles. If there were more than 1 solution, the user has the option of viewing them 1 at a time in a slide-show format. At any time, the user may select the solution he wishes to do more work with  and that puzzle is then brought back to the main menu. This feature should be of help to Sudoku puzzle designers as they can see how removing numbers from the puzzle impacts the candidate lists for each spot.

The command line implementation utilizes a greedy algorithm and recursion to solve the puzzle. The first thing the solver does is scan the grid to determine which spot has the least amount of valid candidate numbers. From here, the solver simply inputs the first candidate and then repeats the process. When a puzzle becomes unsolvable, where an empty spot has no valid candidates, control is simply returned to a previous spot, and the next valid candidate is attempted. The algorithm has O(n ^ 2) time complexity due to the nested loops within each recursive call, but there is an upper limit since each Sudoku puzzle has, at maximum, 81 empty slots.

If you would like to try out the solver, I have uploaded it to Google Drive. Simply download the Sudoku solver and run it on your PC.

The next stage of this project is to implement the SudokuPuzzle class in a Windows form application that will allow us to create a GUI (graphical user interface) in order to allow easier puzzle input. I would also like the option to save and load puzzles for the application.

If you would like to see the source code for the SudokuPuzzle class, it is available here. The class contains the solver method.