1. ## GA nasty bug

Hi,

I am back at my Sudoku Genetic Algorithm. I made a bit of progress. But there is a nasty bug that I can not find it to fix. Please help me. Not that cross-overs and mutations are under development for now. Here is the code:

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 21 15 19 10 11 9
static const int MAX_GEN = 200;//10; 60 120 40 100 200 500
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; // TODO can be removed ?

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(const Chrom_struct, Chrom_struct *const base_ptr);
static void print_chrom_callee(Chrom_struct ch);
void print_prob_callee(const Gen_prob_struct );
int difference(const Chrom_struct first, const Chrom_struct second);
int random_0to8(void);
void replace_two_rows(Chrom_struct * const, const Chrom_struct);
void replace_two_columns(Chrom_struct * const);//, const Chrom_struct);
void single_rotate(cell_t * const nine_cells) ;
//void rotate_row (Chrom_struct * const cs_ptr);
Chrom_struct rotate_row (Chrom_struct const cs_ptr);
//void correctly_derived(const Chrom_struct, const Chrom_struct); // bool

#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)\

#define  correctly_derived(cs, base)\
do{\
int cd_row,cd_col;\
for( cd_row=0;cd_row<=8;cd_row++)\
for( cd_col=0;cd_col<=8;cd_col++)\
{\
cell_t bcell=base.cell[cd_row][cd_col];\
cell_t cscell=cs.cell[cd_row][cd_col];\
if(bounded(bcell) && (bcell!=cscell))\
{\
printf("\$\$#\n");\
print_chrom(base);\
print_chrom(cs);\
printf("\$\$#\n");\
fatal_err("Missmatch, %s is not %s derived. row==%d col==%d",#cs,#base,cd_row,cd_col);\
}\
}\
} 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(const Chrom_struct original, Chrom_struct *const base_ptr) // TODO check it
{
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(bounded(original.cell[row2][col2])) // JA
//continue;
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(0)//if(cnt == 1) // One cell is single valued
{ // Would this conform to GA ?
// Bound the single value
uint8_t ffu=find_first_unbounded(possible_values,9);
res.cell[row][col]=ffu; // 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]++;
/*if(!correctly_derived(res,base)) // JA
{
print_chrom(base);
print_chrom(res);
fatal_err("rv");
}*/
correctly_derived(res,base);
//continue;

}

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

//assert(correctly_derived(base,original)); // JA
//assert(correctly_derived(res,base)); // JA
correctly_derived(base,original);
correctly_derived(res,base);

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);
//assert(correctly_derived(cs,base));
/*if(!correctly_derived(cs,base))
{
print_chrom(base);
print_chrom(cs);
fatal_err("cs base");
}*/
correctly_derived(cs,base);

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

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

for(cv2=1; cv2<=9; cv2++)//(cv2=9; cv2>=1; cv2--)//
{
if(cv2==cv)
continue;
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;
}

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

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);
//assert(correctly_derived(cs,base));
correctly_derived(cs,base);

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];
*/
for (int i = 0; i < 9; i++) // code from comp.lang.c
{
int k = (i + ind) % 9;
if (bounded(p[k]))
return p[k];
}
// assert() or fatal_error() call here as appropriate.
fatal_err("Wrongness");
return 0; // should not be called
}

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=0; i<10; i++) // i=1 i<=10
{
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);
//assert(correctly_derived(copy,base));
correctly_derived(copy,base);

// 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 b1=base.cell[mrow][mcol];
cell_t b2=base.cell[mrow2][mcol2];
if(bounded(b1) || bounded(b2))
continue;
}

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);
assert(!compare_chrom(copy,cs));
//assert(correctly_derived(cs,base));
/*if(!correctly_derived(cs,base))
{
print_chrom(cs);
print_chrom(base);
fatal_err("!correctly_derived");
}*/
correctly_derived(cs,base);

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 difference(const Chrom_struct first, const Chrom_struct second) // recently added for diversity
{
int diff_cnt=0;

int row=0;
int col=0;

for(row=0; row<9; row++)
for(col=0; col<9; col++)
{
if(first.cell[row][col] != second.cell[row][col])
diff_cnt++;
}

assert(diff_cnt>=0);
assert(diff_cnt<=81);
return diff_cnt;
}

int random_0to8(void) // returned unsigned
{
int rr;
double dr=ratio()*9.0;

for(rr=0;rr<dr;rr++)
continue;

rr--;

assert(rr>=0);
assert(rr<=8);
return rr;
}

void replace_two_rows(Chrom_struct * const cs_ptr , const Chrom_struct base) // two point cross-over
{
int r1,r2;
//int co_point = random_0to8(); // cross-over point
Chrom_struct copy=*cs_ptr;
//if(co_point==0) co_point=1;
//if(co_point==8) co_point=7;

//assert(correctly_derived(copy,base));
/*if(!correctly_derived(copy,base))
{
print_chrom(base);
print_chrom(copy);
fatal_err("c b ");
}*/
correctly_derived(copy,base);

do
{
r1=random_0to8();
r2=random_0to8();
}
while(r1==r2);
for(int i=0; i<=8; i++)
{
cell_t r1bcell = base.cell[r1][i];
cell_t r2bcell = base.cell[r2][i];
if(!bounded(r1bcell) && !bounded(r2bcell))
{
cell_t temp=cs_ptr->cell[r2][i];
cs_ptr->cell[r2][i]=cs_ptr->cell[r1][i];
cs_ptr->cell[r1][i]=temp;
}
}

//temp[i]=(cs_ptr)->cell[r2][i];
/*for(int i=0; i<=8; i++)
(cs_ptr)->cell[r2][i]=(cs_ptr)->cell[r1][i];

for(int i=0; i<=8; i++)
(cs_ptr)->cell[r1][i]=temp[i];*/

/*
do
{
r1=random_0to8();//random_row();
r2=random_0to8();//random_row();
}
while(r1==r2
|| (cs_ptr->cell[r1][0]==cs_ptr->cell[r2][0] )
|| (cs_ptr->cell[r1][8]==cs_ptr->cell[r2][8] )
);

cell_t temp1[9+1]= {ICV};
cell_t temp2[9+1]= {ICV};

for(int i=0; i<=8; i++)
{
if(i<=co_point)
{
temp1[i]=(cs_ptr)->cell[r1][i];
temp2[i]=(cs_ptr)->cell[r2][i];
}

else
{
temp1[i]=(cs_ptr)->cell[r2][i];
temp2[i]=(cs_ptr)->cell[r1][i];
}
}

for(int i=0; i<=8; i++)
{
(cs_ptr)->cell[r1][i]=temp1[i];
(cs_ptr)->cell[r2][i]=temp2[i];
}*/

count_ni(*cs_ptr);
//assert(correctly_derived(*cs_ptr,base));
Chrom_struct cs=*cs_ptr;
correctly_derived(cs,base);//(*cs_ptr,base);

return;
}

void replace_two_columns(Chrom_struct * const cs_ptr)// two point cross-over
{
int c1,c2;
int co_point = random_0to8(); // cross-over point
if(co_point==0) co_point=1;
if(co_point==8) co_point=7;

do
{
c1=random_0to8();//random_row();
c2=random_0to8();//random_row();
}
while(c1==c2
|| (cs_ptr->cell[0][c1]==cs_ptr->cell[0][c2])
|| (cs_ptr->cell[8][c1]==cs_ptr->cell[8][c2])
);

cell_t temp1[9+1]= {ICV};
cell_t temp2[9+1]= {ICV};

for(int i=0; i<=8; i++)
{
if(i<=co_point)
{
temp1[i]=(cs_ptr)->cell[i][c1];
temp2[i]=(cs_ptr)->cell[i][c2];
}
else
{
temp1[i]=(cs_ptr)->cell[i][c2];
temp2[i]=(cs_ptr)->cell[i][c1];
}
//temp[i]=(cs_ptr)->cell[i][c2];
}

/*for(int i=0; i<=8; i++)
(cs_ptr)->cell[i][c2]=(cs_ptr)->cell[i][c1];

for(int i=0; i<=8; i++)
(cs_ptr)->cell[i][c1]=temp[i];*/

for(int i=0; i<=8; i++)
{
(cs_ptr)->cell[i][c1]=temp1[i];
(cs_ptr)->cell[i][c2]=temp2[i];
}

count_ni(*cs_ptr);
return;
}

Chrom_struct rotate_row (Chrom_struct const cs)// single point cross-over
{
Chrom_struct ocs=cs; // output
int rr=random_0to8();
cell_t temp[9+1]={ICV};

for(int col=0; col<=8; col++)
temp[col]=ocs.cell[rr][col];

int rn=random_0to8(); // rotates number
if(rn==8)
rn=7;
for(rn++; rn>0; rn--) // was rn>=0
single_rotate(temp); // right rotate

for(int col=0; col<=8; col++)
ocs.cell[rr][col]=temp[col];

compute_fitness(&ocs);
count_ni(ocs);

if(compare_chrom(cs,ocs))
{
print_chrom(ocs);
fatal_err("rr==%d rn==%d\n",rr,rn);
}
return ocs;
}

void single_rotate(cell_t * const nine_cells) // single right rotate of a row
{
cell_t temp=nine_cells[8];

for(int i=8; i>0; i--)
nine_cells[i]=nine_cells[i-1];

nine_cells[0]=temp;
return;
}

/*
void  correctly_derived(const Chrom_struct cs, const Chrom_struct base)
{
//bool ic=false; // is correct
for(int row=0;row<=8;row++)
for(int col=0;col<=8;col++)
{
cell_t bcell=base.cell[row][col];
cell_t cscell=cs.cell[row][col];
if(bounded(bcell) && (bcell!=cscell))
{
//return false;
printf("\$\$#\n");
print_chrom(base);
print_chrom(cs);
printf("\$\$#\n");
fatal_err("Missmatch: cs is not base derivative.");
}
}
return ;//true;
}*/

// TODO have a diverse population for each generation
// TODO for instance: send the most distant(different) of population comparing to fittest to next generation untouched
// TODO revise crossover
// TODO do not change the value of initially bounded cells in mutation and cross-over(use correctly_derived() )
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}; // recent remove

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);
//assert(correctly_derived(s2,base));
correctly_derived(base,s1);
correctly_derived(s2,base);

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];
//assert(correctly_derived(cs[i],base));
correctly_derived(cs[i],s1);//base); s1 s2
correctly_derived(cs[i],base);
correctly_derived(base,s1);
}

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);
count_ni(fittest);
correctly_derived(fittest,s1);//s2);//,base); s1

// For rest of generations
for(int gen=2; gen<=MAX_GEN ; gen++) // was int gen=1  gen<MAX_GEN
{
// TODO inactivated , can be back:
/*current_gen=calc_gen_prob(base);
test_gen_prob(current_gen);

for(idx=(gen-1)*POPULATION; idx<(gen)*POPULATION; idx++) // was gen gen+1
{
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];
}*/

// TODO crossover:replace two distinct (rows)columns from one Chromeosome via ratio()
// TODO for single cross-over shift_rotate a row or column or region
for(int pop=5; pop<POPULATION; pop++)
{
Chrom_struct csc=cs[pop];
count_ni(cs[pop]);
correctly_derived(cs[pop],base);

double r=ratio();
if(r<0.333)//(r<0.5)
replace_two_rows(cs+pop,base);
else if(r<0.666)
replace_two_columns(cs+pop);
else
cs[pop]=rotate_row(cs[pop]);
//rotate_row(cs+pop);

if(compare_chrom(cs[pop],csc)) // TODO above replace and rotate functions do not work properly
{
print_chrom(csc);
fatal_err("gen==%d pop==%d r==%f same cs\n",gen,pop,r);
}
count_ni(cs[pop]);
//(cs+pop).cell
}

// stuff removed

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

Chrom_struct md = cs[0]; // most different
int md_cnt=difference(fittest,cs[0]);
for(int i2=0; i2<POPULATION; i2++)
{
int diff=difference(fittest,cs[i2]);
if(diff>md_cnt)
{

md=cs[i2];
md_cnt=diff;//difference(fittest,cs[i2]);
}
}

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

// TODO for mutations use compare chrome to assure of changes
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);
// printf("#4\n");
printf("#4\n");
// cs[4]=most_different( , fittest);
cs[4]=md;

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;
}```
Once part of output:

Code:
```\$\$#

Chrom base:
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 is 0

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

\$\$#

FILE:/home/mehdi/Documents/Code_Blocks_Projects/Sudoku_GA/Main.c
FUNCTION:main
LINE:1550
DATE:Aug 17 2019
TIME:15:39:18

ERROR:Missmatch, cs[pop] is not base derived. row==0 col==4

Process returned 1 (0x1)   execution time : 0.137 s
Press ENTER to continue.```

2. 3. When posting code, do not post your entire program if you only need help with one function. Post as little as possible. People are much more likely to read small amounts of code and help you, than they are to read a hundred lines of code.

5. For maximum response results, try to Ask Questions to Smart Way.

https://cboard.cprogramming.com/c-pr...uncements.html

3. Some thoughts.

1. You need to write code with tests written, or at least a plan for testing.
Test-driven development - Wikipedia
You need to know that your components work properly before you bring everything together.

2. Some functions are way too long, or way too deeply nested to ever be tested properly.

3. Your use of rand() / srand() is broken. Call srand() exactly ONCE at the start of main.

4. Your bloated macros make debugging impossible. There's no way to set a breakpoint in a macro.

5. Useless suffixes of _struct on names like Chrom_struct and Gen_prob_struct.

4. Originally Posted by Salem
1. You need to write code with tests written, or at least a plan for testing.
Test-driven development - Wikipedia
You need to know that your components work properly before you bring everything together.
*Like*

This one step will completely change the quality of your programmes

5. Originally Posted by Zeus_
3. When posting code, do not post your entire program if you only need help with one function. Post as little as possible. People are much more likely to read small amounts of code and help you, than they are to read a hundred lines of code.

5. For maximum response results, try to Ask Questions to Smart Way.

https://cboard.cprogramming.com/c-pr...uncements.html
Ok, considering the above code, let me narrow down the problem. I am very suspect of init() and correct_count() functions. Maybe bug is in them, but there is a strange phenomenon in main() function. see these parts:

Code:
```[...]

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

[...]```
So it seems the first generation passes the count_ni() and correctly_derived() tests. But usually in second generation as you see:

Code:
```[...]

for(int gen=2; gen<=MAX_GEN ; gen++) // was int gen=1  gen<MAX_GEN
{

for(int pop=5; pop<POPULATION; pop++)
{
Chrom_struct csc=cs[pop];
count_ni(cs[pop]);
correctly_derived(cs[pop],base);

[...]```
AS above I have a correctly_derived() error in short:

Code:
`ERROR:Missmatch, cs[pop] is not base derived. row==5 col==1`
You can refer to my original post in this thread for other functions. Note that the code is still on development, so I try to fix the bugs and after that I will try to improve over the code.