My method does use backtracking, but only when the first two methods
fail. When the cell-based and group-based analysis do not produce any
results, it picks one cell and tries each possible value in that cell.
If that results in a contradiction, it backs out to that point and
tries something else.
I have implemented a Sudoku solver. C++ code follows.
Don
#include <stdio.h>
#include <ctype.h>
#include <conio.h>
#include <time.h>
// The contents of the 81 cells
int board[81];
// The rows, columns, and squares which must each
// contain a permutation of the digits 1-9
int groups[27][9] = {
{ 0, 1, 2, 3, 4, 5, 6, 7, 8},
{ 9,10,11,12,13,14,15,16,17},
{18,19,20,21,22,23,24,25,26},
{27,28,29,30,31,32,33,34,35},
{36,37,38,39,40,41,42,43,44},
{45,46,47,48,49,50,51,52,53},
{54,55,56,57,58,59,60,61,62},
{63,64,65,66,67,68,69,70,71},
{72,73,74,75,76,77,78,79,80},
{ 0, 9,18,27,36,45,54,63,72},
{ 1,10,19,28,37,46,55,64,73},
{ 2,11,20,29,38,47,56,65,74},
{ 3,12,21,30,39,48,57,66,75},
{ 4,13,22,31,40,49,58,67,76},
{ 5,14,23,32,41,50,59,68,77},
{ 6,15,24,33,42,51,60,69,78},
{ 7,16,25,34,43,52,61,70,79},
{ 8,17,26,35,44,53,62,71,80},
{ 0, 1, 2, 9,10,11,18,19,20},
{ 3, 4, 5,12,13,14,21,22,23},
{ 6, 7, 8,15,16,17,24,25,26},
{27,28,29,36,37,38,45,46,47},
{30,31,32,39,40,41,48,49,50},
{33,34,35,42,43,44,51,52,53},
{54,55,56,63,64,65,72,73,74},
{57,58,59,66,67,68,75,76,77},
{60,61,62,69,70,71,78,79,80}
};
// Maps each cell back into its three groups
int map[81][3];
int oneAvail[1023] = {0};
int bits[1023];
unsigned int avail[27];
int known = 0;
// History of moves used to back out wrong guesses
int rec[81];
// Set position to value "num"
void set(int pos, int num)
{
board[pos] = num;
if (num)
{
avail[map[pos][0]] ^= 1 << num;
avail[map[pos][1]] ^= 1 << num;
avail[map[pos][2]] ^= 1 << num;
rec[known++] = pos;
}
}
// Back out to position k
void backout(int k)
{
while(known > k)
{
int pos = rec[--known];
int num = board[pos];
avail[map[pos][0]] ^= 1 << num;
avail[map[pos][1]] ^= 1 << num;
avail[map[pos][2]] ^= 1 << num;
board[pos] = 0;
}
}
// Alternative method which evaluates each group to determine how many
// locations each missing digit could occupy. If there is only one
place
// it could go, it puts it there. Returns 1 unless a contradiction is
found.
int elimination()
{
int i,j,k;
for(i = 0; i < 27; ++i)
for(j = 1; j < 10; ++j)
if (avail[i] & (1<<j))
{
int pos = -1;
for(k = 0; k < 9; ++k)
if (board[groups[i][k]] == 0)
{
int p = groups[i][k];
unsigned int a =
avail[map[p][0]] & avail[map[p][1]] &
avail[map[p][2]];
if (a & (1<<j))
{
if (pos == -1) // Found
one place for digits
pos = p;
else // Digit could go
more than one place. This is not useful
yet.
{
pos = -2;
break;
}
}
}
if (pos > -1)
set(pos, j);
else if (pos == -1) // Contradiction: there is
a digit required
with no place to go
return 0;
}
return 1;
}
// Tries to solve the given puzzle. Returns 1 if solution is found.
int solve()
{
int i,j;
while(known < 81)
{
int priorKnown = known;
int leastPos;
int leastBits=9;
unsigned int leastA;
// Look for a cell which can have only one value
for(i = 0; i < 81; ++i)
if (board[i] == 0)
{
unsigned int a = avail[map[i][0]] &
avail[map[i][1]] & avail[map[i]
[2]];
if (!a) // There is a space where no digit
fits.
return 0;
if (oneAvail[a]) // Exactly one digit can go
here
set(i,oneAvail[a]);
else // Keep track of which cell has the
smallest possible number
of options
if (bits[a] < leastBits)
{
leastPos = i;
leastBits = bits[a];
leastA = a;
}
}
if ((known == priorKnown) && !elimination()) return 0;
if (known == priorKnown)
{
// Take a guess
for(j = 1; j < 10; ++j)
if (leastA & (1<<j))
{
set(leastPos, j);
if (solve()) return 1;
backout(priorKnown);
}
return 0;
}
}
return 1;
}
// Set up all the lookup tables
void init()
{
int i,j;
for(i = 0; i < 27; ++i)
for(j = 0; j < 9; ++j)
map[groups[i][j]][i/9] = i;
for(i = 1; i < 10; ++i)
oneAvail[1<<i] = i;
bits[0] = 0;
for(i = 1; i < 1023; ++i)
bits[i] = (i&1) + bits[i>>1];
for(i = 0; i < 27; ++i)
avail[i] = 1022;
known = 0;
}
// Read in the board from the user
void readBoard()
{
printf("Enter the given numbers and zeros for blanks\n");
for(int i = 0; i < 81; ++i)
{
char c=0;
while(!isdigit(c))
c = getch();
set(i,c-'0');
printf("%c", c);
if (i%9==8) printf("\n");
}
}
void printBoard()
{
printf("====================\n");
for(int i = 0; i < 81; ++i)
{
printf("%d", board[i]);
if (i % 9 == 8) printf("\n");
}
}
int main(int argc, char* argv[])
{
init();
readBoard();
if (!solve()) printf("No solutions found!\n");
else printBoard();
return 0;
}
On Oct 5, 12:46 am, abhishek sharma <[email protected]> wrote:
> Hi Don,
>
> How is your method better than backtracking?
>
> i hope you are implementing a sudoku solver..
>
> Let me know.
>
> Regds.
>
>
>
>
>
>
>
> On Tue, Oct 4, 2011 at 10:42 PM, Don <[email protected]> wrote:
> > When you say "Simulate" Sudoku, do you mean solve a given Sudoku
> > problem?
>
> > Here is an overview of how I did that:
>
> > I used an array of 81 integers to represent the board.
> > Then I built a 27x9 table of all the groups: 9 rows, 9 columns, and 9
> > squares.
> > Then I built a 81x3 map which relates each location on the board to
> > the 3 groups it belongs to.
> > I maintain an array of 27 integers called "avail" whose bits indicate
> > which values are still needed in that group.
>
> > Read in the given values and update avail accordingly.
>
> > Then repeatedly do the following until the problem is solved
> > For each empty cell
> > Compute the bitwise AND of the avail values for the 3 groups it
> > belongs to.
> > If the AND is zero, no value can go there. Return failure.
> > If exactly one value can go there, put it there and update the
> > avail values for the 3 groups
> > If the loop above did not fill in any cells, then do the following
> > Loop at each of the 27 groups
> > For each value missing in that group, count the locations
> > where it could go
> > If it could go in exactly one location, put it there
> > If it cannot go in any location, return failure.
> > If the neither method above filled in any cells, then do the
> > following:
> > Pick the empty cell with the fewest possible values
> > Try the possible values in that cell until you find one which
> > allows the puzzle to be completed
>
> > If the puzzle is solvable, this will solve it in a fraction of a
> > second.
>
> > Don
>
> > On Oct 4, 9:21 am, himanshu kansal <[email protected]>
> > wrote:
> > > can anybody give me the steps you need to check while writing a
> > > program to simulate sudoku....
>
> > > i don't want the exact code....just algorithm would me more than
> > > sufficient.....
>
> > > suggest also the suitable languages for implementing that......VB or
> > > java or any other????
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Nice Day
>
> Abhishek Sharma
> Bachelor of Technology
> IIT Kanpur (2009)
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
