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);
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(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];
count_ni(cs[i]); // just added
//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);
printf("min_fitness==%u md_cnt==%d\n",min_fitness,md_cnt); // added
// 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: