Cool!! here is the thing, pending in the todo list since long back. Having a sense of achievement :) Its no big deal but I felt I have coded something.

Here are the screenshots for 9×9 and 25×25 solutions :)

Here’s the sudoku solver code !! Grid is fixed at the moment, can be tested with any grid.

/* * Sudoku Solution Generator. A timepass activity. * Author - Vishal Thanki * Email - vishalthanki@gmail.com * Date - 23/04/2011 */ #include <stdio.h> #include <malloc.h> #include <string.h> #include <math.h> /* * Grid size which should be a perfect square, like 4x4, 9x9, 16x16 and so on */ #define GRID_SIZE 25 int glb_sqrt; /* The actual puzzle grid */ unsigned char matrix[GRID_SIZE][GRID_SIZE] = { {1,0,4,0,25, 0,19,0,0,10, 21,8,0,14,0, 6,12,9,0,0, 0,0,0,0,5}, {5,0,19,23,24, 0,22,12,0,0, 16,6,0,20,0, 18,0,25,14,13, 10,11,0,1,15}, {0,0,0,0,0, 0,21,5,0,20, 11,10,0,1,0, 4,8,24,23,15, 18,0,16,22,19}, {0,7,21,8,18, 0,0,0,11,0, 5,0,0,24,0, 0,0,17,22,1, 9,6,25,0,0}, {0,13,15,0,22, 14,0,18,0,16, 0,0,0,4,0, 0,0,19,0,0, 0,24,20,21,17}, {12,0,11,0,6, 0,0,0,0,15, 0,0,0,0,21, 25,19,0,4,0, 22,14,0,20,0}, {8,0,0,21,0, 16,0,0,0,2, 0,3,0,0,0, 0,17,23,18,22, 0,0,0,24,6}, {4,0,14,18,7, 9,0,22,21,19, 0,0,0,2,0, 5,0,0,0,6, 16,15,0,11,12}, {22,0,24,0,23, 0,0,11,0,7, 0,0,4,0,14, 0,2,12,0,8, 5,19,0,25,9}, {20,0,0,0,5, 0,0,0,0,17, 9,0,12,18,0, 1,0,0,7,24, 0,0,0,13,4}, {13,0,0,5,0, 2,23,14,4,18, 22,0,17,0,0, 20,0,1,9,21, 12,0,0,8,11}, {14,23,0,24,0, 0,0,0,0,0, 0,0,20,25,0, 3,4,13,0,11, 21,9,5,18,22}, {7,0,0,11,17, 20,24,0,0,0, 3,4,1,12,0, 0,6,14,0,5, 25,13,0,0,0}, {0,0,16,9,0, 17,11,7,10,25, 0,0,0,13,6, 0,0,18,0,0, 19,4,0,0,20}, {6,15,0,19,4, 13,0,0,5,0, 18,11,0,0,9, 8,22,16,25,10, 7,0,0,0,0}, {0,0,0,2,0, 0,10,19,3,0, 1,0,22,9,4, 11,15,0,20,0, 0,8,23,0,25}, {0,24,8,13,1, 0,0,4,20,0, 17,14,0,0,18, 0,16,22,5,0, 11,0,10,0,0}, {23,10,0,0,0, 0,0,0,18,0, 6,0,16,0,0, 17,1,0,13,0, 0,3,19,12,0}, {25,5,0,14,11, 0,17,0,8,24, 13,0,19,23,15,9,0,0,12,0, 20,0,22,0,7}, {0,0,17,4,0, 22,15,0,23,11, 12,25,0,0,0, 0,18,8,0,7, 0,0,14,0,13}, {19,6,23,22,8, 0,0,1,25,4, 14,2,0,3,7, 13,10,11,16,0, 0,0,0,0,0}, {0,4,0,17,0, 3,0,24,0,8, 20,23,11,10,25, 22,0,0,0,12, 13,2,18,6,0}, {0,0,7,16,0, 0,6,17,2,21, 0,18,0,0,0, 19,0,0,8,0, 0,0,0,4,0}, {18,9,25,1,2, 11,0,0,13,22, 4,0,21,0,5, 0,23,7,0,0, 15,0,3,0,8}, {0,21,10,0,0, 12,0,20,16,0, 19,0,0,0,0, 15,14,4,2,18, 23,25,11,7,0} }; /* A parallel grid (copy of actual grid) which is used during finding the solution */ unsigned char para_matrix[GRID_SIZE][GRID_SIZE]; /* * Bitmap logic: * * Here is hot it works. Each cell in a grid falls into 3 category: * 1. a row in which the cell is * 2. a column in which the cell is * 3. a cube in which the cell is (for example cube size is 3x3 in a 9x9 grid) * * So bitmap will be of 3*GRID_SIZE of array. Each element in bitmap array * is an integer (of size 32bits). This each element will represent entire row, * entire column and entire cube. In 9x9 grid, elements from 0-8 will represent * the bitmap for all row, elements from 9-17 will represent the columns bitmap, * and 18-27 will represent the bitmaps for cubes. Any value in a particular cell * will fall into all the three categories (row/column/cube) and hence will * require the update in bitmap. Bitmap will only set a particular bit, bit value * will the value of the cell. * * For example, if cell 3x4 has value 5. Then this cell will belong to row 3, * column 4, and cube 4 (starting from 0). So the bitmap index will be 3 for row, * (9+4) for column, and (18+4) for cube. Now in all these three elements of bitmap, * 5th bit will be set as the cell value is 5. * * These macros defined below are actually the index generator for * bitmap array from the "rows" and "columns" of puzzle grid. * Bitmap array actually holds an image of current grid, and * lets you know which element is currently set in the grid. * */ #define bi (i) #define bj (GRID_SIZE+j) #define bk (int)((GRID_SIZE*2)+(glb_sqrt*(i/glb_sqrt)+(j/glb_sqrt))) /* #define bk (int)((GRID_SIZE*2)+(5*(i/5)+(j/5))) */ /* * This function will verify solved grid. It will start with each element * in grid and update the bitmap step by step. As soon as it encounters an * element which is already present in bitmap, it will return error. * */ int verify() { int i, j, k; int bitmap[GRID_SIZE*3] = {0}; int bmp_idx; for (i = 0; i < GRID_SIZE; i++) { for (j = 0; j < GRID_SIZE; j++) { if ((((bitmap[bi] >> matrix[i][j]) & 0x1) == 0x0) && (((bitmap[bj] >> matrix[i][j]) & 0x1) == 0x0) && (((bitmap[bk] >> matrix[i][j]) & 0x1) == 0x0)) { bitmap[bi] |= 1 << matrix[i][j]; bitmap[bj] |= 1 << matrix[i][j]; bitmap[bk] |= 1 << matrix[i][j]; } else { printf("Sudoku Error: i = %d, j = %d\n", i, j); return -1; } } } return 0; } /* * This routine will find the possible values for a cell by * analyzing the bitmap, fill all the possible values in the * array (first arguemnt) along with the array size filled * in 0th element. */ void find_possible(unsigned char *arr, int i, int j, int *bmp) { int idx = 0; int iter; for (iter = 1; iter <= GRID_SIZE; iter++) { if (((bmp[bi] >> iter) & 0x1) || ((bmp[bj] >> iter) & 0x1) || ((bmp[bk] >> iter) & 0x1)) { continue; } else { idx++; arr[idx] = iter; } } arr[0] = idx; } /* * This routing will fill the bitmap first time * by analyzing the puzzle grid. */ void fill_bitmap(int *bmp) { int i, j; for (i = 0; i < GRID_SIZE; i++) { for (j = 0; j < GRID_SIZE; j++) { if (matrix[i][j]) { bmp[bi] |= 1 << matrix[i][j]; bmp[bj] |= 1 << matrix[i][j]; bmp[bk] |= 1 << matrix[i][j]; } } } } /* * Main solve routine. * * This is a recursive routine. Here the para_matrix is used as * a reference to identify that which element is actually to be * filled. It is used to increment the row and columns value for * all non-zero cells. * * Once a empty cell is found, it will try to find all the possible * values for that cell. It will fill the 1st possible value in the cell, * update the bitmap and and proceed for the next blank cell, * and again follow the same procedure. If there are no possible * values found for the next cell, the current value of cell is * removed, next possible value is taken and update the bitmap * accordingly. * * Repeating this procedure will eventually lead to the solution. * */ int solve(int *bmp, int i, int j) { unsigned char arr[GRID_SIZE+1], temp; int flag= 0; while (para_matrix[i][j] != 0) { j++; if (j % GRID_SIZE == 0) { i++; j = 0;} if (i == GRID_SIZE) return 0; } find_possible(arr, i, j, bmp); if (arr) { int len = arr[0]; int iter, ti, tj; if (len == 0) { return -1; } for (iter = 0; iter < len; iter++) { matrix[i][j] = arr[iter+1]; ti = i; tj = j; flag = 0; bmp[bi] |= 1 << arr[iter+1]; bmp[bj] |= 1 << arr[iter+1]; bmp[bk] |= 1 << arr[iter+1]; j++; if (j % GRID_SIZE == 0) { i++; j = 0; } if (i == GRID_SIZE) { return 0; } if (solve(bmp, i, j) == -1) { i = ti; j = tj; bmp[bi] ^= 1 << arr[iter+1]; bmp[bj] ^= 1 << arr[iter+1]; bmp[bk] ^= 1 << arr[iter+1]; flag = -1; } else return flag; } } return flag; } int main() { int bmp[GRID_SIZE*3] = {0}; int i = 0, j = 0; glb_sqrt = sqrt(GRID_SIZE); fill_bitmap(bmp); memcpy(para_matrix, matrix, sizeof(matrix)); if (solve(bmp, i, j) == 0) { for (i = 0; i < GRID_SIZE; i++) { for (j = 0; j < GRID_SIZE; j++) { printf("%2d ", matrix[i][j]); } printf("\n"); } } if (verify() == 0) { printf("Sudoku generated\n"); } else printf("FAiled\n"); return 0; }

Advertisements

“at tht time i realise that whatever GOD has given us is the best thing. never complain bout anything”—–if you really feel that….you are much more satisfied than i am. Good.

m sure u’ll feel the same thing some time….

I agree..

i agree man, that watever happens is for a good reason…or may b..

after sometime something good happens (may b..independent of the thing that could not happen right now) which v feel or try to feel that.. is beacuse of the thing that dint happen some time back..

but thats how it it…

i hope u get wat i wanna express :-)

it is true that everything happens for a reason ,,, but at least reason should be in our control otherwise there wont be any reason to live.

Pingback: Bug in sudoku solver « Talk to yourself