experchange > c Sudoku Genetic Algorithm

 Mehdi Amini (01-11-19, 01:57 PM)
Hi,

I asked my question on cboard forum but got no help. Lets see if you can
help me. Link to forum:

Soon I will send my code on this newsgroup too.
 Mehdi Amini (01-11-19, 01:59 PM)
On 1/11/19 3:27 PM, Mehdi Amini wrote:
> Hi,
> I asked my question on cboard forum but got no help. Lets see if you can
> help me. Link to forum:
>
> Soon I will send my code on this newsgroup too.

// 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_struc t);
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;
}
// @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@ //
 Ben Bacarisse (01-11-19, 08:00 PM)
Mehdi Amini <atorrses> writes:
<snip code>

I assume you've compiled with lots of warnings turned on and checked
that none of the diagnostics loop suspicious (they do look OK to me at
first glance).

The next step is to compile and run with some sort of sanitiser or
memory checker. Both gcc's -fsanitize=undefined and valgrind report an
out of bounds access here:

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

That line does indeed look dodgy (though I'd need much more study to be
sure).
 Bart (01-11-19, 08:16 PM)
On 11/01/2019 18:00, Ben Bacarisse wrote:
> Mehdi Amini <atorrses> writes:
> <snip code>
> I assume you've compiled with lots of warnings turned on and checked
> that none of the diagnostics loop suspicious (they do look OK to me at
> first glance).
> The next step is to compile and run with some sort of sanitiser or
> memory checker. Both gcc's -fsanitize=undefined and valgrind report an
> out of bounds access here:
> That line does indeed look dodgy (though I'd need much more study to be
> sure).

My compiler tells me that ps.cell_prob has type:

'ref [9][10] double'

(Pointer to array 9 of array 10 of double.)

C rules say that applying three index ops to that should be fine
(otherwise it wouldn't compile), but it does appear a little odd -
usually pointer-to-array needs (*p) to dereference.
 Ben Bacarisse (01-11-19, 10:11 PM)
Bart <bc> writes:

> On 11/01/2019 18:00, Ben Bacarisse wrote:
> My compiler tells me that ps.cell_prob has type:
> 'ref [9][10] double'

In C, the type of the ps.cell_prob object is double [9][9][10].

> (Pointer to array 9 of array 10 of double.)

There's no & or sizeof operator here so ps.cell_prob converts to a
pointer to the first element of the array. That makes the /expression/
(rather than the object) have type double (*)[9][10]. You compiler is
probably reporting the type of the expression in this context rather
than the declared type of the object.

> C rules say that applying three index ops to that should be fine
> (otherwise it wouldn't compile),

Yes. The trouble is the out-of-bounds access.

(It turns out it was simpler than I thought it might be to confirm what
gcc -fsanitize=undefined was reporting. You made me go look at the
declaration, for which thanks.)

> but it does appear a little odd -
> usually pointer-to-array needs (*p) to dereference.

Not for 2D or higher arrays. They almost always involve a
pointer-to-array being indexed rather the referenced. The indexing
expression seen here is normal; the fact that i can be 10 is not.
 Mehdi Amini (01-12-19, 12:20 PM)
On 1/11/19 11:41 PM, Ben Bacarisse wrote:
[..]
> Not for 2D or higher arrays. They almost always involve a
> pointer-to-array being indexed rather the referenced. The indexing
> expression seen here is normal; the fact that i can be 10 is not.

is this one OK ?

[...]
for(int i=0; i<10; i++)
[...]
 Mehdi Amini (01-12-19, 12:28 PM)
On 1/11/19 3:29 PM, Mehdi Amini wrote:
> On 1/11/19 3:27 PM, Mehdi Amini wrote:

[...]

Strange occurrence about the code is that, before the function:

Chrom_struct correct_count(Chrom_struct, const Chrom_struct);

The placed numbers did not add to 9. Most of the time they had more or
less counts. In such situation the best fitness in the last generation
was about 6 to 10. Now after implementing correct_count function and
some more, best fitness is about 30. Is there any area to work so that
the problem is solved ? meaning all cells bounded and fitness is 0.
 Ben Bacarisse (01-12-19, 02:15 PM)
Mehdi Amini <atorrses> writes:

> On 1/11/19 11:41 PM, Ben Bacarisse wrote: <snip>
> is this one OK ?
> [...]
> for(int i=0; i<10; i++)
> [...]

It's in bounds, yes. But then there's another one in this function

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

caused by the fact that 'init' passes a 9-element array for 'p'. I'd
check every loop just to be sure you are using <= and/or <
appropriately. (I found these by using valgrind -- my favourite
debugging tool for C.)

By the way, that function looks a bit odd. The 'if' is only needed if
'ind' can be greater than 10 to start with. Maybe it is there for that
reason, but that's odd enough to deserve a comment. Also, if no element
satisfies 'bounded' the function indexes p[-1].

If the exact order is not important (as the function name suggests) you
could write it like this using the modulo operator:

for (int i = 0; i < 9; i++) {
int k = (i + ind) % 9;
if (bounded(p[k]))
return p[k];
}
// assert() or fatal_error() call here as appropriate.
 Mehdi Amini (01-14-19, 01:51 PM)
On 1/12/19 1:58 PM, Mehdi Amini wrote:
> On 1/11/19 3:29 PM, Mehdi Amini wrote:
>> On 1/11/19 3:27 PM, Mehdi Amini wrote:

[...]

Can someone suggest me a way to reduce "fitness" ? I can not find any
particular fault in this algorithm of the supplied code.
 minforth (01-14-19, 02:09 PM)
Perhaps this helps too:

Solving Sudokus is a nearly no-brainer in CLP. Years ago I wrote a solver
in BProlog, the code fit on a single A4 sheet.

But of course it is not genetic, but solved through backtracking in bounded
solution space defined by the rules of the game.
 Mehdi Amini (01-15-19, 01:09 PM)
On 1/14/19 3:39 PM, minforth wrote:
> Perhaps this helps too:
>

Hopefully will read this one later on.

> Solving Sudokus is a nearly no-brainer in CLP. Years ago I wrote a solver
> in BProlog, the code fit on a single A4 sheet.
> But of course it is not genetic, but solved through backtracking in bounded
> solution space defined by the rules of the game.

I learned to code in Visual Prolog and a bit in SWI Prolog too. I have a
Sudoku solver in C too, based on constraint satisfaction. Check:

 minforth (01-15-19, 08:19 PM)
Am Dienstag, 15. Januar 2019 12:09:55 UTC+1 schrieb Mehdi Amini Valashani son of Bahram:
> On 1/14/19 3:39 PM, minforth wrote:
> Hopefully will read this one later on.
> I learned to code in Visual Prolog and a bit in SWI Prolog too. I have a
> Sudoku solver in C too, based on constraint satisfaction. Check:
>
>
> --
>
> Farewell.

Thanks, but still rather big programs. FWIW here's the BProlog code.
It's just the board and the Sudoku rules and runs nevertheless - fantastic.

/*
Sudoku solver
*/

:- initialization(main).

main :-

Vars = [ % the board
X11,X12,X13, X14,X15,X16, X17,X18,X19,
X21,X22,X23, X24,X25,X26, X27,X28,X29,
X31,X32,X33, X34,X35,X36, X37,X38,X39,

X41,X42,X43, X44,X45,X46, X47,X48,X49,
X51,X52,X53, X54,X55,X56, X57,X58,X59,
X61,X62,X63, X64,X65,X66, X67,X68,X69,

X71,X72,X73, X74,X75,X76, X77,X78,X79,
X81,X82,X83, X84,X85,X86, X87,X88,X89,
X91,X92,X93, X94,X95,X96, X97,X98,X99 ],
Vars :: 1..9,

sudoku(Vars), % read puzzle

%row rules
alldifferent([X11,X12,X13, X14,X15,X16, X17,X18,X19]),
alldifferent([X21,X22,X23, X24,X25,X26, X27,X28,X29]),
alldifferent([X31,X32,X33, X34,X35,X36, X37,X38,X39]),

alldifferent([X41,X42,X43, X44,X45,X46, X47,X48,X49]),
alldifferent([X51,X52,X53, X54,X55,X56, X57,X58,X59]),
alldifferent([X61,X62,X63, X64,X65,X66, X67,X68,X69]),

alldifferent([X71,X72,X73, X74,X75,X76, X77,X78,X79]),
alldifferent([X81,X82,X83, X84,X85,X86, X87,X88,X89]),
alldifferent([X91,X92,X93, X94,X95,X96, X97,X98,X99]),

%column rules
alldifferent([X11,X21,X31, X41,X51,X61, X71,X81,X91]),
alldifferent([X12,X22,X32, X42,X52,X62, X72,X82,X92]),
alldifferent([X13,X23,X33, X43,X53,X63, X73,X83,X93]),

alldifferent([X14,X24,X34, X44,X54,X64, X74,X84,X94]),
alldifferent([X15,X25,X35, X45,X55,X65, X75,X85,X95]),
alldifferent([X16,X26,X36, X46,X56,X66, X76,X86,X96]),

alldifferent([X17,X27,X37, X47,X57,X67, X77,X87,X97]),
alldifferent([X18,X28,X38, X48,X58,X68, X78,X88,X98]),
alldifferent([X19,X29,X39, X49,X59,X69, X79,X89,X99]),

%block rules
alldifferent([X11,X12,X13, X21,X22,X23, X31,X32,X33]),
alldifferent([X14,X15,X16, X24,X25,X26, X34,X35,X36]),
alldifferent([X17,X18,X19, X27,X28,X29, X37,X38,X39]),

alldifferent([X41,X42,X43, X51,X52,X53, X61,X62,X63]),
alldifferent([X44,X45,X46, X54,X55,X56, X64,X65,X66]),
alldifferent([X47,X48,X49, X57,X58,X59, X67,X68,X69]),

alldifferent([X71,X72,X73, X81,X82,X83, X91,X92,X93]),
alldifferent([X74,X75,X76, X84,X85,X86, X94,X95,X96]),
alldifferent([X77,X78,X79, X87,X88,X89, X97,X98,X99]),

labeling(Vars),
writeln(Vars).

% ################################################## ###################

sudoku([ % Puzzle:
8,6,7, _,_,5, 9,1,_,
1,_,_, _,7,_, _,8,5,
_,3,_, _,_,_, _,_,_,

_,_,_, 7,6,2, 1,_,_,
_,8,_, _,9,_, _,6,_,
_,_,2, 8,1,4, _,_,_,

_,_,_, _,_,_, _,3,_,
9,1,_, _,3,_, _,_,6,
_,4,3, 1,_,_, 8,2,9
]).
 Mehdi Amini (01-17-19, 04:51 PM)
On 1/15/19 9:49 PM, minforth wrote:
[...]

My modified code for SWI Prolog. I tried this:

%:- initialization(main).
:- use_module(library(clpfd)).

main :-

Vars = [ % the board
X11,X12,X13, X14,X15,X16, X17,X18,X19,
X21,X22,X23, X24,X25,X26, X27,X28,X29,
X31,X32,X33, X34,X35,X36, X37,X38,X39,

X41,X42,X43, X44,X45,X46, X47,X48,X49,
X51,X52,X53, X54,X55,X56, X57,X58,X59,
X61,X62,X63, X64,X65,X66, X67,X68,X69,

X71,X72,X73, X74,X75,X76, X77,X78,X79,
X81,X82,X83, X84,X85,X86, X87,X88,X89,
X91,X92,X93, X94,X95,X96, X97,X98,X99 ],

% Vars :: 1..9,
ins(Vars,1..9),

sudoku(Vars), % read puzzle

% alldifferent
%row rules
all_distinct([X11,X12,X13, X14,X15,X16, X17,X18,X19]),
all_distinct([X21,X22,X23, X24,X25,X26, X27,X28,X29]),
all_distinct([X31,X32,X33, X34,X35,X36, X37,X38,X39]),

all_distinct([X41,X42,X43, X44,X45,X46, X47,X48,X49]),
all_distinct([X51,X52,X53, X54,X55,X56, X57,X58,X59]),
all_distinct([X61,X62,X63, X64,X65,X66, X67,X68,X69]),

all_distinct([X71,X72,X73, X74,X75,X76, X77,X78,X79]),
all_distinct([X81,X82,X83, X84,X85,X86, X87,X88,X89]),
all_distinct([X91,X92,X93, X94,X95,X96, X97,X98,X99]),

%column rules
all_distinct([X11,X21,X31, X41,X51,X61, X71,X81,X91]),
all_distinct([X12,X22,X32, X42,X52,X62, X72,X82,X92]),
all_distinct([X13,X23,X33, X43,X53,X63, X73,X83,X93]),

all_distinct([X14,X24,X34, X44,X54,X64, X74,X84,X94]),
all_distinct([X15,X25,X35, X45,X55,X65, X75,X85,X95]),
all_distinct([X16,X26,X36, X46,X56,X66, X76,X86,X96]),

all_distinct([X17,X27,X37, X47,X57,X67, X77,X87,X97]),
all_distinct([X18,X28,X38, X48,X58,X68, X78,X88,X98]),
all_distinct([X19,X29,X39, X49,X59,X69, X79,X89,X99]),

%block rules
all_distinct([X11,X12,X13, X21,X22,X23, X31,X32,X33]),
all_distinct([X14,X15,X16, X24,X25,X26, X34,X35,X36]),
all_distinct([X17,X18,X19, X27,X28,X29, X37,X38,X39]),

all_distinct([X41,X42,X43, X51,X52,X53, X61,X62,X63]),
all_distinct([X44,X45,X46, X54,X55,X56, X64,X65,X66]),
all_distinct([X47,X48,X49, X57,X58,X59, X67,X68,X69]),

all_distinct([X71,X72,X73, X81,X82,X83, X91,X92,X93]),
all_distinct([X74,X75,X76, X84,X85,X86, X94,X95,X96]),
all_distinct([X77,X78,X79, X87,X88,X89, X97,X98,X99]),

%labeling(Vars),
label(Vars),
writeln(Vars).

sudoku([ % Puzzle:
8,6,7, _,_,5, 9,1,_,
1,_,_, _,7,_, _,8,5,
_,3,_, _,_,_, _,_,_,

_,_,_, 7,6,2, 1,_,_,
_,8,_, _,9,_, _,6,_,
_,_,2, 8,1,4, _,_,_,

_,_,_, _,_,_, _,3,_,
9,1,_, _,3,_, _,_,6,
_,4,3, 1,_,_, 8,2,9
]).