Thread: Sudoku search verification

Hi,

Before uploading my Sudoku solver, Please verify the code and write what you think of it:

Code:

// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ //

// sudoku search solver. version 1.0

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <stdbool.h>
#include <stdnoreturn.h>
#include <string.h>
#include <stdarg.h>
#include <stddef.h>
#include <time.h>

// TODO these settings could be changed:
//#define DEBUG // TODO activate for stdout printing, no impact on output file
const static double RUN_TIME = 30.0;// roughly runs for this time, in seconds

const static char SI[]="sudoku_input.text";
const static char SO[]="sudoku_output.text";

const static char input_sep='/';
const static char output_sep='$';
#define LINE_LEN 126
#define N_MAX 1000 // Number of tries for each sudoku puzzle
#define PRE_ALLOC 100


#define BUFF_SIZE 256
#define INFO_BUFF_SIZE 64
#define fatal_err(...) \
    do { \
        char buff[BUFF_SIZE]; \
        fprintf(stderr,"\n"); \
        fprintf(stderr, "FILE:%s\n", __FILE__); \
        fprintf(stderr, "FUNCTION:%s\n", __FUNCTION__); \
        fprintf(stderr,"LINE:%d\n",__LINE__); \
        snprintf(buff, sizeof(buff),__VA_ARGS__); \
        fatal_err_callee(buff); \
    } while (0)

#ifdef DEBUG
#define print_info(...) \
    do { \
        char info_buff[INFO_BUFF_SIZE]={'\0'}; \
        snprintf(info_buff, sizeof(info_buff), __VA_ARGS__); \
        print_info_callee(info_buff); \
    } while(0)

#else
#define print_info(...) \
    { \
        \
    } while(0);
#endif // DEBUG


const static uint16_t MAX_HASH=9*9;


enum SINGLE_VALUE // values of cells
{
    ONE=1,
    // ...
    NINE=1<<8

};

struct sudoku_state
{
    uint16_t min_hash;
    uint16_t hash; // sum of cells with 0 contradiction
    uint16_t cell[9][9];
    bool cell_isv[9][9]; // cell is single valued

    uint8_t contradiction[9][9];

    // Padding

};

uint16_t all_possible_in_cell(void);
uint16_t compute_hash(struct sudoku_state);

bool is_single_value(uint16_t );
bool sudoku_states_equal(struct sudoku_state, struct sudoku_state);
bool sudoku_is_solved_hashwise(struct sudoku_state);
bool sudoku_is_solved_cellwise(struct sudoku_state ss);

void init_isv(struct sudoku_state * const ss_ptr);

struct sudoku_state get_ss(void);

void fprint_ss(FILE *of, struct sudoku_state ss);
unsigned count_zero_bits_on_right(uint32_t);

bool ro_co_re(uint8_t,uint8_t,uint8_t,uint8_t);
bool in_region(uint8_t,uint8_t,uint8_t,uint8_t );
bool in_range(uint8_t v,uint8_t min, uint8_t max);

noreturn void solve(void);
bool is_unsolvable (struct sudoku_state);
uint16_t eliminate_single_value(uint16_t,uint16_t);

void implement_constraints(struct sudoku_state *);

void after_imp_con(struct sudoku_state * const ss_ptr);

void compute_contradictions(struct sudoku_state *);

static struct sudoku_state * fill_cells(struct sudoku_state *, size_t,bool);

uint16_t next_cell(uint16_t cell);
uint8_t try_next(uint16_t cell);

void update(struct sudoku_state * const,struct sudoku_state * const);

void previous_cell(int *const row, int *const column);
bool has_contra (struct sudoku_state ss);
bool def_no_solution(struct sudoku_state ss);

noreturn void fatal_err_callee(const char * const); // help from comp.lang.c
void print_info_callee(const char * const s);

void *my_alloc(size_t );

uint8_t popcnt(uint32_t v);
void first_uneq_cell
(const struct sudoku_state current_ptr,const struct sudoku_state end_ptr,int *const row,int *const column);

bool is_repeated
(struct sudoku_state *const root_ptr,struct sudoku_state *const end_ptr);

void print_finish(void);

void print_cell_callee(const char* const cell_name,uint16_t cell);
#define print_cell(var_name) print_cell_callee(#var_name,var_name)


int main(void)
{
    solve();

    return EXIT_SUCCESS;
}

noreturn void solve(void)
{
    time_t time_beg;
    time(&time_beg);

    struct sudoku_state ss;
    struct sudoku_state ss2;

    static struct sudoku_state *root_ptr;
    static struct sudoku_state *end_ptr;
    size_t n=1;
    size_t n2=0;
    int row=0;
    int column=0;

    static long pos=0;// file positioning

    FILE* of=fopen(SO, "wt");
    if(of==NULL)
        fatal_err("Initially can not open output file.");
    fprintf(of, "%c\n", output_sep);
    fclose(of);

    FILE* sif=NULL;
    do
    {
        time_t time_end;
        time(&time_end);
        double dt = difftime( time_end, time_beg );
        if(dt >= RUN_TIME)
            fatal_err("time is over, time passed %f seconds",dt);


        of=fopen(SO, "at");
        if(of==NULL)
            fatal_err("Can not open output file.");

        sif=fopen(SI, "rt");
        fseek(sif, pos * (long)sizeof(char), SEEK_SET);
        if(feof(sif) )
        {
            print_finish();
        }

        static long pre_pos7;
        pre_pos7=pos;
        fseek(sif, pos * (long)sizeof(char), SEEK_SET);
        pos=ftell(sif);

        root_ptr=my_alloc(PRE_ALLOC*sizeof (struct sudoku_state) );
        if(root_ptr==NULL)
            fatal_err("root_ptr malloc failed.");
        end_ptr=root_ptr+1;

        ss=get_ss();

        if(is_unsolvable(ss))
            fatal_err("Problem is unsolvable initially.");
        if(has_contra(ss))
            fatal_err("Problem has contradiction initially.");

        implement_constraints(&ss);
        ss2=ss;

        after_imp_con(&ss2);

        compute_contradictions(&ss2);

        if(is_unsolvable(ss2))
            fatal_err("Problem is unsolvable after implementing constraints.");

        *root_ptr=ss2;

        print_info("// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ //\n");
        if(sudoku_is_solved_cellwise(ss2))
        {
            printf("Problem is solved after implementing constraints.\n");

            fprint_ss(stdout, ss2);

            continue;
        }

        root_ptr=realloc(root_ptr,(n+PRE_ALLOC)*sizeof (struct sudoku_state)); // 0..n-1
        if(root_ptr==NULL)
            fatal_err("realloc of root_ptr failed.");

        end_ptr=fill_cells(root_ptr,n,false);
        if(end_ptr==NULL)
        {
            *root_ptr=get_ss();
            ss2=*root_ptr;
            ss=ss2;
            fprintf(of, "end_ptr is NULL:\n");
            fprint_ss(of, ss2);
            continue;
        }

        if(end_ptr->hash==MAX_HASH)
            printf("Filled all cells,row is %d column is %d n is %zu\n",row,column,n);

        if(sudoku_is_solved_cellwise(*end_ptr))
        {
            printf("Problem is solved after filling.\n");

            continue;
        }
        print_info("// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ //\n");

        print_info("row is %d, column is %d, n is %zu n2 is %zu\n"
                   ,row,column,n,n2);
        row=0;
        column=0;
        print_info("// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ //\n");

        after_imp_con(&ss2);
        compute_contradictions(end_ptr);

        fprint_ss(stdout, *end_ptr);

        if(root_ptr!=NULL)
            free(root_ptr);
        if(end_ptr!=NULL)
            free(end_ptr);

        fclose(sif);
        fclose(of);
    }
    while(true);
}

uint16_t next_cell(uint16_t cell)
{
    uint8_t next=try_next(cell);
    uint16_t first_cell=(uint16_t)(1<<(next-1));

    if(!is_single_value(first_cell))
        fatal_err("first_cell is %u",first_cell);

    print_info("^ %s:cell is %u first_cell is %u\n"
               ,__FUNCTION__,cell,first_cell);

    return first_cell;
}

uint8_t try_next(uint16_t cell) // TODO order can be random rather than 1..9
{
    unsigned count;
    uint8_t next=0;

    if(cell==0)
        fatal_err("Initial cell is %u",cell);

    count=count_zero_bits_on_right(cell);

    next=(uint8_t)(count+1);

    if(!(next>=1 && next<=9))
        fatal_err("Invalid next %u",next);

    return next;
}

static struct sudoku_state * fill_cells
( struct sudoku_state * root_ptr, size_t n,bool pre_contra)
{
    uint16_t root_cell=0;
    uint16_t end_cell=0;

    int row=0;
    int column=0;
    static struct sudoku_state * end_ptr;
    bool contra=false;
    static struct sudoku_state  *current_ptr;

    if(root_ptr==NULL)
        fatal_err("wrong pointer.");


    root_ptr=realloc(root_ptr,(n+PRE_ALLOC)*sizeof (struct sudoku_state)); // 100

    if(root_ptr==NULL)
        fatal_err("root_ptr realloc failed. n is %zu",n);

    if(n>=N_MAX || n==0)
        fatal_err("n is %zu",n);

    print_info("\n--------------------------------\n");
    print_info("$$ Beggining %s function.\n",__FUNCTION__);

    end_ptr=root_ptr+n;
    struct sudoku_state * last_ptr=(end_ptr+1);
    last_ptr=NULL;
    last_ptr++;
    last_ptr=NULL;

    struct sudoku_state * curr1_ptr;
    for(curr1_ptr=end_ptr-1; curr1_ptr>root_ptr; curr1_ptr--)
    {
        if(!def_no_solution(*curr1_ptr))
        {
            implement_constraints((curr1_ptr));
            *(end_ptr)=*(curr1_ptr);

            if(!def_no_solution(*end_ptr))
                break;
        }

    }

    ptrdiff_t diff1=end_ptr-curr1_ptr;
    print_info("$ end_ptr-curr1_ptr (ptrdiff) is %td\n",diff1);

    implement_constraints((curr1_ptr));
    *(end_ptr)=*(curr1_ptr);

    after_imp_con(end_ptr);

    compute_contradictions(end_ptr);

    end_ptr->min_hash=root_ptr->hash;

    end_ptr->hash=compute_hash(*end_ptr);

    if(sudoku_is_solved_cellwise(*end_ptr))
    {
        print_info("Problem is solved, n is %zu\n",n);

        fprint_ss(stdout, *end_ptr);

        FILE* of=fopen(SO, "at");
        fprint_ss(of, *end_ptr);
        fprintf(of, "%c\n", output_sep);

        fclose(of);

        return NULL;
    }

    contra=has_contra(*end_ptr);

    char pc_str[10]= {'\0'};
    char c_str[10]= {'\0'};
    pre_contra==true ? (strncpy(pc_str,"true",8)):(strncpy(pc_str,"false",8));
    contra==true ? (strncpy(c_str,"true",8)):(strncpy(c_str,"false",8));
    print_info("$ pre_contra is %s, contra is %s \n",pc_str,c_str);

    row=0;
    column=0;

    current_ptr=curr1_ptr;

    ptrdiff_t diff=end_ptr-current_ptr;

    print_info("$ end_ptr-current_ptr (ptrdiff) is %td\n",diff);

    print_info("$ n is %zu\n",n);

    row=0;
    column=0;
    root_cell=root_ptr->cell[row][column];
    end_cell=end_ptr->cell[row][column];

    update(root_ptr,current_ptr);
    fprint_ss(stdout, *(current_ptr));

    first_uneq_cell(*current_ptr,*end_ptr,&row,&column);

    print_info("`` first_uneq_cell, row is %d column is %d\n",row,column);
    uint16_t cc1=all_possible_in_cell();
    uint16_t ec1=all_possible_in_cell();
    if(!(row==8 && column==8))
    {
        print_info("$ row is %d, column is %d\n",row,column);
        cc1=current_ptr->cell[row][column];
        ec1=end_ptr->cell[row][column];
        print_cell(cc1);
        print_cell(ec1);

        row=0;
        column=0;
    }

    bool moving_forward= true;

    if(is_single_value(cc1)&&is_single_value(ec1)&& ec1<cc1)
    {
        print_info("$ moving_forward is false\n");

        moving_forward=false;
    }

    if(!moving_forward)
        fatal_err("!moving_forward");

    if(moving_forward)
    {
        print_info("` Moving forward.\n");

        uint16_t current_cell;

        column=0;
        for(row=0; row<=8; row++)
        {
            current_cell=current_ptr->cell[row][column];
            if(!is_single_value(current_cell))
                break;
            for(column=0; column<=8; column++)
            {

                current_cell=current_ptr->cell[row][column];
                if(!is_single_value(current_cell))
                {
                    if(current_cell==0)
                        fatal_err("` current_cell is 0, row is %d, column is %d\n",row,column);

                    print_info("` contra is false, row is %d, column is %d \n",row,column);
                    print_cell(current_cell);

                    break;
                }
            }

            if(column>8)
            {
                column=0;

                continue;
            }

            current_cell=current_ptr->cell[row][column];
            if(!is_single_value(current_cell))
                break;
        }

        if(row>8)
        {
            row=8;
            column=8;
        }
        root_cell=root_ptr->cell[row][column];
        current_cell=current_ptr->cell[row][column];

        print_info("` row is %d, column is %d\n",row,column);

        print_cell(root_cell);
        print_cell(current_cell);

        uint16_t cell=current_ptr->cell[row][column];

        print_cell(cell);

        print_cell(end_cell);

        uint16_t n_cell=next_cell(cell);
        uint16_t esv_cell=eliminate_single_value(n_cell,cell);

        print_cell(n_cell);
        print_cell(esv_cell);

        struct sudoku_state epbu = *end_ptr;
        *end_ptr=*current_ptr;
        end_ptr->cell[row][column]=n_cell;

        init_isv(end_ptr);

        update(root_ptr,end_ptr);

        bool ir=is_repeated(root_ptr,end_ptr);

        uint8_t pc=popcnt(n_cell);
        if(ir)
            print_info("`` ir is true, pc is %u\n",pc);

        bool pwr = ir && (pc>1);
        if( pwr ) // forward backward
        {
            print_info("``previous was repeated.\n");

            esv_cell=eliminate_single_value(n_cell,esv_cell);
            n_cell=next_cell(esv_cell);

            print_cell(n_cell);
            print_cell(esv_cell);

        }
        else
        {
            *end_ptr=epbu;
            end_ptr->cell[row][column]=n_cell;

            init_isv(end_ptr);

            update(root_ptr,end_ptr);
        }


        end_ptr->cell[row][column]=n_cell;

        update(root_ptr,end_ptr);

        print_info("`` contra is false, row is %d, column is %d \n",row,column);
        print_cell(cell);

        if(cell==0)
            fatal_err("cell is %u",cell);

        init_isv(current_ptr);

        current_ptr->cell[row][column]=esv_cell;

        update(root_ptr,current_ptr);

        print_cell(esv_cell);
        if(n<=20)
        {
            print_info("\n$$$ end_ptr begin.");

            fprint_ss(stdout, *end_ptr);
            if(n==3)
                print_cell(end_ptr->cell[0][2]);
            print_info("$$$ end_ptr end.\n");
        }


        bool hce=has_contra(*end_ptr);

        fill_cells(root_ptr,n+1,hce);
    }

    return end_ptr;
}

void init_isv(struct sudoku_state * const ss_ptr)
{
    unsigned row;
    unsigned column;

    ss_ptr->min_hash=0;
    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)

            ss_ptr->cell_isv[row][column]=false;

    return;
}


void after_imp_con(struct sudoku_state *const ss_ptr) // after implement constraints
{
    unsigned row;
    unsigned column;

    uint16_t hash=0;

    init_isv(ss_ptr);
    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
            if(is_single_value(ss_ptr->cell[row][column]))
                ss_ptr->cell_isv[row][column]=true;

    hash=compute_hash(........_ptr);

    ss_ptr->hash=hash;

    return ;

}

uint16_t all_possible_in_cell(void)
{
    uint16_t r=0;
    enum SINGLE_VALUE sv;
    for(sv=ONE; sv<=NINE; sv<<=1)
        r |= sv;

    return r;
}

uint16_t compute_hash(struct sudoku_state ss)
{
    uint16_t hash=0;

    unsigned row;
    unsigned column;

    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
            if(ss.cell_isv[row][column])
            {
                hash++;

            }


    if(hash<ss.min_hash || hash>MAX_HASH)
    {
        fatal_err("wrong hash in compute_hash, hash is %u",hash);
    }

    return hash;
}

unsigned count_zero_bits_on_right(uint32_t v)
{
    // https://graphics.stanford.edu/~seander/bithacks.html#ZerosOnRightBinSearch
    unsigned c;

    if(v==0)
        fatal_err("failed, v is %u",v);

    if (v & 0x1)
    {
        c = 0;
    }
    else
    {
        c = 1;
        if ((v & 0xffff) == 0)
        {
            v >>= 16;
            c += 16;
        }
        if ((v & 0xff) == 0)
        {
            v >>= 8;
            c += 8;
        }
        if ((v & 0xf) == 0)
        {
            v >>= 4;
            c += 4;
        }
        if ((v & 0x3) == 0)
        {
            v >>= 2;
            c += 2;
        }
        c -= v & 0x1;
    }
    if(c>=9)
        fatal_err("Count zero bits failed, c is %u\n",c);

    return c;
}


bool is_single_value(uint16_t value)
{
    bool b=false;
    enum SINGLE_VALUE sv;

    for(sv=ONE; sv<=NINE; sv<<=1)
        if(value == sv)
            b=true;

    return b;

}

bool sudoku_states_equal(struct sudoku_state ss1, struct sudoku_state ss2)
{
    unsigned row;
    unsigned column;
    bool r=true;
    uint16_t ss1_rc;
    uint16_t ss2_rc;

    if(ss1.hash != ss2.hash)
        r=false;

    if(r==true)
    {
        for(row=0; row<=8; row++)
            for(column=0; column<=8; column++)
            {
                ss1_rc=ss1.cell[row][column];
                ss2_rc=ss2.cell[row][column];

                if(ss1_rc!=ss2_rc)
                    r=false;
            }
    }


    if(r==true && (ss1.hash!=ss2.hash) )
        fatal_err("sudoku states are equal, but hashes are not.");

    return r;
}

bool sudoku_is_solved_hashwise(struct sudoku_state ss)
{
    bool r=false;
    if(ss.hash == MAX_HASH)
        r=true;

    return r;
}

bool sudoku_is_solved_cellwise(struct sudoku_state ss)
{
    unsigned row;
    unsigned column;
    bool r=true;
    uint8_t contradiction;
    bool isv;

    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
        {
            contradiction=ss.contradiction[row][column];
            isv=is_single_value(ss.cell[row][column]);

            if(contradiction!=0 || !isv)
                r=false;
        }


    return r;
}


uint16_t eliminate_single_value(uint16_t remove_this,uint16_t original)
{
    uint16_t sc3= original&(~remove_this);
    return sc3;
}

// TODO this function could be called several times untill hash stayes the same
void implement_constraints(struct sudoku_state * const ss_ptr)
{
    uint8_t row;
    uint8_t column;
    uint8_t row2;
    uint8_t column2;
    uint16_t sc1=all_possible_in_cell();
    uint16_t sc2=all_possible_in_cell();
    uint16_t hash=0;

    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
            for(row2=0; row2<=8; row2++)
                for(column2=0; column2<=8; column2++)
                {
                    if(row==row2 && column==column2)
                        continue;
                    if(ro_co_re(row,column,row2,column2))
                    {
                        sc1=ss_ptr->cell[row][column];
                        sc2=ss_ptr->cell[row2][column2];
                        if(is_single_value(sc1) && !is_single_value(sc2) )
                            sc2=eliminate_single_value(sc1,sc2);

                        if(!is_single_value(sc1) && is_single_value(sc2) )
                            sc1=eliminate_single_value(sc2,sc1);
                        ss_ptr->cell[row][column]=sc1;
                        ss_ptr->cell[row2][column2]=sc2;
                    }
                }



    hash=compute_hash(........_ptr);

    if(hash<ss_ptr->min_hash || hash>MAX_HASH)
        fatal_err("wrong hash, hash is %u",hash);
    ss_ptr->hash=hash;

    compute_contradictions(ss_ptr);

    return;
}

void compute_contradictions(struct sudoku_state ........)
{
    uint8_t row;
    uint8_t column;
    uint8_t row2;
    uint8_t column2;
    bool rcr=false;
    uint16_t cell_1;
    uint16_t cell_2;
    bool cell_1_isv;
    bool cell_2_isv;

    if(ss==NULL)
        fatal_err("wrong pointer.");

    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
            ss->contradiction[row][column]=0;

    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
            for(row2=0; row2<=8; row2++)
                for(column2=0; column2<=8; column2++)
                {
                    if(row==row2 && column==column2)
                        continue;
                    rcr=ro_co_re(row,column,row2,column2);
                    cell_1=ss->cell[row][column];
                    cell_2=ss->cell[row2][column2];
                    cell_1_isv = is_single_value(cell_1);
                    cell_2_isv=is_single_value(cell_2);
                    if( (rcr || row==row2||column==column2)&& cell_1==cell_2 && cell_1_isv &&cell_2_isv)
                    {
                        ss->contradiction[row][column]++;

                    }




                }
    return;
}

bool ro_co_re(uint8_t ro1,uint8_t co1,uint8_t ro2,uint8_t co2) // row column region
{
    bool r=false;

    if(ro1==ro2 || co1==co2)
        r=true;

    if(in_region(ro1,co1,ro2,co2))
        r=true;

    return r;
}

bool in_region(uint8_t ro1,uint8_t co1,uint8_t ro2,uint8_t co2)
{
    bool r=false;

    if(in_range(ro1,0,2) && in_range(co1,0,2) && in_range(ro2,0,2) && in_range(co2,0,2))
        r=true;
    if(in_range(ro1,0,2) && in_range(co1,3,5) && in_range(ro2,0,2) && in_range(co2,3,5))
        r=true;
    if(in_range(ro1,0,2) && in_range(co1,6,8) && in_range(ro2,0,2) && in_range(co2,6,8))
        r=true;
    if(in_range(ro1,3,5) && in_range(co1,0,2) && in_range(ro2,3,5) && in_range(co2,0,2))
        r=true;
    if(in_range(ro1,3,5) && in_range(co1,3,5) && in_range(ro2,3,5) && in_range(co2,3,5))
        r=true;
    if(in_range(ro1,3,5) && in_range(co1,6,8) && in_range(ro2,3,5) && in_range(co2,6,8))
        r=true;
    if(in_range(ro1,6,8) && in_range(co1,0,2) && in_range(ro2,6,8) && in_range(co2,0,2))
        r=true;
    if(in_range(ro1,6,8) && in_range(co1,3,5) && in_range(ro2,6,8) && in_range(co2,3,5))
        r=true;
    if(in_range(ro1,6,8) && in_range(co1,6,8) && in_range(ro2,6,8) && in_range(co2,6,8))
        r=true;

    return r;
}

bool in_range(uint8_t v,uint8_t min, uint8_t max )
{
    bool r=false;

    if(v>=min && v<=max)
        r=true;

    return r;
}

bool is_unsolvable (struct sudoku_state ss)
{
    uint8_t row;
    uint8_t column;
    bool r=false;
    uint16_t cell=0;
    uint16_t apic=all_possible_in_cell();

    for(row=0; row<=8; row++)
    {
        for(column=0; column<=8; column++)
        {
            cell=ss.cell[row][column];
            apic=all_possible_in_cell();
            if(cell==0 || cell>apic)
                r=true;
        }
        if(column>8)
            column=8;
        cell=ss.cell[row][column];
        apic=all_possible_in_cell();
        if(cell==0 || cell>apic)
            r=true;
    }


    return r;
}

bool has_contra (struct sudoku_state ss)
{
    uint8_t row=0;
    uint8_t column=0;
    bool r=false;

    for(row=0; row<=8; row++)
        for(column=0; column<=8; column++)
            if(ss.contradiction[row][column]!=0)
            {
                //r=true;
                print_info("$$ $ %s: row is %u column is %u\n ",__FUNCTION__,row,column);
                print_info("$$ $$ ");
                print_cell(ss.cell[row][column]);
                return true;
            }

    return r;
}

bool def_no_solution(struct sudoku_state ss)
{
    bool r;
    r= is_unsolvable(ss) || has_contra(ss);
    return r;
}


void update(struct sudoku_state * const root_ptr,struct sudoku_state * const ss_ptr)
{

    if(root_ptr==NULL || ss_ptr==NULL )
        fatal_err("wrong pointer.");

    implement_constraints((ss_ptr));

    after_imp_con(ss_ptr);
    compute_contradictions(ss_ptr);

    ss_ptr->min_hash=root_ptr->hash;

    ss_ptr->hash=compute_hash(........_ptr);

    return;

}

void previous_cell(int *const row, int *const column)
{
    if(row==NULL || column==NULL)
        fatal_err("wrong pointer.");

    if(*row==0 && *column==0)
        fatal_err("Can not step back any further.");

    if(*column==0)
    {
        (*row)--;
        *column=8;

    }
    else
        (*column)--;

    return;
}


struct sudoku_state get_ss(void)
{
    unsigned row=0;
    unsigned column=0;

    struct sudoku_state ss1
        = {.min_hash=0,.hash=0,.cell={{0}},.cell_isv={{false}},.contradiction={{0}} };
    FILE *f_input = NULL;
    char line[LINE_LEN]= {'\n','\0'};
    char ch='0';// int for EOF

    uint16_t apic=0;
    uint16_t hash=0;
    struct sudoku_state ........_ptr=&ss1;

    static long pos=0;

    if(ss_ptr==NULL)
        fatal_err("wrong pointer.");

    f_input=fopen(SI,"rt");
    if(f_input==NULL)
        fatal_err("Opening input file failed.");

    if(pos==EOF)
        fatal_err("wrong pos, pos is EOF");

    if(pos==EOF)
        fatal_err("pos failed.");

    fseek(f_input, pos * (long)sizeof(char), SEEK_SET);

    print_info("``` up_pos is %ld, current_ch is %c\n",pos,getc(f_input));

    do
    {

        fscanf(f_input,"%125s\n", line);
        if(feof(f_input) )
        {
            print_finish();
        }

    }
    while(strchr(line,input_sep)!=NULL);

    int oc=ungetc(line[0],f_input);
    if(oc==EOF)
        fatal_err("ungetc failed, EOF is returned.");

    for (row=0; row<=8; row++)
    {

        for (column=0; column<=8; column++)
        {
            do
                fscanf(f_input,"%c ",&ch);
            while(ch==' ' || ch=='\n')
                ;
            if( ! ((ch>='1' && ch<='9') || (ch=='*') ) )

                fatal_err("Unacceptable input char, char is %c",ch);

            apic=all_possible_in_cell();

            ss1.cell[row][column] = (uint16_t)(ch=='*' ? apic : 1<<(ch-'1') );
            ss1.cell_isv[row][column] = (ch=='*'? false: true);

        }

    }

    pos = ftell(f_input);

    if(pos==EOF)
        fatal_err("pos failed.");

    print_info("``` down_pos is %ld, current_ch is %c\n",pos,getc(f_input));

    fclose(f_input);

    hash=compute_hash(ss1);
    ss1.hash=hash;

    ss1.min_hash=hash;

    compute_contradictions(ss_ptr);

    return ss1;
}


void fprint_ss(FILE* of,struct sudoku_state ss)
{

    unsigned row;
    unsigned column;
    uint16_t sc=0;
    unsigned uc;

    if(of==stdout)
    {
#ifdef DEBUG
        fprintf(of,"\nhash is %u\n",ss.hash);


        fprintf(of,"Value in cells:\n");
        for(row=0; row<=8; row++)
        {
            for(column=0; column<=8; column++)
            {

                uc=count_zero_bits_on_right(ss.cell[row][column]);
                fprintf(of,"%d ",uc+1);
            }
            fprintf(of,"\n");
        }
#endif // DEBUG
    }
    else
    {
        if(of !=stdout)
            ftell(of);
    }
//#ifdef DEBUG
    if(of != stdout)
    {
        for(row=0; row<=8; row++)
        {
            for(column=0; column<=8; column++)
            {

                sc=ss.cell[row][column];
                if(is_single_value(sc))
                {

                    fprintf(of,"%u ",count_zero_bits_on_right(sc)+1);
                    if(of !=stdout)
                        ftell(of);
                }
                else
                {

                    fprintf(of,"%c ",'*');
                    if(of !=stdout)
                        ftell(of);
                }
            }

            fprintf(of,"\n");
            if(of !=stdout)
                ftell(of);
        }
    }
//#endif // DEBUG
    if(of==stdout)
    {
#ifdef DEBUG
        //printf("\n");
        fprintf(of,"\nBounded cells:\n");
        for(row=0; row<=8; row++)
        {
            for(column=0; column<=8; column++)
                //printf(ibc.cell[row][column]==true?"1 ":"0 ");
                fprintf(of,ss.cell_isv[row][column]==true?"1 ":"0 ");
            fprintf(of,"\n");
        }

        fprintf(of,"\nContradictions:\n");
        for(row=0; row<=8; row++)
        {
            for(column=0; column<=8; column++)
                fprintf(of,"%d ",ss.contradiction[row][column]);
            fprintf(of,"\n");
        }
#endif // DEBUG
    }


}


noreturn void fatal_err_callee(const char * const s) // help from comp.lang.c
{
    if ((s == NULL) || (*s == '\0'))
    {
        fprintf(stderr, "Please provide a proper message for "
                "fatal_err_callee function.\n");
        exit(EXIT_FAILURE);
    }
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wdate-time"

    fprintf(stderr,"DATE:%s\n",__DATE__);
    fprintf(stderr,"TIME:%s\n",__TIME__);

#pragma clang diagnostic pop

    fprintf(stderr, "\nERROR:%s\n", s);
    exit(EXIT_FAILURE);
}

void print_info_callee(const char * const s)
{
    if ((s == NULL) || (*s == '\0'))
    {
        fprintf(stderr, "Please provide a proper message for "
                "print_info_callee function.\n");
        exit(EXIT_FAILURE);
    }

    fprintf(stdout,"%s\n",s);

    return;
}

void *my_alloc( size_t size )
{
    static void *alloc_ptr = NULL; // see: http://c-faq.com/ptrs/passptrinit.html
    alloc_ptr = malloc(size);

    if( alloc_ptr == NULL )
        fatal_err("alloc_ptr memory allocation failed.");

    return alloc_ptr;
}

uint8_t popcnt(uint32_t v)
{
    //https://graphics.stanford.edu/~seander/bithacks.html
    uint8_t c;
    for (c = 0; v; c++)
    {
        v &= v - 1; // clear the least significant bit set
    }
    return c;
}

void first_uneq_cell
(const struct sudoku_state current_ptr, const struct sudoku_state end_ptr,int *const row,int *const column)
{
    uint16_t current_cell=0;
    uint16_t end_cell=0;

    if( *row<0 || *column<0)
        fatal_err("Wrong sub.");

    *row=0;
    *column=0;

    for(*row=0; *row<=8; (*row)++)
    {
        for(*column=0; *column<=8; (*column)++)
        {
            current_cell=current_ptr.cell[*row][*column];
            end_cell=end_ptr.cell[*row][*column];
            if(current_cell!=end_cell )

                break;
        }
        if(*column>8)
        {
            continue;
        }

        current_cell=current_ptr.cell[*row][*column];
        end_cell=end_ptr.cell[*row][*column];
        if(current_cell!=end_cell )

            break;
    }

    if(*row>8)
    {
        *row=8;
        *column=8;
    }
    return;
}

bool is_repeated
(struct sudoku_state *const root_ptr,struct sudoku_state *const end_ptr)
{
    bool ir=false;
    struct sudoku_state *current_ptr=root_ptr;

    if(root_ptr>end_ptr)
        fatal_err("Wrong pointer.");

    for(; current_ptr<end_ptr; current_ptr++)
    {
        if(sudoku_states_equal(*current_ptr,*end_ptr))
        {
            ptrdiff_t pd=end_ptr-current_ptr;
            print_info("$ is_repeated diff %td\n",pd);
            ir=true;
            break;
        }

    }

    return ir;
}

noreturn void print_finish(void)
{
    printf("EOF in input file %s reached.\n",SI);
    printf("Output file name is %s\n",SO);
    exit (EXIT_SUCCESS);
}

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-parameter"

void print_cell_callee(const char* const cell_name, uint16_t cell)
{
#ifdef DEBUG

    enum SINGLE_VALUE sv;
    unsigned char ch='0';

    if(cell_name[0]=='\0')
        fatal_err("Wrong cell_name");

    printf("`` %s (1..9) is ",cell_name);
    for(sv=ONE; sv<=NINE; sv<<=1)
    {
        uint16_t cell_sv=cell&sv;
        if(cell_sv)
        {
            ch=try_next(cell_sv)+'0';
            if(ch<'0' || ch>'9')
                fatal_err("Illegal char.");
            printf("%c ",ch);
        }


    }

    if(cell==0)
        printf("0");
    printf("\n");
    printf("%c",'\0');


#endif // DEBUG
}
#pragma clang diagnostic pop

// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ //

The three related files:

sudoku_input.text

Code:

/
* * * * 5 * * * *
* 4 3 2 6 * * 8 *
* * 1 * * 4 9 2 *
* * 4 * 1 * * 5 *
1 2 * 5 * 3 * 9 6
* 5 * * 2 * 7 * *
* 3 5 1 * * 2 * *
* 1 * * 4 2 8 6 *
* * * * 9 * * * *
/
* 2 * * * * * * *
* * * 6 * * * * 3
* 7 4 * 8 * * * *
* * * * * 3 * * 2
* 8 * * 4 * * 1 *
6 * * 5 * * * * *
* * * * 1 * 7 8 *
5 * * * * 9 * * *
* * * * * * * 4 *
/
1 * * 4 8 9 * * 6
7 3 * * * * * 4 *
* * * * * 1 2 9 5
* * 7 1 2 * 6 * *
5 * * 7 * 3 * * 8
* * 6 * 9 5 7 * *
9 1 4 6 * * * * *
* 2 * * * * * 3 7
8 * * 5 1 2 * * 4
/
* 2 * 6 * 8 * * *
5 8 * * * 9 7 * *
* * * * 4 * * * *
3 7 * * * * 5 * *
6 * * * * * * * 4
* * 8 * * * * 1 3
* * * * 2 * * * *
* * 9 8 * * * 3 6
* * * 3 * 6 * 9 *
/
* * * 6 * * 4 * *
7 * * * * 3 6 * *
* * * * 9 1 * 8 *
* * * * * * * * *
* 5 * 1 8 * * * 3
* * * 3 * 6 * 4 5
* 4 * 2 * * * 6 *
9 * 3 * * * * * *
* 2 * * * * 1 * *
/
2 * * 3 * * * * *
8 * 4 * 6 2 * * 3
* 1 3 8 * * 2 * *
* * * * 2 * 3 9 *
5 * 7 * * * 6 2 1
* 3 2 * * 6 * * *
* 2 * * * 9 1 4 *
6 * 1 2 5 * 8 * 9
* * * * * 1 * * 2
/
* * * 2 6 * 7 * 1
6 8 * * 7 * * 9 *
1 9 * * * 4 5 * *
8 2 * 1 * * * 4 *
* * 4 6 * 2 9 * *
* 5 * * * 3 * 2 8
* * 9 3 * * * 7 4
* 4 * * 5 * * 3 6
7 * 3 * 1 8 * * *
/

sudoku_output.text

Code:

$
2 7 8 9 5 1 6 3 4 
9 4 3 2 6 7 5 8 1 
5 6 1 8 3 4 9 2 7 
8 9 4 7 1 6 3 5 2 
1 2 7 5 8 3 4 9 6 
3 5 6 4 2 9 7 1 8 
6 3 5 1 7 8 2 4 9 
7 1 9 3 4 2 8 6 5 
4 8 2 6 9 5 1 7 3 
$
1 2 6 4 3 7 9 5 8 
8 9 5 6 2 1 4 7 3 
3 7 4 9 8 5 1 2 6 
4 5 7 1 9 3 8 6 2 
9 8 3 2 4 6 5 1 7 
6 1 2 5 7 8 3 9 4 
2 6 9 3 1 4 7 8 5 
5 4 8 7 6 9 2 3 1 
7 3 1 8 5 2 6 4 9 
$
1 5 2 4 8 9 3 7 6 
7 3 9 2 5 6 8 4 1 
4 6 8 3 7 1 2 9 5 
3 8 7 1 2 4 6 5 9 
5 9 1 7 6 3 4 2 8 
2 4 6 8 9 5 7 1 3 
9 1 4 6 3 7 5 8 2 
6 2 5 9 4 8 1 3 7 
8 7 3 5 1 2 9 6 4 
$
1 2 3 6 7 8 9 4 5 
5 8 4 2 3 9 7 6 1 
9 6 7 1 4 5 3 2 8 
3 7 2 4 6 1 5 8 9 
6 9 1 5 8 3 2 7 4 
4 5 8 7 9 2 6 1 3 
8 3 6 9 2 4 1 5 7 
2 1 9 8 5 7 4 3 6 
7 4 5 3 1 6 8 9 2 
$
5 8 1 6 7 2 4 3 9 
7 9 2 8 4 3 6 5 1 
3 6 4 5 9 1 7 8 2 
4 3 8 9 5 7 2 1 6 
2 5 6 1 8 4 9 7 3 
1 7 9 3 2 6 8 4 5 
8 4 5 2 1 9 3 6 7 
9 1 3 7 6 8 5 2 4 
6 2 7 4 3 5 1 9 8 
$
2 7 6 3 1 4 9 5 8 
8 5 4 9 6 2 7 1 3 
9 1 3 8 7 5 2 6 4 
4 6 8 1 2 7 3 9 5 
5 9 7 4 3 8 6 2 1 
1 3 2 5 9 6 4 8 7 
3 2 5 7 8 9 1 4 6 
6 4 1 2 5 3 8 7 9 
7 8 9 6 4 1 5 3 2 
$
4 3 5 2 6 9 7 8 1 
6 8 2 5 7 1 4 9 3 
1 9 7 8 3 4 5 6 2 
8 2 6 1 9 5 3 4 7 
3 7 4 6 8 2 9 1 5 
9 5 1 7 4 3 6 2 8 
5 1 9 3 2 6 8 7 4 
2 4 8 9 5 7 1 3 6 
7 6 3 4 1 8 2 5 9 
$

sudoku_answers.text

Code:

/
2 7 8 9 5 1 6 3 4 
9 4 3 2 6 7 5 8 1 
5 6 1 8 3 4 9 2 7 
8 9 4 7 1 6 3 5 2 
1 2 7 5 8 3 4 9 6 
3 5 6 4 2 9 7 1 8 
6 3 5 1 7 8 2 4 9 
7 1 9 3 4 2 8 6 5 
4 8 2 6 9 5 1 7 3
/
1 2 6 4 3 7 9 5 8
8 9 5 6 2 1 4 7 3
3 7 4 9 8 5 1 2 6
4 5 7 1 9 3 8 6 2
9 8 3 2 4 6 5 1 7
6 1 2 5 7 8 3 9 4
2 6 9 3 1 4 7 8 5
5 4 8 7 6 9 2 3 1
7 3 1 8 5 2 6 4 9
/
1 5 2 4 8 9 3 7 6
7 3 9 2 5 6 8 4 1
4 6 8 3 7 1 2 9 5
3 8 7 1 2 4 6 5 9
5 9 1 7 6 3 4 2 8
2 4 6 8 9 5 7 1 3
9 1 4 6 3 7 5 8 2
6 2 5 9 4 8 1 3 7
8 7 3 5 1 2 9 6 4
/
1 2 3 6 7 8 9 4 5
5 8 4 2 3 9 7 6 1
9 6 7 1 4 5 3 2 8
3 7 2 4 6 1 5 8 9
6 9 1 5 8 3 2 7 4
4 5 8 7 9 2 6 1 3
8 3 6 9 2 4 1 5 7
2 1 9 8 5 7 4 3 6
7 4 5 3 1 6 8 9 2
/
5 8 1 6 7 2 4 3 9
7 9 2 8 4 3 6 5 1
3 6 4 5 9 1 7 8 2
4 3 8 9 5 7 2 1 6
2 5 6 1 8 4 9 7 3
1 7 9 3 2 6 8 4 5
8 4 5 2 1 9 3 6 7
9 1 3 7 6 8 5 2 4
6 2 7 4 3 5 1 9 8
/
2 7 6 3 1 4 9 5 8
8 5 4 9 6 2 7 1 3
9 1 3 8 7 5 2 6 4
4 6 8 1 2 7 3 9 5
5 9 7 4 3 8 6 2 1
1 3 2 5 9 6 4 8 7
3 2 5 7 8 9 1 4 6
6 4 1 2 5 3 8 7 9
7 8 9 6 4 1 5 3 2
/
4 3 5 2 6 9 7 8 1
6 8 2 5 7 1 4 9 3
1 9 7 8 3 4 5 6 2
8 2 6 1 9 5 3 4 7
3 7 4 6 8 2 9 1 5
9 5 1 7 4 3 6 2 8
5 1 9 3 2 6 8 7 4
2 4 8 9 5 7 1 3 6
7 6 3 4 1 8 2 5 9
/

Originally Posted by Salem

Some thoughts.
1. input and output files should be via argv in main, not hard-coded in the program.

Hi,
Done.

2. You use 8 and 9 all over the place; a single #define would make things far more readable.

Please explain more.

3. solve() and fill_cells() are way too long to be of any usefulness in terms of readability and testability.

Done.

4. Your use of realloc is poor - it's only saving grace is that you exit on error.

More explanation please.

5. The board censor has made ..... out of some of your symbols. The result is something we cannot even compile without a load of guessing. A simple review before hitting submit would have found this.

For this, I uploaded version 2.0 on my site.

6. Some variables (eg your alloc) are static for no good or obvious reason.

Done.

[snip]

Originally Posted by Salem

Sure, you may only have one constant at the moment, but it won't always be so.

Plus if you want 'super-sudoku' on based on 4x4 cells, it's only one number to change (rather than a mass edit and hope you get it right).

Done.
One point though, scaling may need other changes like in_region function, some typedef, and so on, I suspect.

> Your use of realloc is poor - it's only saving grace is that you exit on error.
> More explanation please.
If realloc fails, the old memory pointer is still valid.
But if you do
ptr = realloc(ptr,size);
then you leak memory because you trash your pointer.

Always do

Code:

temp = realloc(ptr,size);
if ( temp ) {
  ptr = temp;
} else {
  // now what?
  free(ptr);
}

As I said, it's a moot point in your example since you just bail out.

Done.

I just uploaded version 2.1 , just in case.