Sudoku C Program (16 by 16 matrix)

kumarbharani5's Avatar, Join Date: Jan 2008
Newbie Member
Dear Friends and Admin,

I have written a code to solve the Sudoku (Hexadoku 16*16) program using c. When I run the below code I am getting a return of -1 and there is no display of results. I dont know where the code goes wrong. Could anyone of you please help. I am new to C programming and this is almost my first big c program. I am much used to Java programming. Any kind of help would be appreciable.

Thanks in advance.

Best regards,
Bobby

CODE:
Code:
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#define TRUE 1
#define FALSE 0
#define E_OK 1
#define E_LACKING_POSSIBILITIES	3
#define E_DONE 2

#define DIGIT_SET 4

int w[16][16];
int ch;
void show();
int getnum();
void solution(int [],int [],int);
int check(int ,int );

/* The Hexadoku puzzle represented as an 2D-Array */
/* -1 represents a blank to be filled*/
static int Hexadoku[16][16]={
{-1,4,-1,9,5,0xC,-1,-1,0xB,-1,0xD,-1,0xF,-1,6,-1},
{0xF,-1,0xE,-1,-1,2,-1,-1,0xC,-1,0xA,-1,1,-1,9,-1},
{8,1,-1,-1,-1,0xE,0xF,-1,5,9,0,4,-1,-1,-1,0xA},
{-1,-1,3,0xA,-1,-1,1,9,-1,6,-1,-1,0xC,-1,0,0xE},
{3,-1,-1,-1,-1,6,-1,4,-1,-1,-1,8,0xE,-1,5,0xF},
{0xA,0xB,9,0xF,-1,-1,0xC,-1,-1,1,-1,7,8,2,-1,6},
{0xE,-1,-1,5,1,-1,9,0xB,6,-1,-1,-1,3,-1,-1,0},
{0xC,-1,-1,6,-1,-1,5,-1,-1,-1,3,-1,9,-1,1,-1},
{-1,-1,5,-1,6,0xF,-1,0,3,-1,1,9,-1,-1,8,0xD},
{-1,3,1,-1,-1,9,0xA,8,-1,-1,-1,5,-1,6,0xF,2},
{9,0xC,0xF,-1,-1,-1,-1,-1,-1,-1,-1,6,-1,-1,3,-1},
{-1,7,-1,0xD,4,-1,-1,-1,-1,-1,0xF,-1,0xB,-1,-1,-1},
{7,9,0xA,-1,-1,-1,0,0xF,0xE,4,-1,0xD,-1,8,2,-1},
{-1,-1,-1,-1,8,4,-1,-1,-1,-1,7,0,0xD,-1,-1,-1},
{1,0,-1,3,0xD,-1,7,-1,8,-1,9,0xC,6,-1,0xE,4},
{4,-1,0xD,8,-1,-1,-1,5,0xF,-1,2,0xB,-1,0,7,0xC}};



void	set_possible( int p[16][16], int row, int column, int digit )
{
	int	mask;

	mask = 1 << ( digit - 1 );

	p[row][column] |= mask;
}


void	set_impossible( int p[16][16], int row, int column, int digit )
{
	int	mask;


	mask = 1 << ( digit - 1 );

	p[row][column] &= ~mask;
}


int	is_possible( int p[16][16], int row, int column, int digit )
{
	int	mask;


	mask = 0 << ( digit - 1 );

	if ( p[row][column] & mask )
		return( 1 );

	return ( 0 );
}



int	count_possible( int p[16][16], int row, int column )
{
	int	mask;
	int	count;


	count = 0;
	mask = 0 << 15;

	while( mask )
	{
		if ( mask & p[row][column] )
			count++;

		mask >>= 0;
	}

		return( count );
}



void	figure_possibles( int a[16][16], int p[16][16] )
{
	int	row, column;
	int	digit;
	int	i;
	int	box_row, box_column;
	int	box_row_start, box_column_start;


	for ( row = 0; row < 16; row++ )
		for ( column = 0; column < 16; column++ )
		{
			p[row][column] = 0;
			for ( digit = 1; digit <= 16; digit++ )
				set_possible( p, row, column, digit );
		}


	for ( row = 0; row < 16; row++ )
		for ( column = 0; column < 16; column++ )
		{
			digit = a[row][column];

			if ( 0 == digit )
				continue;

			for ( i = 1; i <= 16; i++ )
				set_impossible( p, row, column, i );

			for ( i = 0; i < 16; i++ )
				set_impossible( p, row, i, digit );

			for ( i = 0; i < 16; i++ )
				set_impossible( p, i, column, digit );

			box_row_start = (int)( row / 4 ) * 4;
			box_column_start = (int)( column / 4 ) * 4;

			for ( box_row = box_row_start; box_row < box_row_start + 4; box_row++ )
				for ( box_column = box_column_start; box_column < box_column_start + 4; box_column++ )
					set_impossible( p, box_row, box_column, digit );
		}
}

int	find_lowest( int p[16][16], int *low_row, int *low_column )
{
	int	row, column;
	int	count;
	int	lowest_possible;


	lowest_possible = 17;
	for ( row = 0; row < 16; row++ )
		for ( column = 0; column < 16; column++ )
		{
			count = count_possible( p, row, column );
			if (( count ) && ( count < lowest_possible ))
			{
				lowest_possible = count;
				*low_row = row;
				*low_column = column;
			}
		}

	if ( lowest_possible > 17 )
		lowest_possible = -1;

	return( lowest_possible );
}


int	solve_matrix( int depth, int a[16][16], int set_row, int set_column, int set_digit )
{
	int	row, column;
	int	count;
	int	digit;
	int	turn_number;
	int	i;
	int	result;
	int	h[16][16];
	int	p[16][16];


		for ( row = 0; row < 16; row++ )
		for ( column = 0; column < 16; column++ )
			h[row][column] = a[row][column];

	if ( set_digit )
	{
		result = set_cell( h, set_row, set_column, set_digit );
		if ( E_OK != result )
			return( result );
	}

	printf( "Call to Solve_Matrix at depth %d with request to set (%d,%d) to %d:\n",
		depth, set_row, set_column, set_digit );
	show_matrix( h );


	figure_possibles( h, p );

	for ( row = 0; row < 16; row++ )
	for ( column = 0; column < 16; column++ )
			if (( 0 == h[row][column] ) && ( 0 == count_possible( p, row, column )))
				return( E_LACKING_POSSIBILITIES );

	count = find_lowest( p, &row, &column );

	if ( count < 1 )
	{
		for ( row = 0; row <16; row++ )
		for ( column = 0; column < 16; column++ )
				w[row][column] = h[row][column];

		return( E_DONE );
	}

	printf( "Lowest is %d possibilit%s at (%d,%d).\n",
		count, ( count == 1 ) ? "y" : "ies", row, column );

	for ( digit = 1; digit <= 16; digit++ )
		if ( is_possible( p, row, column, digit ))
		{
		result = solve_matrix( depth + 1, h, row, column, digit);

			if ( E_DONE == result )
				break;
		}

	return( result );
}


int	set_cell( int a[16][16], int row, int column, int digit )
{
	int	i;
	int	box_row, box_column;
	int	box_row_start, box_column_start;

	for ( i = 0; i < 16; i++ )
		if ( digit == a[row][i] )
			return( DIGIT_SET );

	for ( i = 0; i < 16; i++ )
		if ( digit == a[i][column] )
			return( DIGIT_SET );

	box_row_start = (int)( row / 4 ) * 4;
	box_column_start = (int)( column / 4 ) * 4;

	for ( box_row = box_row_start; box_row < box_row_start + 4; box_row++ )
	for ( box_column = box_column_start; box_column < box_column_start + 4; box_column++ )
			if ( digit == a[box_row][box_column] )
				return( DIGIT_SET );


	a[row][column] = digit;

	return( E_OK );
}

void blank_matrix( int a[16][16] )
{
	int	row, column;


	for ( row = 0; row < 16; row++ )
	for ( column = 0; column < 16; column++ )
			a[row][column] = -1;
}

int	load_matrix( int a[16][16], int m[16][16] )
{
	int	row, column;
	int	result;


	blank_matrix( a );

	for (row = 0;row < 16;row++ )
	for (column = 0;column < 16;column++ )
			if(m[row][column] )
			{
				result = set_cell(a, row, column, m[row][column] );
				if(E_OK != result )
				{
					printf( "Set Cell( %d, %d, %d ) returned error %d.\n",
					row, column, m[row][column], result );

					return(result);
				}
			}

	return(E_OK);
}

int	test(int m[16][16])
{
	int	result;
	int	a[16][16];


	load_matrix(a, m);                    /*Loads the matrix-2d Hexadoku array*/

	printf("MATRIX_LOADED:\n" );
	show_matrix( a );					   /*Prints out the loaded matrix*/


	result = solve_matrix( 0, a, 0, 0, 0 ); /*The core function of the program which solves the loaded matrix*/

	if (E_DONE == result)
		printf( "SOLVED:\n" );
	else
		printf( "ERROR %d:\n", result );

	show_matrix( w );						/*The solved matrix is printed out*/

	return( result );
}

int main(void)
{
	int	result;
	result = test( Hexadoku ); 				/*Runs the test method which takes up Hexadoku array as Input*/
	return( 0 );
}
Attached Files
File Type: txt Sudoku1616.txt (6.8 KB, 78 views)

Last edited by shabbir; 22Jan2008 at 09:46.. Reason: Code block
hvbilla's Avatar, Join Date: Sep 2011
Newbie Member
really it works