As the name indicates, the project is to solve a Sudoku puzzle. It also includes some special features.
A knowledge of backtracking algorithms such as Solution to the N Queens problem would be helpful.
Some problems can be solved in a certain number of steps sequentially, wherein in each step we have to choose between certain number of possibilities. We make a guess of the choice among the possibilities and proceed to the next step. After making each choice, we check whether it is feasible. If not, we make a different choice. At a certain step, if none of the possibilities turns out to be feasible, we know that anyone/some of our guesses is/are wrong. Hence, we go to the previous step and make a different choice and proceed. Hence the name backtracking.
Some Special Features
- Can solve partial Sudoku puzzles (Can solve Sudoku puzzles having more than one solution).
- Can find out the number of solutions a given puzzle has.
- Can check validity of a given puzzle.
- The digits which are part of the problem appear in a color different from the other digits in the solution.
- Any modification to a problem can be done after it has been solved easily by clicking "Modify input" button.
- Has an easy-to-use interface.
Using the Code
All important parts of the code are provided with appropriate comments and hence I feel not much explanation is needed of the code here. I would like to get the reader's reaction to this issue.
The code consists of the following classes among others:
sudokugame: Contains the heart of the project (the function
evaluate() to solve the puzzle). The function
validsarr(bool comp) is used to find whether a given array is a completely (
if comp=true)/incompletely (
if comp=false) filled valid Sudoku row/column/grid.
LIST: A template class containing some list operations. An object of this class is used in class
sudokugame to store solutions of a given puzzle.
num: A class derived from
System::Windows::Forms::DomainUpDown. Includes two integers
j. An object of this class represents a position in a Sudoku matrix.
j represent the row & column of the position respectively.
barrs: A class similar to list but more appropriate to use in function
Points of Interest
- We may think of improving the backtracking procedure by using more intelligence in function
- The backtracking procedure seemed to be the most appropriate procedure since:
- It is quite simple to apply to this problem.
- Any solution involving recursive calls would surely result in a stack overflow during runtime.
- A procedure involving guesses is the most appropriate since a procedure involving conformative evaluation in each step would be very complex, if possible.
How to Use
- Just run the demo project. To do this, download the file sud_demo.zip. Unzip the file. Run the file sud_demo/release/sudoku.
- Fill in the puzzle. The numbers can be fed using tab key and the keypad quickly or by using just the mouse leisurely.
- Click the Submit button.
- You see the solution.
- If the problem has many solutions, the first 10 (
LIMIT defined in stdafx.h) are only evaluated.
- To see the next solution, click the Next Solution button.
- If you want to modify the problem, click the Modify input button.
- To enter a new problem, click Clear All.
- Initially, I did not use the barrs objects in function
evaluate(), instead I'd used
- Even before that, I did not even use these lists and had designed an evaluation involving only backtracking.
- Also, previously
sudokugame was an unmanaged class.