13,768,258 members
alternative version

#### Stats

63.1K views
17 bookmarked
Posted 26 Jan 2007
Licenced CPOL

# Sudoku Solver

, 7 Feb 2007
Sudoku solver using a backtracking algorithm

## 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.

## 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.

## Share

I've studied info. sc. engg. from Sir MVIT, Bangalore.

I'm interested in programming.

Some of my technical blogs:

http://perl-blog.kbsbng.com/
http://java-blog.kbsbng.com/

I also enjoy writing some webpages such as http://sites.google.com/site/plantencyclopedia/

More about me at http://www.kbsbng.com and http://blog.kbsbng.com.

## You may also be interested in...

 First Prev Next
 Where next ? boffin6328-Jun-07 9:58 boffin63 28-Jun-07 9:58
 Re: Where next ? jonpetitta28-Jun-07 12:24 jonpetitta 28-Jun-07 12:24
 Re: Where next ? boffin6329-Jun-07 4:36 boffin63 29-Jun-07 4:36
 Where's the source? Lee Middle10-Feb-07 23:24 Lee Middle 10-Feb-07 23:24
 Re: Where's the source? kbsbng10-Feb-07 23:27 kbsbng 10-Feb-07 23:27
 Re: Where's the source? kbsbng10-Feb-07 23:32 kbsbng 10-Feb-07 23:32
 Re: Something misssing kbsbng27-Jan-07 0:52 kbsbng 27-Jan-07 0:52
 Re: Something misssing kbsbng27-Jan-07 0:59 kbsbng 27-Jan-07 0:59
 Re: Something misssing kbsbng27-Jan-07 1:10 kbsbng 27-Jan-07 1:10