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

- 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 `i`

& `j`

. An object of this class represents a position in a Sudoku matrix. `i`

&`j`

represent the row & column of the position respectively.
**barrs**

: A class similar to list but more appropriate to use in function `evaluate()`

.

## Points of Interest

- We may think of improving the backtracking procedure by using more intelligence in function
`evaluate()`

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

## History

- Initially, I did not use the barrs objects in function
`evaluate()`

, instead I'd used `LIST<int>`

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