1. ## 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```

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.

3. 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;```

4. 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);
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;
}```

5. 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```

6. Any help ?

BUMP.