a c++ code that solves sudoku

I have to write a c++ code that can solve a given sudoku puzzle.Here are the specific details:-
We have defined a file format for Sudoku puzzles: A puzzle file consists of 9 lines,each of which contains 9 integer values separated by spaces. The integer values are notnecessarily in the range 1–9, and 0. A zero indicates an empty space in the puzzle. An example unsolved sudoku puzzle:-
0 3 2 0 0 8 9 1 4
0 0 0 0 0 0 0 0 3
0 0 7 1 0 0 0 2 6
0 0 8 0 7 6 0 0 0
9 2 1 3 0 0 0 8 7
0 6 0 0 0 0 4 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 4 0 5 0 8
8 0 0 6 0 7 0 0 0
The code must implement at least the following solution techniques:
• scanning and elimination
• singleton identification
The scanning and elimination is a means to generate a list of possible values for each cell. We first list (conceptually at least) all possible values 1–9 for an empty cell, and then scan that cell’s row (and column and minigrid) to eliminate from this list all values that already appear in that row (or column or minigrid). At the end of this process, the list of possible cell entries can be examined, and if the list for some cell has been reduced to a
single value, then this must be the value that belongs in that cell.
Singleton identification works by also considering the lists of possible values for each cell. We can then examine these lists for all empty cells in a row (or column or minigrid) to see if any value appears in only one of these lists. In this case, that single value must be the value for the cell where it appears. For example, suppose that a puzzle has the row 1 A 5 9 6 7 2 B C and we know that A can only be 3, 4 or 8, B can only be 3 or 4, and C can only be 3 or 4. Then cell A must be an 8, because 8 is a singleton: it appears only in the list of possibilities for cell A.
CAN SOMEONE PLEASE HELP ME WITH THIS?

http://www.codeguru.com/forum/showthread.php?t=366302

Regards,

Paul McKenzie

Quote:

---

CAN SOMEONE PLEASE HELP ME WITH THIS?

---

If by help you mean write the code for you, no we will not do that.

Have you even attempted this yourself? What code do you have so far?

These numbers are stored in a file, so why don't you try to read them from the file into some kind of data structure, like an array?

Ok, I will help the OP just a little bit. Have a look at my Matrix class in the FAQ - that will allow you to create a 9*9 matrix quite easily.

You might alternatively find that std::valarray fits this model very well. There are various methods to slice a valarray so, for example, you can obtain a slice that is a row or a column. You might even be able to slice your 3*3 block, and then you can have methods to examine a slice.

std::valarray will only allow certain types, although std::bitset might be the type to use, alternatively you could have some kind of union (but won't work with valarray) thus:

Code:

---

struct cell
{
  bool isResolved;
  union
  {
      int value;
      std::bitset<9> bits;
  };
};

---

You could alternatively just use your own custom bit-set as an int so you can use 9 bits for calculation and 4 to store the value when solved, so it would fit comfortable into a 16-bit integer.

You might want a temporary grid for working, for example, if you use trial and error to solve it. You can also add an "error" bit that is set if an impossible situation has occurred.

Go to www.sourceforge.net and search for "sudoku solver"
you will find a lot of applications (including sourcecode).
So you can check-out how other people solved this problem already.