Sudoku Solver

• Download source files - 35.78 KB
• Download demo project - 310.9 KB

Introduction

As the name indicates, the project is to solve a Sudoku puzzle. It also includes some special features.

Background

A knowledge of backtracking algorithms such as Solution to the N Queens problem would be helpful.

• http://en.wikipedia.org/wiki/Backtracking
• http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128

Concepts Used

Backtracking

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

1. Can solve partial Sudoku puzzles (Can solve Sudoku puzzles having more than one solution).
2. Can find out the number of solutions a given puzzle has.
3. Can check validity of a given puzzle.
4. The digits which are part of the problem appear in a color different from the other digits in the solution.
5. Any modification to a problem can be done after it has been solved easily by clicking "Modify input" button.
6. 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:

1. 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.
2. 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.
3. num: A class derived from System::Windows::Forms::DomainUpDown. Includes two integers i & j. An object of this class represents a position in a Sudoku matrix. i &j represent the row & column of the position respectively.
4. barrs: A class similar to list but more appropriate to use in function evaluate().

Points of Interest

1. We may think of improving the backtracking procedure by using more intelligence in function evaluate().
2. The backtracking procedure seemed to be the most appropriate procedure since:
   1. It is quite simple to apply to this problem.
   2. Any solution involving recursive calls would surely result in a stack overflow during runtime.
   3. 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

1. Just run the demo project. To do this, download the file sud_demo.zip. Unzip the file. Run the file sud_demo/release/sudoku.
2. Fill in the puzzle. The numbers can be fed using tab key and the keypad quickly or by using just the mouse leisurely.
3. Click the Submit button.
4. You see the solution.
5. If the problem has many solutions, the first 10 (LIMIT defined in stdafx.h) are only evaluated.
6. To see the next solution, click the Next Solution button.
7. If you want to modify the problem, click the Modify input button.
8. To enter a new problem, click Clear All.

History

1. Initially, I did not use the barrs objects in function evaluate(), instead I'd used LIST<int> objects.
2. Even before that, I did not even use these lists and had designed an evaluation involving only backtracking.
3. Also, previously sudokugame was an unmanaged class.