sudoku solved (finally)

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 :)

This is a 9x9 solved sudoku screen-shot

This is a 25x25 solved sudoku screen shot!!

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

5 thoughts on “sudoku solved (finally)

  1. 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 :-)

  2. 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.

  3. Pingback: Bug in sudoku solver « Talk to yourself

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s