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