1. We have moved from vBulletin to XenForo and you are viewing the site in the middle of the move. Though the functional aspect of everything is working fine, we are still working on other changes including the new design on Xenforo.
    Dismiss Notice

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