Sunday, 30 November 2014

Sudoku Solver without recursion in C

Posted by Mahesh Doijade
Sudoku Solver without recursion; Sudoku Solver; Sudoku solving
 
  
     I am sure you know basics about the Sudoku problem, in case you don't this link will provide you with comprehensive details about it. The code posted below, is a non-recursive stack-based backtracking implementation of Sudoku Solving. The aim is to provide you a working solution for automated Sudoku Solving. All the backtracking based search for sudoku solving happens in the function sudokuSolver(sudoku_elem **grid)
    Also, some sample extremely difficult sudoku problems are provided in the commented lines below char *sudoku , you can use them for further testing. In case you intend to give any other sudoku problem it should be fed to the implementation in the similar format the way been currently given to char *sudoku .
    Due to iterative nature of the implementation it can work for any extreme problems involving all the kind of depths of the sudoku solving search tree. Along with this, it also has reasonable performance, almost all the tested the sudoku problem where crunched within few seconds. For any questions about the code below, please post your questions in the comments section, it will be a pleasure answering them.


Sudoku Solver without recursion


 #include <stdio.h>  
 #include <stdlib.h>  
 #include <assert.h>  
 #include <omp.h>  
   
 #define GRID_SIZE 9  
   
 struct sudoku_elem_t  
 {  
   int val;  
   int fixed;  
 };  
 typedef struct sudoku_elem_t sudoku_elem;  
   
 struct triedValue_t  
 {  
   int rowPos;  
   int colPos;  
   int value;  
 };  
 typedef struct triedValue_t triedValue;  
   
 struct allTriedValues_t  
 {  
   int count;  
   int size;  
   triedValue *allValues;  
 };  
 typedef struct allTriedValues_t allTriedValues;  
   
 sudoku_elem** allocInitSudoku()  
 {  
   sudoku_elem **grid;  
   grid = (sudoku_elem **) malloc(sizeof(sudoku_elem *)*GRID_SIZE);  
   if (grid == NULL)  
   {  
     return NULL; // Failed to allocate memory returning  
   }  
   int i, j;  
   for (i = 0; i < GRID_SIZE; i++)  
   {  
     grid[i] = (sudoku_elem *) calloc(9, sizeof(sudoku_elem));  
     if (grid[i] == NULL)  
     {  
       return NULL;  
     }  
     for (j=0; j < GRID_SIZE; j++)  
     {  
       grid[i][j].fixed = 0;  
       grid[i][j].val = 0;  
     }  
   }  
   return grid;  
 }  
   
 int initAllTriedValues(allTriedValues *a)  
 {  
   assert(a);  
   
   a->count = 0;  
   a->size = 30;  
   a->allValues = (triedValue *) malloc(sizeof(triedValue) * a->size);  
   if (a->allValues != NULL)  
   {  
     return 1;  
   }  
   return -1;  
 }  
   
 int insertIntoTriedValues(allTriedValues *a, int row, int col, int value)  
 {  
   assert(a);  
   
   if (a->count == a->size)  
   {  
     a->size *= 2;  
     a->allValues = realloc(a->allValues, sizeof(triedValue)*a->size);  
     if (a->allValues == NULL)  
     {  
       return -1; // Reallocation failed no memory  
     }  
   }  
   a->allValues[a->count].rowPos = row;  
   a->allValues[a->count].colPos = col;  
   a->allValues[a->count].value = value;  
   a->count++;  
   return 1;  
 }  
   
 /* Returns 1: if no duplicates found in the sudoku constraints */  
 int verifyRules(sudoku_elem** grid, int rowPos, int colPos, int valToCheck)  
 {  
   int i, j;  
   // Check if the given number exists in the row or the column  
   for (i = 0; i < GRID_SIZE; i++)  
   {  
     if (grid[rowPos][i].val == valToCheck)  
     {  
       return -1;  
     }  
     if (grid[i][colPos].val == valToCheck)  
     {  
       return -1;  
     }  
   }  
   
   // Check if the same number exists in the 3x3 tile of rowPos and colPos  
   int bound3x3TopLeft_x = (rowPos / 3) * 3;  
   int bound3x3TopLeft_y = (colPos / 3) * 3;  
   int bound3x3BottomRight_x = ((rowPos / 3) + 1) * 3;  
   int bound3x3BottomRight_y = ((colPos / 3) + 1) * 3;  
   
   for (i = bound3x3TopLeft_x; i < bound3x3BottomRight_x; i++)  
   {  
     for (j = bound3x3TopLeft_y; j < bound3x3BottomRight_y; j++)  
     {  
       if (grid[i][j].val == valToCheck)  
       {  
         return -1;  
       }  
     }  
   }  
   return 1;  
 }  
   
 int insertValuesInSudokuGrid(sudoku_elem **grid)  
 {  
   assert(grid);  
   int rowPos = 0;  
   int colPos = 0;  
   
   // Randomly select the row and column  
   while (1)  
   {  
     rowPos = rand() % 9;  
     colPos = rand() % 9;  
     if (grid[rowPos][colPos].val == 0)  
     {  
       break;  
     }  
   }  
   
   int i;  
   for (i = 1; i <=9; i++)  
   {  
     int retVal = verifyRules(grid, rowPos, colPos, i);  
     if (retVal == 1)  
     {  
       grid[rowPos][colPos].val = i;  
       grid[rowPos][colPos].fixed = 1;  
       return 1;  
     }  
   }  
   return 1;  
 }  
   
 int getUnfilledPosition(sudoku_elem **grid, int *row, int *col)  
 {  
   int i, j;  
   for (i = 0; i < 9; i++)  
   {  
     for (j = 0; j < 9; j++)  
     {  
       if (grid[i][j].val == 0 && grid[i][j].fixed != 1)  
       {  
         *row = i;  
         *col = j;  
         return 0;  
       }  
     }  
   }  
   return 1; // All the positions are filled appropriately  
 }  
   
 // All the magic happens here.  
 void sudokuSolver(sudoku_elem **grid)  
 {  
   assert(grid);  
   allTriedValues allValuesStack;  
   int ret = initAllTriedValues(&allValuesStack);  
   int row = 0, col = 0;  
   if (ret == -1)  
   {  
     printf("Failed to allocate memory returning\n");  
     return;  
   }  
   int temp_cnt = 0;  
   
   while (getUnfilledPosition(grid, &row, &col) == 0)  
   {  
     int startVal = 1;  
     for (startVal = 1; startVal <= 9; startVal++)  
     {  
       int retVal = verifyRules(grid, row, col, startVal);  
       if (retVal == 1)  
       {  
         grid[row][col].val = startVal;  
         insertIntoTriedValues(&allValuesStack, row, col, startVal);  
         break;  
       }  
     }  
     if (grid[row][col].val == 0)  
     {  
       int shouldBacktrack = 1;  
       int backtrack_level;  
       int backtrack_row = row;  
       int backtrack_col = col;  
       int temprow = row;  
       int tempcol = col;  
   
       while (grid[backtrack_row][backtrack_col].val == 0)  
       {  
         if (shouldBacktrack && (allValuesStack.count > 0))  
         {  
           allValuesStack.count--;  
           backtrack_level = allValuesStack.count;  
           temprow = allValuesStack.allValues[backtrack_level].rowPos;  
           tempcol = allValuesStack.allValues[backtrack_level].colPos;  
           int inc_val = grid[temprow][tempcol].val + 1;  
   
           grid[temprow][tempcol].val = 0;  
           for (inc_val = inc_val; inc_val <= 9; inc_val++)  
           {  
             int retVal = verifyRules(grid, temprow, tempcol, inc_val);  
             if (retVal == 1)  
             {  
               grid[temprow][tempcol].val = inc_val;  
               shouldBacktrack = 0;  
               insertIntoTriedValues(&allValuesStack, temprow, tempcol, inc_val);  
               break;  
             }  
           }  
           if (grid[temprow][tempcol].val == 0)  
           {  
             shouldBacktrack = 1;  
             continue;  
           }  
         }  
         int start_row, start_col;  
         if (tempcol == 8)  
         {  
           start_col = 0;  
           start_row = temprow + 1;  
         }  
         else  
         {  
           start_col = tempcol + 1;  
           start_row = temprow;  
         }  
         int backtrackPos = backtrack_row*9 + backtrack_col;  
         int startPos = start_row*9 + start_col;  
         if (startPos > backtrackPos)  
         {  
           shouldBacktrack = 1;  
           continue;  
         }  
         while (startPos <= backtrackPos)  
         {  
           start_row = startPos / 9;  
           start_col = startPos % 9;  
           if (grid[start_row][start_col].fixed == 0)  
           {  
             grid[start_row][start_col].val = 0;  
             for (startVal = 1; startVal <= 9; startVal++)  
             {  
               int retVal = verifyRules(grid, start_row, start_col, startVal);  
               if (retVal == 1)  
               {  
                 grid[start_row][start_col].val = startVal;  
                 insertIntoTriedValues(&allValuesStack, start_row, start_col, startVal);  
                 break;  
               }  
             }  
             if (grid[start_row][start_col].val == 0)  
             {  
               shouldBacktrack = 1;  
               break;  
             }  
             else  
             {  
               shouldBacktrack = 0;  
             }  
           }  
           startPos++;  
         }  
       }  
     }  
   }  
   free(allValuesStack.allValues);  
 }  
   
 void printSudokuGrid(sudoku_elem **grid)  
 {  
   int i, j;  
   for (i = 0; i < GRID_SIZE; i++)  
   {  
     printf("\n");  
     for (j = 0; j < GRID_SIZE; j++ )  
       printf("%d-%d ", grid[i][j].val, grid[i][j].fixed);  
   }  
 }  
   
 int isValidSudoku(sudoku_elem **grid)  
 {  
   int i, j;  
   for (i=0; i < GRID_SIZE; i++)  
   {  
     for (j=0; j < GRID_SIZE; j++)  
     {  
       if (grid[i][j].val != 0)  
       {  
         int temp = grid[i][j].val;  
         grid[i][j].val = 0;  
         int retval = verifyRules(grid, i, j, temp);  
         grid[i][j].val = temp;  
         if (retval == -1)  
         {  
           return 0;  
         }  
       }  
     }  
   }  
   
   return 1;  
 }  
   
 int main()  
 {  
   int i, j;  
   
   sudoku_elem **newGrid = allocInitSudoku();  
   //sudoku_elem newGrid[GRID_SIZE][GRID_SIZE];  
   char *sudoku = "........3..1..56...9..4..7......9.5.7.......8.5.4.2....8..2..9...35..1..6........";  
   // Some of the other extreme Sudoku puzzles, you can try this out.  
   //".2..5.7..4..1....68....3...2....8..3.4..2.5.....6...1...2.9.....9......57.4...9..";  
   // ".......12........3..23..4....18....5.6..7.8.......9.....85.....9...4.5..47...6...";  
   // "..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9";  
   
   for (i=0; i < GRID_SIZE; i++)  
   {  
     for (j=0; j < GRID_SIZE; j++)  
     {  
       if (sudoku[i*GRID_SIZE + j] != '.')  
       {  
         newGrid[i][j].fixed = 1;  
         newGrid[i][j].val = sudoku[i*GRID_SIZE + j] - '0';  
       }  
     }  
   }  
   
   int ret = isValidSudoku(newGrid);  
   if (ret == 0)  
   {  
     printf("Invalid sudoku exiting.....\n");  
     return;  
   }  
   printf("\n -0 ==> initially empty cell\n -1 ==> fixed cell, i.e., initially filled cell\n");  
   printSudokuGrid(newGrid);  
   
   double startime = omp_get_wtime();  
   sudokuSolver(newGrid);  
   double endtime = omp_get_wtime();  
   printf("\n\n Solved Sudoku ");  
   
   printSudokuGrid(newGrid);  
   printf("\n\nSolving time = %lf\n", endtime - startime);  
 }  
   
Read More