123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103 |
- #include <stdio.h>
- #include <stdlib.h>
- #define SIZE 9
- #define SUM ((SIZE * (SIZE * SIZE + 1)) / 2)
- int data[SIZE][SIZE];
- void init() {
- for(int x = 0; x < SIZE; x++) {
- for(int y = 0; y < SIZE; y++) {
- data[x][y] = y * SIZE + x + 1;
- }
- }
- }
- int errorFactor(int e) {
- return e * e;
- }
- int getFitness() {
- int fitness = 0;
- for(int y = 0; y < SIZE; y++) {
- int sum = 0;
- for(int x = 0; x < SIZE; x++) {
- sum += data[x][y];
- }
- fitness += errorFactor(sum - SUM);
- }
- for(int x = 0; x < SIZE; x++) {
- int sum = 0;
- for(int y = 0; y < SIZE; y++) {
- sum += data[x][y];
- }
- fitness += errorFactor(sum - SUM);
- }
- int diaA = 0;
- int diaB = 0;
- for(int i = 0; i < SIZE; i++) {
- diaA += data[i][i];
- diaB += data[i][(SIZE - 1) - i];
- }
- fitness += errorFactor(diaA - SUM);
- fitness += errorFactor(diaB - SUM);
- return fitness;
- }
- void print() {
- printf("Fitness: %d\n", getFitness());
- for(int y = 0; y < SIZE; y++) {
- for(int x = 0; x < SIZE; x++) {
- printf("%2d ", data[x][y]);
- }
- putchar('\n');
- }
- putchar('\n');
- }
- void swap(int x1, int y1, int x2, int y2) {
- int tmp = data[x1][y1];
- data[x1][y1] = data[x2][y2];
- data[x2][y2] = tmp;
- }
- void randSwap() {
- swap(rand() % SIZE, rand() % SIZE, rand() % SIZE, rand() % SIZE);
- }
- void randSwaps(int swaps) {
- for(int i = 0; i < swaps; i++) {
- swap(rand() % SIZE, rand() % SIZE, rand() % SIZE, rand() % SIZE);
- }
- }
- int main() {
- init();
- for(int k = 0; k < 2000; k++) {
- for(int i = 0; i < 1000000; i++) {
- int oldFitness = getFitness();
- int x1 = rand() % SIZE;
- int y1 = rand() % SIZE;
- int x2 = rand() % SIZE;
- int y2 = rand() % SIZE;
- swap(x1, y1, x2, y2);
- int newFitness = getFitness();
- if(newFitness == 0) {
- break;
- }
- if(newFitness >= oldFitness) {
- swap(x1, y1, x2, y2);
- }
- }
- if(getFitness() == 0) {
- print();
- }
- randSwaps(400);
- }
- return 0;
- }
|