#define N 9
#include <bits/stdc++.h>
using namespace std;

typedef struct{double r[N];} rowOf;

void cpyMatrix(rowOf a[], rowOf b[]){
    for(int r = 0; r < N; r++){
        a[r] = b[r];
    }
}

double matrixEval(rowOf matrix[]){
    double det = 1;

    for(int i = 0; i < N; i++){
        bool found = false;
        for(int row = i; row < N; row++){
            if(matrix[row].r[i] != 0){
                if(row != i){
                    rowOf temp = matrix[row];
                    matrix[row] = matrix[i];
                    matrix[i] = temp;
                }
                found = true;
                break;
            }
        }
        if(!found){
            det = 0;
            break;
        }
        det *= matrix[i].r[i];
        for(int row = i + 1; row < N; row++){
            double coff = matrix[row].r[i] / matrix[i].r[i];
            for(int j = i; j < N; j++){
                matrix[row].r[j] -= coff * matrix[i].r[j];
                if (abs(matrix[row].r[j]) < 10e-11)
                    matrix[row].r[j] = 0;
            }
        }
    }
    return det;
}

int main(){
    cout << hex;
    srand(time(NULL));

    int maxOfMax = 0;
    string matrixString = "134278569569341827827695134298456371371982645645713298416837952783529416952164783";

    // random_shuffle(matrixString.begin(), matrixString.end());

    rowOf matrix[9], maxMatrix[9], matrixCopy[9], matrixSave[9];

    int iteration = 0;

    int r = 0, c = 0;

    for(char& num : matrixString){
        matrix[r].r[c] = (double)(num - '0');
        cout << matrix[r].r[c] << ' ';
        r++;
        if (r == N){
            r = 0;
            c += 1;
        }
    }

    pair<int, int> bestSwap = make_pair(-1,-1), lastSwap;
    while(maxOfMax < 0x3704d007){
        int maxVal = 0;
        for(int limit = 0; limit < N; limit++){
            for(int i = limit * N; i < (limit + 1) * N; i++){
                for(int j = i + 1; j < (limit + 1) * N; j++){
                    if(matrix[i / N].r[i % N] == matrix[j / N].r[j % N]) continue;

                    cpyMatrix(matrixCopy, matrix);

                    matrixCopy[i / N].r[i % N] = matrix[j / N].r[j % N];
                    matrixCopy[j / N].r[j % N] = matrix[i / N].r[i % N];

                    cpyMatrix(matrixSave, matrixCopy);

                    int det = ceil(matrixEval(matrixCopy));

                    if(abs(det) > maxVal){
                        bool latin = true;

                        for(int index = 0; index < N; index++){

                            set<double> row;
                            set<double> col;

                            for(int x = 0; x < N; x++){
                                row.insert(matrixSave[index].r[x]);
                                col.insert(matrixSave[x].r[index]);
                            }
                            if(row.size() != N || col.size() != N){
                                latin = false;
                                break;
                            }
                        }
                        if(!latin){
                            maxVal = abs(det);
                            cpyMatrix(maxMatrix, matrixSave);
                            bestSwap = make_pair(i, j);
                        }
                    }
                }
            }

        }

        cpyMatrix(matrix, maxMatrix);

        if(lastSwap == bestSwap){
            cout << iteration++ << endl;
            if(maxVal > maxOfMax){
                for(auto& row : matrix){
                    for(auto& a : row.r){
                        cout << a;
                    }
                }

                cout << '\n';

                for(auto& row : matrix){
                    for(auto& a : row.r){
                        cout << a << ' ';
                    }
                    cout << '\n';
                }
                cout << "iteration: " << iteration << " " << maxOfMax << ' ' << maxVal << '\n';
                maxOfMax = maxVal;
            }

            int row = rand() % N;

            for(int i = 0; i < N; i ++){
                int swap = rand() % 9;
                double temp = matrix[row].r[i];
                matrix[row].r[i] = matrix[row].r[swap];
                matrix[row].r[swap] = temp;
            }
        }

        lastSwap = bestSwap;
    }
}