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 );
}
