fork download 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <time.h>
  5. #include <math.h>
  6. #include <stdbool.h>
  7.  
  8. #define SIZE        9      // rozmiar planszy
  9. #define BLOCK       3      // rozmiar bloku 3x3
  10.  
  11. // parametry GA
  12. #define POP_SIZE    200    // liczebnosc populacji
  13. #define MAX_GEN     5000   // maksymalna liczba generacji
  14. #define TOURN_SIZE  3      // liczba w turnieju
  15. #define CROSS_RATE  0.05    // prawdopodobienstwo krzyzowania
  16. #define MUT_RATE    0.05    // prawdopodobienstwo mutacji
  17.  
  18. #define REPORT_GEN 50      // raport co
  19.  
  20. // dane sudoku, 0 = puste pole
  21. int puzzle[SIZE][SIZE] = {
  22.     {5,3,0, 0,7,0, 0,0,0},
  23.     {6,0,0, 1,9,5, 0,0,0},
  24.     {0,9,8, 0,0,0, 0,6,0},
  25.  
  26.     {8,0,0, 0,6,0, 0,0,3},
  27.     {4,0,0, 8,0,3, 0,0,1},
  28.     {7,0,0, 0,2,0, 0,0,6},
  29.  
  30.     {0,6,0, 0,0,0, 2,8,0},
  31.     {0,0,0, 4,1,9, 0,0,5},
  32.     {0,0,0, 0,8,0, 0,7,9}
  33. };
  34.  
  35. // struktura jednego osobnika
  36. typedef struct {
  37.     int grid[SIZE][SIZE]; // wartosci w komorkach
  38.     int fitness;          // ocena dopasowania
  39. } Individual;
  40.  
  41. // deklaracje funkcji
  42. void entry_individual(Individual *ind);
  43. int  evaluate_fitness(const Individual *ind);
  44. Individual* tournament_selection(Individual pop[]);
  45. void crossover(const Individual *p1, const Individual *p2,
  46.                Individual *c1, Individual *c2, int generation);
  47. void mutate(Individual *ind, int generation);
  48. void do_sudoku_ga(void);
  49. void print_individual(const Individual *ind);
  50. void print_iteration(int gen, const Individual *best);
  51.  
  52. // losowa liczba z przedzialu [a,b]
  53. static int rand_range(int a, int b) {
  54.     return a + rand() % (b - a + 1);
  55. }
  56.  
  57. // inicjalizacja osobnika: uzupelnienie pustych pol w blokach 3x3
  58. void entry_individual(Individual *ind) {
  59.     bool fixed[SIZE][SIZE] = {false};
  60.     // skopiuj stale wart
  61.     for (int i = 0; i < SIZE; i++) {
  62.         for (int j = 0; j < SIZE; j++) {
  63.             ind->grid[i][j] = puzzle[i][j];
  64.             fixed[i][j] = (puzzle[i][j] != 0);
  65.         }
  66.     }
  67.     // wypełnij kazdy blok
  68.     for (int br = 0; br < BLOCK; br++) {
  69.         for (int bc = 0; bc < BLOCK; bc++) {
  70.             bool present[SIZE+1] = {false};
  71.             // zaznacz juz obecne wartosci
  72.             for (int di = 0; di < BLOCK; di++)
  73.             for (int dj = 0; dj < BLOCK; dj++) {
  74.                 int v = ind->grid[br*BLOCK+di][bc*BLOCK+dj];
  75.                 if (v) present[v] = true;
  76.             }
  77.             int missing[SIZE], m = 0;
  78.             // zbierz brakujace
  79.             for (int v = 1; v <= SIZE; v++)
  80.                 if (!present[v]) missing[m++] = v;
  81.             // losowo przemieszaj brakujace
  82.             for (int x = m-1; x > 0; x--) {
  83.                 int y = rand() % (x+1);
  84.                 int tmp = missing[x]; missing[x] = missing[y]; missing[y] = tmp;
  85.             }
  86.             // wstaw w puste miejsca
  87.             int idx = 0;
  88.             for (int di = 0; di < BLOCK; di++)
  89.             for (int dj = 0; dj < BLOCK; dj++) {
  90.                 int r = br*BLOCK+di, c = bc*BLOCK+dj;
  91.                 if (!fixed[r][c]) ind->grid[r][c] = missing[idx++];
  92.             }
  93.         }
  94.     }
  95.     // oblicz fitness poczatkowy
  96.     ind->fitness = evaluate_fitness(ind);
  97. }
  98.  
  99. // ocena ile roznych liczb w kazdym wierszu i kolumnie
  100. int evaluate_fitness(const Individual *ind) {
  101.     int score = 0;
  102.     int row_cnt[SIZE+1], col_cnt[SIZE+1];
  103.     for (int i = 0; i < SIZE; i++) {
  104.         memset(row_cnt, 0, sizeof row_cnt);
  105.         memset(col_cnt, 0, sizeof col_cnt);
  106.         for (int j = 0; j < SIZE; j++) {
  107.             row_cnt[ind->grid[i][j]]++;
  108.             col_cnt[ind->grid[j][i]]++;
  109.         }
  110.         for (int v = 1; v <= SIZE; v++) {
  111.             if (row_cnt[v] > 0) score++;
  112.             if (col_cnt[v] > 0) score++;
  113.         }
  114.     }
  115.     return score;
  116. }
  117.  
  118. // selekcja turniejowa, najlepsze z TOURN_SIZE osobnikow
  119. Individual* tournament_selection(Individual pop[]) {
  120.     Individual *best = NULL;
  121.     for (int i = 0; i < TOURN_SIZE; i++) {
  122.         Individual *cand = &pop[rand() % POP_SIZE];
  123.         if (!best || cand->fitness > best->fitness) best = cand;
  124.     }
  125.     return best;
  126. }
  127.  
  128. // krzyzowanie swapuj losowo bloki 3x3 z CROSS_RATE %
  129. void crossover(const Individual *p1, const Individual *p2,
  130.                Individual *c1, Individual *c2, int generation) {
  131.     // skopiuj rodzicow
  132.     memcpy(c1->grid, p1->grid, sizeof p1->grid);
  133.     memcpy(c2->grid, p2->grid, sizeof p2->grid);
  134.     if ((double)rand()/RAND_MAX < CROSS_RATE) {
  135.         for (int br = 0; br < BLOCK; br++) {
  136.             for (int bc = 0; bc < BLOCK; bc++) {
  137.                 if (rand()%2) {
  138.                     // zamien blok
  139.                     for (int di = 0; di < BLOCK; di++)
  140.                     for (int dj = 0; dj < BLOCK; dj++) {
  141.                         int r = br*BLOCK+di, c = bc*BLOCK+dj;
  142.                         int tmp = c1->grid[r][c];
  143.                         c1->grid[r][c] = c2->grid[r][c];
  144.                         c2->grid[r][c] = tmp;
  145.                     }
  146.                 }
  147.             }
  148.         }
  149.     }
  150.     c1->fitness = evaluate_fitness(c1);
  151.     c2->fitness = evaluate_fitness(c2);
  152. }
  153.  
  154. // mutacja = w jednym bloku zamienia dwie losowe puste komorki
  155. void mutate(Individual *ind, int generation) {
  156.     if ((double)rand()/RAND_MAX >= MUT_RATE) return;
  157.     int br = rand_range(0, BLOCK-1), bc = rand_range(0, BLOCK-1);
  158.     int idxs[SIZE], m = 0;
  159.     for (int di = 0; di < BLOCK; di++)
  160.     for (int dj = 0; dj < BLOCK; dj++) {
  161.         int r = br*BLOCK+di, c = bc*BLOCK+dj;
  162.         if (puzzle[r][c] == 0) idxs[m++] = r*SIZE + c;
  163.     }
  164.     if (m < 2) return;
  165.     int a = idxs[rand()%m], b = idxs[rand()%m];
  166.     if (a != b) {
  167.         int r1 = a/SIZE, c1 = a%SIZE;
  168.         int r2 = b/SIZE, c2 = b%SIZE;
  169.         int tmp = ind->grid[r1][c1];
  170.         ind->grid[r1][c1] = ind->grid[r2][c2];
  171.         ind->grid[r2][c2] = tmp;
  172.         ind->fitness = evaluate_fitness(ind);
  173.     }
  174. }
  175.  
  176. // glowna petla
  177. void do_sudoku_ga(void) {
  178.     srand((unsigned)time(NULL));
  179.     Individual pop[POP_SIZE], newpop[POP_SIZE];
  180.     // inicjalizacja populacji
  181.     for (int i = 0; i < POP_SIZE; i++) entry_individual(&pop[i]);
  182.     Individual best = pop[0];
  183.  
  184.     for (int gen = 1; gen <= MAX_GEN; gen++) {
  185.         // aktualizacja najlepszego
  186.         for (int i = 0; i < POP_SIZE; i++)
  187.             if (pop[i].fitness > best.fitness) best = pop[i];
  188.         // raport co mniej jesli wystarczy
  189.         if (gen % REPORT_GEN == 0) print_iteration(gen, &best);
  190.         // tworzenie nastepnej populacji
  191.         for (int i = 0; i < POP_SIZE; i += 2) {
  192.             Individual *p1 = tournament_selection(pop);
  193.             Individual *p2 = tournament_selection(pop);
  194.             crossover(p1, p2, &newpop[i], &newpop[i+1], gen);
  195.             mutate(&newpop[i],   gen);
  196.             mutate(&newpop[i+1], gen);
  197.         }
  198.         memcpy(pop, newpop, sizeof pop);
  199.         // znaleziono idealne rozwiazanie
  200.         if (best.fitness == 2 * SIZE * SIZE) break;
  201.     }
  202.     // wynik
  203.     printf("\nFinal best fitness %d/%d\n", best.fitness, 2*SIZE*SIZE);
  204.     print_individual(&best);
  205. }
  206.  
  207. // wyswietlenie
  208. void print_individual(const Individual *ind) {
  209.     for (int i = 0; i < SIZE; i++) {
  210.         for (int j = 0; j < SIZE; j++)
  211.             printf("%d ", ind->grid[i][j]);
  212.         printf("\n");
  213.     }
  214. }
  215.  
  216. // raport
  217. void print_iteration(int gen, const Individual *best) {
  218.     printf("Gen %4d, best fitness=%3d\n", gen, best->fitness);
  219. }
  220.  
  221. int main(void) {
  222.     printf("GA Sudoku solver\n");
  223.     do_sudoku_ga();
  224.     return 0;
  225. }
Success #stdin #stdout 0.49s 5280KB
comments (?)
stdin 
/*  Berechnung des Hamming-Abstandes zwischen zwei 128-Bit Werten in 	*/
/*	einer Textdatei. 													*/
/*  Die Werte müssen auf einer separaten Zeile gespeichert sein			*/
/* 																		*/
/*	Erstellt: 17.5.2010													*/
/*  Autor: Thomas Scheffler												*/

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_SIZE 32

unsigned Hamdist(unsigned x, unsigned y)
{
  unsigned dist = 0, val = x ^ y;
 
  // Count the number of set bits
  while(val)
  {
    ++dist; 
    val &= val - 1;
  }
 
  return dist;
}



int main (void)
{
	char hex;
	int i;
	int a[ARRAY_SIZE];
	int b[ARRAY_SIZE];
	int hamDist = 0;
	FILE* fp;
	
	//Arrays mit 0 initialisieren
	for (i = 0; i < ARRAY_SIZE; ++i)
	{
  		a[i] = 0;
  		b[i] = 0;
	}

	
	fp = fopen("hex.txt","r");
	if (fp == NULL) 
	{
		printf("Die Datei hex.txt wurde nicht gefunden!");
		exit(EXIT_FAILURE);
	}

	i=0;
	printf("1.Zeile einlesen.\n");

 	while((hex=fgetc(fp))!='\n' && hex != EOF)
    {
        a[i]=strtol(&hex,0,16);
		i++;
    }
	i=0;
	printf("2.Zeile einlesen.\n");

 	while((hex=fgetc(fp))!='\n' && hex != EOF)
    {
    	b[i]=strtol(&hex,0,16);
        i++;
    }
	fclose(fp);

	printf("Hamming-Abweichung pro Nibble:\n");
	for (i = 0; i < ARRAY_SIZE; ++i)
	{
		printf ("%i\t%i\t%i\n",a[i],b[i],Hamdist(a[i],b[i]));
		hamDist += Hamdist(a[i],b[i]);
	}
	printf ("\nHamming-Abweichung der Hash-Werte:%d\n",hamDist);
}
stdout 
GA Sudoku solver
Gen   50, best fitness=147
Gen  100, best fitness=150
Gen  150, best fitness=151
Gen  200, best fitness=151
Gen  250, best fitness=151
Gen  300, best fitness=151
Gen  350, best fitness=153
Gen  400, best fitness=154
Gen  450, best fitness=156
Gen  500, best fitness=156
Gen  550, best fitness=156
Gen  600, best fitness=156
Gen  650, best fitness=156
Gen  700, best fitness=156
Gen  750, best fitness=156
Gen  800, best fitness=156
Gen  850, best fitness=156
Gen  900, best fitness=156
Gen  950, best fitness=156
Gen 1000, best fitness=156
Gen 1050, best fitness=156
Gen 1100, best fitness=156
Gen 1150, best fitness=156
Gen 1200, best fitness=156
Gen 1250, best fitness=156
Gen 1300, best fitness=156
Gen 1350, best fitness=156
Gen 1400, best fitness=156
Gen 1450, best fitness=156
Gen 1500, best fitness=156
Gen 1550, best fitness=156
Gen 1600, best fitness=156
Gen 1650, best fitness=156
Gen 1700, best fitness=156
Gen 1750, best fitness=156
Gen 1800, best fitness=156
Gen 1850, best fitness=156
Gen 1900, best fitness=158
Gen 1950, best fitness=158
Gen 2000, best fitness=158
Gen 2050, best fitness=160
Gen 2100, best fitness=160
Gen 2150, best fitness=160
Gen 2200, best fitness=160
Gen 2250, best fitness=160
Gen 2300, best fitness=160
Gen 2350, best fitness=160
Gen 2400, best fitness=160
Gen 2450, best fitness=160
Gen 2500, best fitness=160
Gen 2550, best fitness=160
Gen 2600, best fitness=160
Gen 2650, best fitness=160
Gen 2700, best fitness=160
Gen 2750, best fitness=160
Gen 2800, best fitness=160
Gen 2850, best fitness=160
Gen 2900, best fitness=160
Gen 2950, best fitness=160
Gen 3000, best fitness=160
Gen 3050, best fitness=160
Gen 3100, best fitness=160
Gen 3150, best fitness=160
Gen 3200, best fitness=160
Gen 3250, best fitness=160
Gen 3300, best fitness=160
Gen 3350, best fitness=160
Gen 3400, best fitness=160
Gen 3450, best fitness=160
Gen 3500, best fitness=160
Gen 3550, best fitness=160
Gen 3600, best fitness=160
Gen 3650, best fitness=160
Gen 3700, best fitness=160
Gen 3750, best fitness=160
Gen 3800, best fitness=160
Gen 3850, best fitness=160
Gen 3900, best fitness=160
Gen 3950, best fitness=160
Gen 4000, best fitness=160
Gen 4050, best fitness=160
Gen 4100, best fitness=160
Gen 4150, best fitness=160
Gen 4200, best fitness=160
Gen 4250, best fitness=160
Gen 4300, best fitness=160
Gen 4350, best fitness=160
Gen 4400, best fitness=160
Gen 4450, best fitness=160
Gen 4500, best fitness=160
Gen 4550, best fitness=160
Gen 4600, best fitness=160
Gen 4650, best fitness=160
Gen 4700, best fitness=160
Gen 4750, best fitness=160
Gen 4800, best fitness=160
Gen 4850, best fitness=160
Gen 4900, best fitness=160
Gen 4950, best fitness=160

Final best fitness 162/162
5 3 4 6 7 8 9 1 2 
6 7 2 1 9 5 3 4 8 
1 9 8 3 4 2 5 6 7 
8 5 9 7 6 1 4 2 3 
4 2 6 8 5 3 7 9 1 
7 1 3 9 2 4 8 5 6 
9 6 1 5 3 7 2 8 4 
2 8 7 4 1 9 6 3 5 
3 4 5 2 8 6 1 7 9
https://ideone.com/wQnfzI
language:
C (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!