Go4Expert

Go4Expert (http://www.go4expert.com/)
-   C (http://www.go4expert.com/forums/c/)
-   -   Sudoku 16*16 matrix c Program (http://www.go4expert.com/forums/sudoku-1616-matrix-c-program-t8394/)

bobby2305 22Jan2008 13:33

Sudoku 16*16 matrix c Program
 
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 );
}


shabbir 22Jan2008 17:43

Re: Sudoku 16*16 matrix c Program
 
You already have the same thread once under different username : Sudoku C Program (16 by 16 matrix)


All times are GMT +5.5. The time now is 01:30.