Sudoku 16*16 matrix c Program

Discussion in 'C' started by bobby2305, Jan 22, 2008.

  1. bobby2305

    bobby2305 New Member

    Joined:
    Jan 22, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    Dear Readers and Administrator,

    I have written a code to solve 16*16 Sudoku and when I run the program it return me -3 rather than filling in the blanks. I dont know where the program goes wrong. I am new to C programming and this is my first big program which I have tried out. I am 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 );
    }
     
    Last edited by a moderator: Jan 22, 2008
  2. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,336
    Likes Received:
    377
    Trophy Points:
    83

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice