Sudoku GA

Hi,

Do you think the following fitness function is correct :

Code:

---


typedef struct
{
    uint32_t fitness; // Minimize number of wrong cells, was uint8_t
    cell_t cell[9][9];

    /*const*/ uint8_t padding[3]; // TODO add const, use function copy for this struct

} Chrom_struct;



bool bounded(cell_t cell)
{
    bool r;
    if(cell==0 || cell==ICV)
        r=false;
    else if(cell>=1 && cell<=9)
        r=true;
    else
        fatal_err("Wrong cell value, cell==%u",cell);

    return r;
}

bool depend(int row,int col,int row2,int col2)
{
    bool res=false;
    if(row2==row || col2==col || region(row,col,row2,col2) )
        res=true;

    return res;
}

bool region(int row, int col, int row2, int col2)
{
    bool r=false;

    if( in_between(row,0,2) && in_between(col,0,2) && in_between(row2,0,2) && in_between(col2,0,2) )
        r=true;
    else if( in_between(row,0,2) && in_between(col,3,5) && in_between(row2,0,2) && in_between(col2,3,5) )
        r=true;
    else if( in_between(row,0,2) && in_between(col,6,8) && in_between(row2,0,2) && in_between(col2,6,8) )
        r=true;
    else if( in_between(row,3,5) && in_between(col,0,2) && in_between(row2,3,5) && in_between(col2,0,2) )
        r=true;
    else if( in_between(row,3,5) && in_between(col,3,5) && in_between(row2,3,5) && in_between(col2,3,5) )
        r=true;
    else if( in_between(row,3,5) && in_between(col,6,8) && in_between(row2,3,5) && in_between(col2,6,8) )
        r=true;
    else if( in_between(row,6,8) && in_between(col,0,2) && in_between(row2,6,8) && in_between(col2,0,2) )
        r=true;
    else if( in_between(row,6,8) && in_between(col,3,5) && in_between(row2,6,8) && in_between(col2,3,5) )
        r=true;
    else if( in_between(row,6,8) && in_between(col,6,8) && in_between(row2,6,8) && in_between(col2,6,8) )
        r=true;

    return r;
}

void compute_fitness(Chrom_struct *const cs_ptr)
{
    uint8_t fitness=0;
    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
            for(int row2=0; row2<9; row2++)
                for(int col2=0; col2<9; col2++)
                {
                    if(row==row2 && col==col2) // Same cell
                        continue;
                    cell_t cell=cs_ptr->cell[row][col];
                    cell_t cell2=cs_ptr->cell[row2][col2];
                    if(depend(row,col,row2,col2) && cell==cell2 && bounded(cell) && bounded(cell2))
                        fitness++;
                }

    if(fitness%2 != 0)
        fatal_err("Wrong fitness==%d",fitness);


    if(fitness==0 )
    {
        bool all_bounded=true;
        for(int row=0; row<9; row++)
            for(int col=0; col<9; col++)
            {
                cell_t cell=cs_ptr->cell[row][col];
                if(!bounded(cell))
                    all_bounded=false;

            }
        if(all_bounded)
        {
            printf("# solved: #\n");
            print_chrom(*cs_ptr);
            exit (EXIT_SUCCESS);
        }
    }

    cs_ptr->fitness=(fitness/2);
    return;
}

---

Code:

---

Chrom cs[i]:
3 6 9 5 5 6 3 7 2
3 4 3 2 6 6 4 8 5
4 7 1 7 7 4 9 2 1
9 7 4 8 1 6 8 5 8
1 2 7 5 5 3 4 9 6
1 5 2 9 2 1 7 3 3
1 3 5 1 8 7 2 5 3
7 1 9 8 4 2 8 6 4
9 8 8 4 9 9 2 6 6
Fitness is 36

--- i==0

---

Code:

---

Chrom cs[i]:
3 6 9 5 5 1 3 7 2
3 4 3 2 6 6 4 8 5
4 7 1 7 7 4 9 2 1
9 7 4 8 1 6 8 5 8
1 2 7 5 5 3 4 9 6
1 5 2 9 2 1 7 3 3
6 3 5 1 8 7 2 5 3
7 1 9 8 4 2 8 6 4
9 8 8 4 9 9 2 6 6
Fitness is 53

--- i==2

---

Excuse me I'm not answering your question but I'm just studying about GA and I have a basic question I think you can answer. Do I need to produce the exact same number of children in the cross-over step? For example if I have an initial population of 40, do I need to produce exactly 40 chromosomes as the next population? Or I can also choose a random number of them -for instance- 30 of them and thus produce 60 children? (each two chromosomes together produce a child, and so 30 parents give 30 children)?! I see no problem in doing that (as a beginner to it of course) but every explanations I see (including my textbook) produces the exact same number of chromosomes as the next population.

Quote:

---

Originally Posted by narniat

Excuse me I'm not answering your question but I'm just studying about GA and I have a basic question I think you can answer. Do I need to produce the exact same number of children in the cross-over step? For example if I have an initial population of 40, do I need to produce exactly 40 chromosomes as the next population? Or I can also choose a random number of them -for instance- 30 of them and thus produce 60 children? (each two chromosomes together produce a child, and so 30 parents give 30 children)?! I see no problem in doing that (as a beginner to it of course) but every explanations I see (including my textbook) produces the exact same number of chromosomes as the next population.

---

To begin with, I suggest a fixed number of population. I have a few mutation of fittest in the previous population and rest are produced using cross-over.

Code:

---

#define POPULATION 11
static const int MAX_GEN = 100;

---

I could post the whole code. Please note that there are issues for this code. My main priority is to get the correct answer.

Code:

---

// Trying to solve Sudoku using Genetic Algorithm.

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdnoreturn.h>
#include <inttypes.h>
#include <stdbool.h>
#include <time.h>
#include <math.h>

typedef uint8_t cell_t;

#define POPULATION 11 // 100 15 19 10 11 9
static const int MAX_GEN = 100;//10; 60 120 40 100 200
static const int MAX_ALLOC_SIZE=20000000;

static const double MAX_PROB = 0.800;
static const double MIN_PROB = 0.050;
static const cell_t ICV = (cell_t)(~0); // Illegal cell value

void next_cell(const int , const int , int* const , int* const );
uint8_t rand_value(cell_t const * const p, int n);
uint8_t find_first_unbounded(cell_t const * const p, int n);
void print_possible_values(cell_t const * const p, int n);
uint8_t count_possible_values(cell_t const * const p, int n);
bool region(int row, int col, int row2, int col2);
bool in_between(int n, int low, int high);
noreturn void fatal_err_callee(const char * const); // help from comp.lang.c
void *inside_alloc(size_t);//my_alloc
double ratio(void);

#define BUFF_SIZE 256
#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)\


typedef struct
{
    uint32_t fitness; // Minimize number of wrong cells, was uint8_t
    cell_t cell[9][9];

    /*const*/ uint8_t padding[3]; // TODO add const, use function copy for this struct

} Chrom_struct;

typedef struct
{
    double cell_prob[9][9][10]; // row column choices
} Gen_prob_struct;

Chrom_struct permutate(const Chrom_struct ,const Chrom_struct,const Chrom_struct);
void random_cell(const Chrom_struct , const Chrom_struct , int *const ,int *const );
void max_coll( /*const Chrom_struct ,*/const Chrom_struct , const Chrom_struct , int *,int *);
void print_count(int const * const );
Chrom_struct correct_count(Chrom_struct , const Chrom_struct);//,int *const );// ,int);
void count_ni (const Chrom_struct);
void first_unbounded_cell(const Chrom_struct , int *const , int *const);
Chrom_struct mutate_replace(Chrom_struct, const Chrom_struct );
Chrom_struct mutate_best( Chrom_struct,const  Chrom_struct );
Chrom_struct mutate_random(Chrom_struct,const Chrom_struct );
void test_gen_prob(const Gen_prob_struct );
int compare_fitness(const void *, const void * );
bool compare_chrom(Chrom_struct, Chrom_struct );
bool placable_value(Chrom_struct, int, int, cell_t );
Gen_prob_struct calc_gen_prob( const Chrom_struct);
uint32_t count_value(Chrom_struct const* const,int,int,cell_t);
void compute_fitness( Chrom_struct *const );
bool depend(int row,int col,int row2,int col2);
bool bounded(cell_t);
Chrom_struct test(void);
Chrom_struct init(Chrom_struct, Chrom_struct *base_ptr);
static void print_chrom_callee(Chrom_struct ch);
void print_prob_callee(const Gen_prob_struct );

#define print_chrom(ch)\
    do { \
    printf("\nChrom %s:\n",#ch);\
    print_chrom_callee(ch);\
    } while(0) \

#define print_prob(prob)\
    do{\
        printf("\nprob is %s\n",#prob);\
        print_prob_callee(prob);\
    } while(0)\

Chrom_struct test(void)
{

    Chrom_struct s1=
    {
        .cell=
        {
            {0, 0, 0, 0, 5, 0, 0, 0, 0},
            {0, 4, 3, 2, 6, 0, 0, 8, 0},
            {0, 0, 1, 0, 0, 4, 9, 2, 0},
            {0, 0, 4, 0, 1, 0, 0, 5, 0},
            {1, 2, 0, 5, 0, 3, 0, 9, 6},
            {0, 5, 0, 0, 2, 0, 7, 0, 0},
            {0, 3, 5, 1, 0, 0, 2, 0, 0},
            {0, 1, 0, 0, 4, 2, 8, 6, 0},
            {0, 0, 0, 0, 9, 0, 0, 0, 0},
        },
        .fitness=0
    };


    return s1;
}

Chrom_struct init(Chrom_struct original, Chrom_struct *base_ptr)
{
    Chrom_struct res= {.cell={{0}},.fitness=0};
    Chrom_struct base= {.cell={{0}},.fitness=0};
    int count[10]={0};

    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
        {
            cell_t cell=original.cell[row][col];
            bool ib = bounded(cell);
            if( ib )
            {
                res.cell[row][col]=cell;
                base.cell[row][col]=cell;
                count[cell]++;
            }
            else // !ib , cell is not initially bounded
            {

                cell_t possible_values[]= {1,2,3,4,5,6,7,8,9}; // modifiable, TODO start from 0
                uint8_t nop = 9;// Number of possiblities for each cell

                for(int row2=0; row2<9; row2++)
                    for(int col2=0; col2<9; col2++)
                    {
                        if(row2==row && col2==col) // same cell
                            continue;

                        if(depend(row,col,row2,col2))
                        {
                            cell_t ocell=original.cell[row][col];
                            cell_t cell2=original.cell[row2][col2];
                            bool cond=bounded(ocell)||bounded(cell2);
                            if(bounded(ocell) && bounded(cell2)) // added
                                cond=false;
                            if(cond)

                            {
                                // Only when to eliminate a possibility
                                nop--;
                                possible_values[cell2-1]=ICV;
                            }
                        }
                    }

                int cnt=0;
                for(cell_t i=1;i<=9;i++)
                    if(count[i]<9 && placable_value(base,row,col,i))
                        cnt++;

            if (cnt == 0) // One cell has no value
            { // TODO maybe not solvable here
                printf("$## cnt==0\n");
                cell_t i;
                for(i=1;i<=9;i++)
                    if(count[i]<9)
                        break;
                assert(bounded(i));
                // TODO base?
                if(!bounded(i))
                    fatal_err("i=%u",i);
                res.cell[row][col]=i;
                count[i]++;

                print_possible_values(possible_values,9);

            }

                else if(cnt == 1) // One cell is single valued
                {
                    // Bound the single value
                    uint8_t ffu=find_first_unbounded(possible_values,9);
                    res.cell[row][col]=ffu+1; // why this and next differ
                    base.cell[row][col]=ffu;
                    count[ffu+1]++;
                    printf("$$$ row==%d col==%d cell==%u\n",row,col,ffu);
                }
                else // Randomly place for initial population
                {
                    double pratio=ratio();
                    double cnt_inv = (double)1.0 / (double)cnt;
                    int ind;
                    for(ind=0 ; ind<=cnt ; ind++)
                    {
                        double min=ind*cnt_inv;
                        double max=(ind+1)*cnt_inv;
                        if(pratio>min && pratio<max)
                            break;
                    }
                    if(ind>cnt)
                        fatal_err("Wrong ind==%d cnt==%d",ind, cnt);

                    cell_t rv = rand_value(possible_values,ind);
                    printf("$ row==%d col==%d cnt==%d %.2lf ind==%d rv==%u\n"
                          , row, col, cnt, cnt_inv,ind,rv);
                    print_possible_values(possible_values,9);
                    printf("\n");

                    if(count[rv]>=9 || !placable_value(base,row,col,rv))
                        for(rv=1; rv<=9 ;rv++) // single condition
                            if(count[rv]<9 && placable_value(base,row,col,rv))
                                break;
                    if(!bounded(rv))
                        fatal_err("!bounded");
                    if(!placable_value(base,row,col,rv))
                    {
                        print_chrom(base);
                        fatal_err("Wrong row==%d col==%d rv==%d",row,col,rv);
                    }
                    res.cell[row][col]=rv;
                    base.cell[row][col]=0; // ICV;

                    count[rv]++;

                }

            }
        }
    compute_fitness(&res);
    compute_fitness(&base);
    uint32_t bf=base.fitness;

    print_chrom(base);
    if(bf!=0)
        fatal_err("$ base fitness==%u\n",bf);
    base.fitness=bf;

    *base_ptr = base;

    res=correct_count(res,base);
    compute_fitness(&res);

    print_chrom(res);

    print_count(count);
    count_ni(res);
    return res;
}

void print_count(int const * const count)
{
    for(int i=0; i<=9; i++) // i=1
        printf("c[%d]=%d ",i,count[i]);
    printf("\n");
    return;
}

Chrom_struct correct_count(Chrom_struct cs, const Chrom_struct base)
{

    int count[10]={0};
    static int pnum=0;
    static int npnum=0;

    printf("##$$\n");
    print_count(count);


    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
        {
            cell_t cell=cs.cell[row][col];
            count[cell]++;
        }

    for(cell_t cv=1; cv<=9; cv++)
    {
        while(count[cv]>9)
        {
            for(int row=0; row<9; row++)
                for(int col=0; col<9; col++)
                    if(cs.cell[row][col]==cv && !bounded(base.cell[row][col]))
                    {
                        cell_t cv2;

                        for(cv2=1; cv2<=9; cv2++)
                            if(count[cv2]<9 && placable_value(base,row,col,cv2))
                            {
                                pnum++;
                                cs.cell[row][col]=cv2;
                                count[cv2]++;
                                count[cv]--;
                                break;

                            }

                        if(cv2>=10)
                        {
                            uint32_t min_fitness=(uint32_t)~0;
                            cell_t save_cv2=0;

                            for(cv2=1; cv2<=9; cv2++)  // TODO select lowest fitness
                                if(count[cv2]<9 )
                                {
                                    cs.cell[row][col]=cv2;
                                    compute_fitness(&cs);

                                    if(cs.fitness<min_fitness)
                                    {
                                        min_fitness=cs.fitness;
                                        save_cv2=cv2;
                                    }

                                    count[cv2]++;
                                    count[cv]--;
                                    break;
                                }
                            if(bounded(save_cv2))
                            {
                                npnum++;
                                cs.cell[row][col]=save_cv2;
                                compute_fitness(&cs);
                            }
                    else
                    {
                        for(cv2=1; cv2<=9; cv2++)
                            if(count[cv2]<9 )//placable_value
                            {

                                npnum++;
                                cs.cell[row][col]=cv2;

                                count[cv2]++;
                                count[cv]--;
                                break;
                            }
                    }
                }
            }
        }
    }

    print_count(count);
    printf("#$@\n");
    print_chrom(cs);
    printf("#@@\n");
    printf("pnum is %d all is %d pnum/all is %lf\n"
          ,pnum,pnum+npnum,(double)pnum/(double)(pnum+npnum));
    printf("#$@@\n");
    count_ni(cs);

    compute_fitness(&cs);

    return cs;
}

bool depend(int row,int col,int row2,int col2)
{
    bool res=false;
    if(row2==row || col2==col || region(row,col,row2,col2) )
        res=true;

    return res;
}

// TODO maybe the counting is wrong i==0 comparing i==2
void compute_fitness(Chrom_struct *const cs_ptr)
{
    uint8_t fitness=0;
    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
            for(int row2=0; row2<9; row2++)
                for(int col2=0; col2<9; col2++)
                {
                    if(row==row2 && col==col2) // Same cell
                        continue;
                    cell_t cell=cs_ptr->cell[row][col];
                    cell_t cell2=cs_ptr->cell[row2][col2];
                    if(depend(row,col,row2,col2) && cell==cell2 && bounded(cell) && bounded(cell2))
                        fitness++;
                }

    if(fitness%2 != 0)
        fatal_err("Wrong fitness==%d",fitness);


    if(fitness==0 )
    {
        bool all_bounded=true;
        for(int row=0; row<9; row++)
            for(int col=0; col<9; col++)
            {
                cell_t cell=cs_ptr->cell[row][col];
                if(!bounded(cell))
                    all_bounded=false;

            }
        if(all_bounded)
        {
            printf("# solved: #\n");
            print_chrom(*cs_ptr);
            exit (EXIT_SUCCESS);
        }
    }

    cs_ptr->fitness=(fitness/2);
    return;
}

void print_possible_values(cell_t const * const p, int n)
{
    int i;
    printf("$$ ");
    for(i=0; i<n; i++)
        printf("%u ",*(p+i) );

    printf("\n");
    return;
}

uint8_t count_possible_values(cell_t const * const p, int n)
{
    uint8_t cnt=0;
    int i;

    for(i=0; i<n; i++)
    {

        bool ib=bounded(*(p+i)); // (p[i])
        if(ib)
            cnt++;
    }

    return cnt;
}

cell_t find_first_unbounded(cell_t const * const p, int n)
{
    cell_t r;

    for(r=0; r<n; r++)
        if(bounded(p[r]))
            break;

    return ++r;
}

cell_t rand_value(cell_t const * const p, int ind)
{
    int i2;
    for( i2=ind;i2<=9;i2++)
        if(bounded(p[i2]))
          return p[i2];
    if(i2>=10 )
        for(i2=9; i2>=0; i2--)
            if(bounded(p[i2]))
              break;
    return p[i2];
}

bool in_between(int n, int low, int high)
{
    bool r=false;
    if(!(low<high))
        fatal_err("Wrong low and high, low==%d, high==%d",low,high);

    if(n>=low && n<=high)
        r=true;

    return r;

}
bool region(int row, int col, int row2, int col2)
{
    bool r=false;

    if( in_between(row,0,2) && in_between(col,0,2) && in_between(row2,0,2) && in_between(col2,0,2) )
        r=true;
    else if( in_between(row,0,2) && in_between(col,3,5) && in_between(row2,0,2) && in_between(col2,3,5) )
        r=true;
    else if( in_between(row,0,2) && in_between(col,6,8) && in_between(row2,0,2) && in_between(col2,6,8) )
        r=true;
    else if( in_between(row,3,5) && in_between(col,0,2) && in_between(row2,3,5) && in_between(col2,0,2) )
        r=true;
    else if( in_between(row,3,5) && in_between(col,3,5) && in_between(row2,3,5) && in_between(col2,3,5) )
        r=true;
    else if( in_between(row,3,5) && in_between(col,6,8) && in_between(row2,3,5) && in_between(col2,6,8) )
        r=true;
    else if( in_between(row,6,8) && in_between(col,0,2) && in_between(row2,6,8) && in_between(col2,0,2) )
        r=true;
    else if( in_between(row,6,8) && in_between(col,3,5) && in_between(row2,6,8) && in_between(col2,3,5) )
        r=true;
    else if( in_between(row,6,8) && in_between(col,6,8) && in_between(row2,6,8) && in_between(col2,6,8) )
        r=true;

    return r;
}
bool bounded(cell_t cell)
{
    bool r;
    if(cell==0 || cell==ICV)
        r=false;
    else if(cell>=1 && cell<=9)
        r=true;
    else
        fatal_err("Wrong cell value, cell==%u",cell);

    return r;
}

static void print_chrom_callee(Chrom_struct ch)
{
    cell_t cell;
    int row, col;

    for(row=0; row<9; row++)
    {
        for(col=0; col<9; col++)
        {
            cell=ch.cell[row][col];
            printf("%u ",cell);
        }
        printf("\n");
    }

    printf("Fitness is %u\n\n",ch.fitness);
    return;
}

uint32_t count_value(Chrom_struct const* const previous_ptr,int row,int col,cell_t cell)
{
    uint32_t cv=0;
    for (int ind=0; ind<POPULATION; ind++) // ind=1
    {

        cell_t pcell=(previous_ptr+ind)->cell[row][col];
        if(pcell==cell)
        {

            cv++;
        }
    }

    return cv;
}

bool placable_value(Chrom_struct base, int row, int col, cell_t icell)
{
    bool ipv=true; // is placable value

    for(int row2=0; row2<9; row2++)
        for(int col2=0; col2<9; col2++)
        {
            bool dep=depend(row, col, row2, col2);
            bool eq= (icell == base.cell[row2][col2]);
            if(dep && eq)
                return false;
        }

    return ipv;
}

Gen_prob_struct calc_gen_prob(const Chrom_struct base)
{
    Gen_prob_struct gp= {{{{ (double)0.0 }}}};
    test_gen_prob(gp);

    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
        {
            cell_t cell=base.cell[row][col];
            if(!bounded(cell))
            {
                uint32_t cv=0;
                for(cell_t i=1; i<=9; i++)
                {
                    bool ipv=placable_value(base,row,col,i);
                    if(ipv)
                        cv++;
                }
                for(cell_t i=1; i<=9; i++) // possible values in each cell
                {
                    if(!( cv<=POPULATION))
                        fatal_err("cv==%u\n",cv);
                    bool ipv=placable_value(base,row,col,i);
                    double prob=0.0;
                    if(ipv)
                        prob=(double)cv / (double)(POPULATION);

                    if(!(prob>=0.0 && prob<=1.0))
                        fatal_err("prob==%lf",prob);
                    if( prob<MIN_PROB && ipv)
                        prob=MIN_PROB;
                    else if(prob>MAX_PROB && ipv)
                        prob=MAX_PROB;

                    if(!(prob>=0.0 && prob<=MAX_PROB))
                        fatal_err("prob==%lf",prob);
                    gp.cell_prob[row][col][i]=prob+gp.cell_prob[row][col][i-1];

                }

                double sum=0;
                for(int i=1; i<=9; i++)
                {

                    double prob=gp.cell_prob[row][col][i]-gp.cell_prob[row][col][i-1];
                    sum += prob;

                }

                if(sum<0.99||sum>1.01)// Redistribute
                {

                    for(int i=1; i<=9; i++)
                    {
                        double new_prob=gp.cell_prob[row][col][i]/sum;
                        if(new_prob<0.0 || new_prob>1.0)
                            fatal_err("new_prob==%lf",new_prob);

                        gp.cell_prob[row][col][i]=new_prob;

                    }

                    double new_sum=gp.cell_prob[row][col][9];
                    if(new_sum <0.99 || new_sum>1.01)
                        fatal_err("new_sum==%lf row==%d col==%d\n",new_sum,row,col);
                }

            }
            else // bounded(cell)
            {
                for(int i=cell; i<=9; i++)
                    gp.cell_prob[row][col][i]=1.0;
                test_gen_prob(gp);
            }
        }

    test_gen_prob(gp);

    return gp;
}

void test_gen_prob(const Gen_prob_struct ps)
{

    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
            for(int i=1; i<=10; i++)
            {
                double prob=ps.cell_prob[row][col][i];
                if(!(prob>-0.01 && prob<1.01))
                {
                    print_prob(ps);
                    fatal_err("row==%d col==%d i==%d prob==%lf"
                              ,row,col,i,prob);
                }
            }
    return;
}

Chrom_struct mutate_replace(Chrom_struct cs,const Chrom_struct base )
{
    Chrom_struct count= {.cell={{0}},.fitness=0}; // Counts the number of contradictions for all cells
    Chrom_struct copy=cs;
    int row=0;
    int col=0;

    int mrow=0;
    int mcol=0;
    int mrow2=0;
    int mcol2=0;

    //test_gen_prob(ps);

    for(row=0; row<9; row++)
        for(col=0; col<9; col++)
        {

            for(int row2=0; row2<9; row2++)
                for(int col2=0; col2<9; col2++)
                {
                    if(row==row2 && col==col2)
                        continue;
                    if(!depend(row,col,row2,col2) )
                        continue;

                    cell_t cell=cs.cell[row][col];
                    cell_t cell2=cs.cell[row2][col2];
                    bool cond = (depend(row,col,row2,col2) && cell==cell2);
                    if(cond)
                        count.cell[row][col]++;

                }
        }

    first_unbounded_cell(base, &row, &col);

    max_coll(base,count,&mrow, &mcol);

    first_unbounded_cell(base, &row, &col);

    do
    {
        random_cell(cs,base,&mrow2,&mcol2);
        count.cell[mrow2][mcol2]=0;
    }
    while
        (cs.cell[mrow][mcol]==cs.cell[mrow2][mcol2]);

    const cell_t temp = cs.cell[mrow2][mcol2];
    cs.cell[mrow2][mcol2]=cs.cell[mrow][mcol];
    cs.cell[mrow][mcol]=temp;

    compute_fitness(&cs);

    if(compare_chrom(cs,copy))
    {
        fprintf(stderr,"mrow==%d mcol==%d mrow2==%d mcol2==%d temp==%u\n"
              ,mrow,mcol, mrow2,mcol2, temp );
        fatal_err("no change");
    }
    count_ni(cs);
    return cs;
}

Chrom_struct mutate_random(Chrom_struct cs,const Chrom_struct base)
{
    Chrom_struct copy=cs;

    int row,col;
    int row2,col2;
    random_cell(cs,base,&row,&col);
    do
        random_cell(cs,base,&row2,&col2);
    while(cs.cell[row][col]==cs.cell[row2][col2]
          || (row==row2 && col==col2)); // TODO add:not same cell, maybe depend
    cell_t temp=cs.cell[row][col];
    cs.cell[row][col]=cs.cell[row2][col2];
    cs.cell[row2][col2]=temp;

    bool cond=compare_chrom(cs,copy);
    if(cond)
        fatal_err("same chromes");
    return cs;
}

Chrom_struct mutate_best( Chrom_struct cs,const Chrom_struct base)
{
    Chrom_struct count= {.cell={{0}},.fitness=0}; // Counts the number of contradictions for all cells
    int mrow=0;
    int mcol=0;

    int row=0;
    int col=0;
    Chrom_struct copy=cs;

    count_ni(cs);

    // Could be based on POPULATION, MAX_GEN
    for(row=0; row<9; row++)
        for(col=0; col<9; col++)
            for(int row2=0; row2<9; row2++)
                for(int col2=0; col2<9; col2++)
                {
                    if(row==row2 && col==col2)
                        continue;
                    cell_t cell=cs.cell[row][col];
                    cell_t cell2=cs.cell[row2][col2];
                    bool cond = (depend(row,col,row2,col2) && cell==cell2);
                    if(cond)
                        count.cell[row][col]++;

                }

    max_coll(base,count,&mrow,&mcol);

    count_ni(cs);

    int mrow2,mcol2;
    count.cell[mrow][mcol]=0;
    max_coll(base,count,&mrow2,&mcol2);

    while(cs.cell[mrow][mcol]==cs.cell[mrow2][mcol2])//;
    {
        max_coll(base,count,&mrow2,&mcol2);
        count.cell[mrow2][mcol2]=0;
    }

    cell_t temp=cs.cell[mrow][mcol];
    cs.cell[mrow][mcol]=cs.cell[mrow2][mcol2];
    cs.cell[mrow2][mcol2]=temp;

    bool cond=compare_chrom(cs,copy);
    if(cond)
    {
        fatal_err("No change in cs\n");
    }

    compute_fitness(&cs);

    count_ni(cs);
    return cs;
}



void random_cell(const Chrom_struct cs, const Chrom_struct base
                , int *const rrow_ptr,int *const rcol_ptr)
{
    int row2,col2;
    int row=(int)(ratio()*9.0); // random cell
    int col=(int)(ratio()*9.0);

    if(row<0 || row>8 || col<0 || col>8)
        fatal_err("row==%d col==%d",row,col);
    printf("### row==%d col==%d\n",row,col);
    do
    {
        row2=row;
        col2=col;

        while(bounded(cs.cell[row][col]))
        {
            if(row==8 && col==8)
            {
                first_unbounded_cell(base, &row, &col);
                break;
            }
            else // TODO unbounded in base?
            {
                do
                {
                    next_cell(row,col,&row2,&col2);
                    row=row2;
                    col=col2;
                }
                while(bounded(base.cell[row2][col2]));

                break; // why this must be here?
            }

        }

    }
    while(false);

    if(row>8 || col>8)
    {
        row=0;
        col=0;
        first_unbounded_cell(base, &row, &col);
    }
    if(row<0 || row>8 || col<0 || col>8)
        fatal_err("row==%d col==%d",row,col);
    cell_t base_cell=base.cell[row][col];
    if(bounded(base_cell))
        fatal_err("Wrong base_cell");
    if(!bounded(cs.cell[row][col]))
        fatal_err("Wrong cell");
    *rrow_ptr=row;
    *rcol_ptr=col;

    return;
}

void max_coll(const Chrom_struct base, const Chrom_struct count, int *mrow,int *mcol)
{
    int row,col;
    uint16_t max_collusion=0;

    first_unbounded_cell(base, &row,&col);

    max_collusion=count.cell[row][col];
    *mrow=row;
    *mcol=col;
    for(row=0; row<9; row++)
        for(col=0; col<9; col++)
        {
            if(bounded(base.cell[row][col]))
                continue;
            cell_t cellc=count.cell[row][col];
            cell_t base_cell=base.cell[row][col];

            bool possible=!bounded(base_cell);
            if(cellc>max_collusion && possible)
            {
                max_collusion=cellc;
                *mrow=row;
                *mcol=col;
            }
        }
    if( bounded(base.cell[*mrow][*mcol] ))
        fatal_err("cell is bounded");
    if(*mrow>8 && *mcol>8)
        fatal_err("end reached.");

    return;
}



void next_cell(const int row, const int col, int* const new_row_ptr, int* const new_col_ptr)
{
    assert(row>=0 && row<=8);
    assert(col>=0 && col<=8);

    if(row==8 && col==8)
        fatal_err("No next cell for last cell.");

    if(col<8)
    {
        *new_row_ptr=row;
        *new_col_ptr=(col+1);
    }
    else
    {
        assert(col==8);
        *new_row_ptr=(row+1);
        *new_col_ptr=0;
    }

    return;
}

double ratio(void)
{
    long seed = time(NULL);
    double r;
    double dr;
    static unsigned s2=0;

    s2++;
    srand((unsigned)seed+s2);
    dr = rand();
    r =  dr / (double)RAND_MAX;
    if( r<0.0 || r>1)
        fatal_err("Wrong ratio, ratio==%lf",r);

    return r;
}

bool compare_chrom(Chrom_struct first, Chrom_struct second)
{

    if(first.fitness != second.fitness) // fitness is used as hash
        return false;

    for(int row=0; row<9; row++)
        for(int col=0; col<9; col++)
        {
            cell_t cell=first.cell[row][col];
            cell_t cell2=second.cell[row][col];
            if(cell != cell2)
                return false;
            bool cond=( !bounded(cell) || !bounded(cell2) );
            if(cond)
                fatal_err("Not bounded.");
        }
    return true;
}

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 "
                "my_err 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 *inside_alloc( size_t size ) // my_alloc
{
    static void *alloc_ptr = NULL; // added static
    alloc_ptr = malloc(size);

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

    return alloc_ptr;
}

void print_prob_callee(Gen_prob_struct prob)
{

    int row, col;

    for(row=0; row<=8; row++)
    {
        for(col=0; col<=8; col++)
        {
            int si=1;
            double max=prob.cell_prob[row][col][1];
            for(int i=1; i<=9; i++)
            {
                double cprob=prob.cell_prob[row][col][i];
                double diff=cprob-prob.cell_prob[row][col][i-1];

                if(max<diff)
                {
                    si=i;

                    max=diff;
                }

            }

            printf("%d/%.2lf ", si, max);

        }
        printf("\n");
    }
    return;
}

int compare_fitness(const void * first, const void * second)
{
    int r=0;
    Chrom_struct first_struct=*(const Chrom_struct*)first;
    Chrom_struct second_struct=*(const Chrom_struct*)second;

    uint32_t ff=first_struct.fitness;
    uint32_t sf=second_struct.fitness;

    if(ff<sf)
        r=-1;
    else if(ff>sf)
        r=1;

    return r;
}

void first_unbounded_cell(const Chrom_struct base, int *const row_ptr, int *const col_ptr)
{
    int row=0;
    int col=0;

    for(row=0; row<9; row++)
    {
        if(!bounded(base.cell[row][col]))
            break;
        for(col=0; col<9; col++)
            if(!bounded(base.cell[row][col]))
                break;
        if(!bounded(base.cell[row][col]))
            break;
    }

    if( bounded(base.cell[row][col] ))
        fatal_err("cell is bounded");
    if(row>8 && col>8)
        fatal_err("end reached.");

    *row_ptr=row;
    *col_ptr=col;

    return;
}

void count_ni (const Chrom_struct filled)
{
    int count[10]={0};
    int row=0;
    int col=0;

    for(row=0; row<9; row++)
        for(col=0; col<9; col++)
        {
            cell_t cell=filled.cell[row][col];
            if(!bounded(cell))
                fatal_err("unbounded.");
            count[cell]++;

        }
    if(count[0]!=0)
        fatal_err("count[0]");

    int sum=0;
    for(int i=1; i<=9; i++)
    {
        sum += count[i];
        if(count[i]!=9)
            fatal_err("Wrong count, i==%d count[%d]==%d",i,i,count[i]);
    }
    if(sum != 9*9)
        fatal_err("Wrong sum==%d\n",sum);

    return;
}

int main(void)
{
    assert(POPULATION>=9 && POPULATION<=100);
    assert(MAX_GEN>=10 && MAX_GEN<=300);

    Chrom_struct s1,s2,base;
    Chrom_struct cs[POPULATION];
    Chrom_struct fittest;
    Gen_prob_struct current_gen= {{{{(double)0.0}}}};

    size_t size=(POPULATION+1)*(MAX_GEN+1)*sizeof(Chrom_struct);
    Chrom_struct *const beg_ptr=malloc(size);
    Chrom_struct *const end_ptr=beg_ptr+(POPULATION)*(MAX_GEN); // +1 +1
    Chrom_struct *current_ptr=beg_ptr;
    int idx=0;
    int count[10]={0};

    if(size>MAX_ALLOC_SIZE)
        fatal_err("Too big size==%zu",size);
    if(beg_ptr==NULL)
        fatal_err("Not enough memory");
    if(end_ptr==NULL)
        fatal_err("end_pre==NULL");
    if(current_ptr==NULL)
        fatal_err("current_ptr==NULL");

    s1=test();
    print_chrom(s1);

    test_gen_prob(current_gen);

    s2=init(s1,&base);
    print_chrom(s2);

    uint64_t fsum=0;
    double fav=0.0;
    double pre_fav=0.0;
    uint32_t min_fitness;

    //  For first generation
    for(int i=0; i<POPULATION; i++)
    {
        cs[i]=init(s1,&base);
        fsum+=cs[i].fitness;
        *current_ptr=cs[i];
    }

    fav=(double)fsum/(double)POPULATION;
    printf("fitness average==%lf\n",fav);

    min_fitness=cs[0].fitness;
    fittest=cs[0];
    for(int i2=0; i2<POPULATION; i2++)
        if(cs[i2].fitness < min_fitness)
        {
            min_fitness=cs[i2].fitness;
            fittest=cs[i2];
        }
    printf("min_fitness==%u\n",min_fitness);

    print_chrom(fittest);

    // For rest of generations
    for(int gen=1; gen<MAX_GEN ; gen++)
    {
        current_gen=calc_gen_prob(base);
        test_gen_prob(current_gen);

        for(idx=(gen)*POPULATION; idx<(gen+1)*POPULATION; idx++)
        {
            current_ptr=beg_ptr+idx;
            assert(current_ptr>=beg_ptr);
            assert(current_ptr<end_ptr);

            int new_idx= idx-(gen)*POPULATION;
            *(current_ptr)=cs[new_idx];
        }


        for(int pop=4; pop<POPULATION; pop++) // pop=1 2 4 5
        {
            // Fill according to current_gen
            for(int row=0; row<9; row++)
                for(int col=0; col<9; col++)
                {
                    cell_t cell=base.cell[row][col];
                    bool bnd=bounded(cell);
                    if(bnd)
                    {
                        (cs+pop)->cell[row][col]=cell;
                        count[cell]++;
                    }
                    else // !bnd
                    {
                        cell_t ind;
                        for(ind=1; ind<=9; ind++)
                        {
                            bool is_placable=placable_value(base,row,col,ind);
                            if(is_placable)
                            {
                                (cs+pop)->cell[row][col]=ind;
                                compute_fitness(cs+pop);
                                break;
                            }

                        }
                        if(bounded(ind))
                            break;

                        for(ind=1; ind<=9; ind++)
                        {
                            double r=ratio();
                            double pre_prob=current_gen.cell_prob[row][col][ind-1];
                            double prob=current_gen.cell_prob[row][col][ind];
                            assert(r>=0 && r<=1.0);
                            assert(prob>=0.0 && prob<=1.01);

                            if(r>pre_prob && r<prob)
                            {
                                if(count[ind]<9)
                                {
                                    printf("$$@\n");
                                    if(!bounded(ind))
                                        fatal_err("Wrong ind=%u",ind);
                                    (cs+pop)->cell[row][col]=ind;

                                    compute_fitness(cs+pop);
                                    count[ind]++;
                                    break;
                                }
                                else // count[ind]>=9
                                {
                                    int less_cnt=0; // less than 9 times for each sudoku number
                                    cell_t i;
                                    for( i=1; i<=9; i++)
                                    {
                                        if(i==ind)
                                            continue;
                                        if(count[i]<9)
                                            less_cnt++;
                                    }
                                    if(!(less_cnt>=0 && less_cnt<=9)) // 1..9
                                        fatal_err("less_cnt==%d",less_cnt);
                                    int nth=(int)(ratio()*less_cnt);
                                    for( i=1; i<=9; i++)
                                    {
                                        if(nth<=0 && count[i]<9)
                                            break;
                                        if(count[i]<9)
                                            nth--;
                                    }

                                    if(i>=9)
                                        continue;
                                    if(!bounded(i))
                                        fatal_err("Wrong i=%u",i);
                                    (cs+pop)->cell[row][col]=i;

                                    compute_fitness(cs+pop);
                                    count[i]++;
                                    break;

                                }


                            }
                        }
                    }

                }

            cs[pop]=correct_count(cs[pop],base);
            count_ni(cs[pop]);

            compute_fitness(cs+pop);
            print_chrom(cs[pop]);
            printf("$$#$$ gen=%d pop=%d\n",gen,pop);
            count_ni(cs[pop]);
            printf("$$#$$\n");
        }

        double f_average=0;
        for(int i=0; i<POPULATION; i++)
        {
            f_average+= (cs+i)->fitness;
        }
        f_average /= (double)POPULATION;
        printf("f_average==%lf\n",f_average);
        if(pre_fav>0.1 && (f_average-10.0)>pre_fav) // -5
            fatal_err("Average got worse: fav==%lf pre==%lf gen==%d\n",f_average,pre_fav,gen);

        min_fitness=cs[0].fitness;
        fittest=cs[0];
        for(int i2=0; i2<POPULATION; i2++)
            if(cs[i2].fitness <= min_fitness)
            {
                min_fitness=cs[i2].fitness;
                fittest=cs[i2];
            }

        print_prob(current_gen);
        printf("\ngen==%d\n",gen);
        printf("min_fitness==%u\n",min_fitness);

        printf("#0\n");
        cs[0]=fittest;
        printf("#1\n");
        cs[1]=mutate_best(fittest, base);
        printf("#2\n");
        cs[2]=mutate_replace(fittest, base);
        printf("#3\n");
        cs[3]=mutate_random(fittest,base);

        pre_fav=f_average;

        // Sort pop
        qsort(cs, POPULATION, sizeof(Chrom_struct), compare_fitness);

        for(int i=0; i<POPULATION; i++)
        {
            print_chrom(cs[i]);
            count_ni(cs[i]);
            printf("--- i==%d\n",i);
        }

        for(int i=2;i<POPULATION; i++)
        {
            bool exist_flag=false;
            for(idx=0; idx<(gen)*POPULATION; idx++)
                if( compare_chrom( cs[i],*(beg_ptr+idx) ) )
                {
                    exist_flag=true;
                    break;
                }
            if(exist_flag)
            {
                cs[i]=mutate_random(cs[i],base); // TODO try other mutations too
            }
        }

        print_chrom(cs[0]);
        print_chrom(cs[1]);
    }

    free(beg_ptr);
    printf("Limits reached: MAX_GEN==%d\n",MAX_GEN);
    return EXIT_SUCCESS;
}

---

Part of output:

Code:

---


Chrom cs[i]:
6 9 8 3 5 5 4 2 8
9 4 3 2 6 9 3 8 1
6 4 1 6 7 4 9 2 8
9 6 4 7 1 6 3 5 7
1 2 7 5 3 3 8 9 6
4 5 5 9 2 1 7 7 4
7 3 5 1 8 7 2 1 3
7 1 3 9 4 2 8 6 8
2 8 6 5 9 1 2 5 4
Fitness is 32

--- i==0

Chrom cs[i]:
6 9 8 3 5 5 4 2 8
9 4 3 2 6 5 3 8 1
6 4 1 6 7 4 9 2 8
9 6 4 7 1 6 3 5 7
1 2 7 5 3 3 8 9 6
4 5 5 9 2 1 7 7 4
7 3 5 1 8 7 2 1 3
7 1 3 9 4 2 8 6 8
2 8 6 9 9 1 2 5 4
Fitness is 32

--- i==1

Chrom cs[i]:
6 9 8 3 5 5 4 2 9
8 4 3 2 6 9 3 8 1
6 4 1 6 7 4 9 2 8
9 6 4 7 1 6 3 5 7
1 2 7 5 3 3 8 9 6
4 5 5 9 2 1 7 7 4
7 3 5 1 8 7 2 1 3
7 1 3 9 4 2 8 6 8
2 8 6 5 9 1 2 5 4
Fitness is 44

--- i==2

Chrom cs[i]:
6 9 8 3 5 5 4 2 4
9 4 3 2 6 9 3 8 1
6 4 1 6 7 4 9 2 8
9 6 4 7 1 6 3 5 7
1 2 7 5 3 3 8 9 6
8 5 5 9 2 1 7 7 4
7 3 5 1 8 7 2 1 3
7 1 3 9 4 2 8 6 8
2 8 6 5 9 1 2 5 4
Fitness is 44

--- i==3

Chrom cs[i]:
2 9 8 9 5 6 4 8 7
6 4 3 2 6 7 1 8 1
5 9 1 3 7 4 9 2 5
3 4 4 9 1 6 3 5 6
1 2 7 5 7 3 8 9 6
3 5 7 9 2 5 7 7 4
6 3 5 1 3 4 2 1 8
7 1 5 8 4 2 8 6 8
2 8 6 3 9 1 2 9 4
Fitness is 50

--- i==4

Chrom cs[i]:
2 9 8 7 5 9 4 7 8
6 4 3 2 6 9 4 8 1
5 4 1 6 7 4 9 2 8
3 6 4 7 1 6 3 5 8
1 2 7 5 3 3 8 9 6
3 5 5 9 2 1 7 7 4
6 3 5 1 9 7 2 1 3
7 1 3 9 4 2 8 6 8
2 8 6 5 9 1 2 5 4
Fitness is 51

--- i==5

Chrom cs[i]:
2 4 8 4 5 9 4 7 6
3 4 3 2 6 1 1 8 9
5 5 1 7 7 4 9 2 1
9 6 4 6 1 6 8 5 9
1 2 7 5 8 3 9 9 6
3 5 8 4 2 7 7 3 3
6 3 5 1 4 9 2 5 7
7 1 3 6 4 2 8 6 8
2 8 8 3 9 1 2 5 7
Fitness is 52

--- i==6

Chrom cs[i]:
7 9 7 9 5 7 4 9 1
2 4 3 2 6 8 3 8 8
5 5 1 3 4 4 9 2 4
3 8 4 6 1 5 3 5 5
1 2 7 5 8 3 3 9 6
3 5 6 9 2 8 7 1 1
6 3 5 1 7 9 2 4 9
7 1 7 6 4 2 8 6 1
8 7 2 4 9 6 2 6 8
Fitness is 58

--- i==7

Chrom cs[i]:
2 9 8 9 5 9 4 8 1
9 4 3 2 6 4 3 8 1
8 9 1 7 7 4 9 2 3
3 5 4 6 1 6 3 5 6
1 2 7 5 7 3 8 9 6
3 5 5 9 2 7 7 7 4
6 3 5 1 4 4 2 1 3
7 1 6 8 4 2 8 6 7
2 8 6 5 9 1 2 5 8
Fitness is 59

--- i==8

Chrom cs[i]:
2 9 7 9 5 4 9 7 1
5 4 3 2 6 6 4 8 9
5 6 1 4 4 4 9 2 9
3 6 4 1 1 6 3 5 8
1 2 7 5 7 3 3 9 6
3 5 7 9 2 6 7 1 1
6 3 5 1 8 3 2 4 3
7 1 8 7 4 2 8 6 2
2 8 8 5 9 5 8 8 7
Fitness is 61

--- i==9

Chrom cs[i]:
2 9 7 9 5 4 9 7 1
7 4 3 2 6 6 8 8 8
9 7 1 7 9 4 9 2 8
3 5 4 5 1 6 3 5 8
1 2 7 5 7 3 4 9 6
3 5 6 4 2 4 7 3 1
6 3 5 1 1 6 2 5 4
7 1 3 8 4 2 8 6 9
2 8 8 5 9 6 2 3 1
Fitness is 65

--- i==10

---

Any help ?

BUMP.