1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Sudoku C Program (16 by 16 matrix)

Discussion in 'C' started by kumarbharani5, Jan 21, 2008.

  1. kumarbharani5

    kumarbharani5 New Member

    Joined:
    Jan 21, 2008
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    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:

    Last edited by a moderator: Jan 22, 2008
  2. hvbilla

    hvbilla New Member

    Joined:
    Sep 22, 2011
    Messages:
    1
    Likes Received:
    0
    Trophy Points:
    0
    really it works
     

Share This Page