The New Sudoku Players' Forum

[wimcolgate]

Hi all, first and probably only post -- I was on a plane from LA to Seattle and found a "diabolical" sudoku in the LA paper someone left behind. Since I didn't solve it on the plane (sleep took over ;-)), I decided to write a program to solve it for me.

So I have included here a freeware C language recursive program for anywone who wants to play with it. Just don't take credit for it (like homework, or school project) because you didn't write it.

Regards,

Wim

-----------------------------------------------------------
/* freeware, simple recursive sudoku solver */
/* it will print all possible solutions */
/* inspired by a hard sudoku found in the */
/* #if 0 ... */

/* wim colgate, January, 11th, 2006 */

#define BASE(num) ((num/9)*9)
#define TOP(num) ((num%9))
#define ULEFT(num) (((BASE(num)/27)*27)+(((num-BASE(num))/3)*3))

typedef struct _sudoku {
unsigned char array[81];
} sudoku;

int solution_found = 0;

#if 0
sudoku original_board = {
0, 0, 7, 0, 6, 0, 0, 1, 0,
5, 0, 0, 2, 0, 0, 0, 8, 7,
9, 0, 0, 1, 0, 0, 0, 3, 0,

0, 0, 0, 3, 0, 0, 7, 4, 0,
0, 5, 0, 0, 0, 0, 0, 9, 0,
0, 9, 8, 0, 0, 2, 0, 0, 0,

0, 7, 0, 0, 0, 1, 0, 0, 9,
2, 1, 0, 0, 0, 8, 0, 0, 4,
0, 8, 0, 0, 5, 0, 3, 0, 0
};
#else
sudoku original_board = {
3, 0, 0, 0, 4, 9, 0, 0, 0,
0, 0, 0, 7, 0, 0, 0, 6, 0,
0, 7, 2, 0, 0, 0, 0, 8, 0,

5, 0, 0, 0, 8, 0, 0, 0, 2,
0, 0, 4, 5, 0, 3, 6, 0, 0,
6, 0, 0, 0, 2, 0, 0, 0, 3,

0, 9, 0, 0, 0, 0, 5, 3, 0,
0, 4, 0, 0, 0, 5, 0, 0, 0,
0, 0, 0, 4, 1, 0, 0, 0, 7
};
#endif

int place_next(int loc, sudoku *pboard)
{
while ((loc < 81) && (pboard->array[loc] != 0)) loc++;

if (loc <81) return loc;

return -1;
}

void print_solution(sudoku *pboard)
{
int i, j;

if (solution_found) printf("-------------------------------------\n\n");
for (i=0; i<9; i++) {
for (j=0; j<9; j++) {
if (j%3 == 0) printf(" ");
printf(" %d", pboard->array[i*9+j]);
}
if (i==2 || i == 5) printf("\n");
printf("\n");
}

printf("\n");
solution_found = 1;
}

int row_check(int loc, int val, sudoku *pboard)
{
int i = BASE(loc);
int j;

for (j=0; j<9; j++) {
if (pboard->array[i+j] == val) return 0;
}

return 1;
}

int column_check(int loc, int val, sudoku *pboard)
{
int i = TOP(loc);
int j;

for (j=0; j<9; j++) {
if (pboard->array[i+j*9] == val) return 0;
}

return 1;
}

int square_check(int loc, int val, sudoku *pboard)
{
int i = ULEFT(loc);
int j, k;

for (j=0; j<3; j++) {
for (k=0; k<3; k++) {
if (pboard->array[i+j*9+k] == val) return 0;
}
}

return 1;
}

int sudo(int loc, int num, sudoku board)
{
if (num > 9) return -1;

loc = place_next(loc, &board);

if (loc == -1) {
print_solution(&board);
return -1;
}

if (row_check(loc, num, &board) && column_check(loc, num, &board) && square_check(loc, num, &board)) {
board.array[loc] = num;
sudo(loc+1, 1, board);
board.array[loc] = 0;
sudo(loc, num+1, board);
} else {
sudo(loc, num+1, board);
}
}

main(int argc, char *argv[])
{
sudo(0, 1, original_board);

if (!solution_found) printf("no solution found\n");
}

[wimcolgate]

apologies to the formatting... for some reason the cut/paste looked OK, but the forum software seemed to left justify everything.

[wimcolgate]

Some minor improvements (brought out constants) so as to handle 16x16 sudoku's.

Wim
-------------------------------------

Code: Select all

/* freeware, simple recursive sudoku solver */
/* it will print all possible solutions     */
/* inspired by a hard sudoku found in the   */
/* else clause of the orginal_board         */

/* wim colgate, January, 11th, 2006         */
/* extended for large 16x16 January 15th    */

#if defined(LARGE)
#define ROW_SIZE 12
#else
#define ROW_SIZE 9
#endif

#define SQUARE_X   (ROW_SIZE/3)
#define SQUARE_Y   (3)
#define ARRAY_SIZE (ROW_SIZE*ROW_SIZE)

#define BASE(num)  (((num)/ROW_SIZE)*ROW_SIZE)
#define TOP(num)   (((num)%ROW_SIZE))
#define ULEFT(num) ((BASE(num)/(ROW_SIZE*SQUARE_Y)*(ROW_SIZE*SQUARE_Y))+((((num)-BASE(num))/SQUARE_X)*SQUARE_X))

typedef struct _sudoku {
    unsigned char array[ARRAY_SIZE];
} sudoku;

int solution_found = 0;

#if defined(LARGE)
sudoku original_board = {
   4,  0,  1,  0,  0xb,  2,  0,  0,  0xc,  0,  0,  0,
   0,  0,  0,0xb,    0,  7,  0,  0,    0,  0,  2,  8,
   0,  2,  0,  0,    0,  0,  0,0xa,    0,  0,  1,  0,
 
   7,  9,  0,  0,    3,  0,  1,  0,    6,  0,  4,  0,
 0xc,  0,  0,  0,    0,  0,  0,  0,    0,  3,  0,  0,
 0xb,  3,  0,  0,    0,  4,0xc,  0,    7,  2,  0,  0,

   0,  0,  2,  9,    0,0xb,  4,  0,    0,  0,  6,0xa,
   0,  0,  6,  0,    0,  0,  0,  0,    0,  0,  0,  3,
   0,  7,  0,  4,    0,  1,  0,  3,    0,  0,  8,  5,

   0,0xc,  0,  0,    9,  0,  0,  0,    0,  0,  3,  0,
   9,  4,  0,  0,    0,  0,  6,  0,    5,  0,  0,  0,
   0,  0,  0,0xa,    0,  0,  2,  4,    0,0xc,  0,  9,
};
#else
sudoku original_board = {
   0, 0, 7,    0, 6, 0,    0, 1, 0,
   5, 0, 0,    2, 0, 0,    0, 8, 7,
   9, 0, 0,    1, 0, 0,    0, 3, 0,

   0, 0, 0,    3, 0, 0,    7, 4, 0,
   0, 5, 0,    0, 0, 0,    0, 9, 0,
   0, 9, 8,    0, 0, 2,    0, 0, 0,

   0, 7, 0,    0, 0, 1,    0, 0, 9,
   2, 1, 0,    0, 0, 8,    0, 0, 4,
   0, 8, 0,    0, 5, 0,    3, 0, 0
};
#endif

int place_next(int loc, sudoku *pboard)
{
    while ((loc < ARRAY_SIZE) && (pboard->array[loc] != 0)) loc++;

    if (loc < ARRAY_SIZE) return loc;

    return -1;
}

void print_solution(sudoku *pboard)
{
    int i, j;

    if (solution_found) printf("-------------------------------------\n\n");
    for (i=0; i<ROW_SIZE; i++) {
        for (j=0; j<ROW_SIZE; j++) {
            if (j%SQUARE_X == 0) printf("  ");
            printf("  %X", pboard->array[i*ROW_SIZE+j]);
        }
        if ((i+1)%SQUARE_Y == 0) printf("\n");
        printf("\n");
    }

    printf("\n");
    solution_found = 1;
}

int row_check(int loc, int val, sudoku *pboard)
{
    int i = BASE(loc);
    int j;

    for (j=0; j<ROW_SIZE; j++) {
        if (pboard->array[i+j] == val) return 0;
    }

    return 1;
}

int column_check(int loc, int val, sudoku *pboard)
{
    int i = TOP(loc);
    int j;

    for (j=0; j<ROW_SIZE; j++) {
        if (pboard->array[i+j*ROW_SIZE] == val) return 0;
    }

    return 1;
}

int square_check(int loc, int val, sudoku *pboard)
{
    int i = ULEFT(loc);
    int j, k;

    for (j=0; j<SQUARE_Y; j++) {
        for (k=0; k<SQUARE_X; k++) {
            if (pboard->array[i+j*ROW_SIZE+k] == val) return 0;
        }
    }

    return 1;
}

int sudo(int loc, int num, sudoku board)
{
    if (num > ROW_SIZE) return -1;

    loc = place_next(loc, &board);

    if (loc == -1) {
        print_solution(&board);
        return -1;
    }

    if (row_check(loc, num, &board) && column_check(loc, num, &board) && square_check(loc, num, &board)) {
        board.array[loc] = num;
        sudo(loc+1, 1, board);
        board.array[loc] = 0;
        sudo(loc, num+1, board);
    } else {
        sudo(loc, num+1, board);
    }
}

main(int argc, char *argv[])
{
    sudo(0, 1, original_board);

    if (!solution_found) printf("no solution found\n");
}


[qwijibow]

I use a recursive function to solve sudoku problems. its lightning fast.
and then the 3rd parameter is set to true, it uses a random seed, and generates radnom end game state, which can then be used to set a puzzle.

Code: Select all


bool solvePuzzle(const state &S, state *result, bool random) {

   int x,y,n;
   
   char seq[] = {1,2,3,4,5,6,7,8,9};

   if(random) {
      shuffle(&seq[0],9,SMALL_SHUFFLE);
   }

   if(S.isComplete()) {
      if(result != 0) {
         *result = S;
      }
      return true;
   }

   for(y=0; y<9; y++) {
      for(x=0; x<9; x++) {
         for(n=0; n<9; n++) {
            if(S.legalMove(x,y, seq[n])) {
               if(solvePuzzle( state( S, x, y, seq[n]), result, random )) {

                  return true;
               }
            }
         }
         if(S.isEmpty(x,y)) { return false; }
      }
   }

   return false;
}


as you can see, the code is very very simple..

there are 3 nested for loops, looping every possable X,Ycoordinate, and the 3rd for loop, looping possable numbers to insert into that grid referance.

if the number can legally be placed into the X,Y, then that move is made, and the ffunction recurses.

when it finds an end game state, the solution is placed into the buffer at the second parameter.