#include <stdio.h>
#include <string.h>

#define MAX_SIZE 10

int matrix[MAX_SIZE][MAX_SIZE];

int used[MAX_SIZE];

int neighbours[MAX_SIZE][MAX_SIZE];
bool neighbourPossible(int i, int j)
{
    return i != j && (i < j ? neighbours[i][j] : neighbours[j][i]) < 4;
}
void neighboursAdd(int i, int j)
{
    if (i < j)
        neighbours[i][j]++;
    else
        neighbours[j][i]++;
}
void neighboursRemove(int i, int j)
{
    if (i < j)
        neighbours[i][j]--;
    else
        neighbours[j][i]--;
}
    
int n;

void print_solution()
{
    char min_sol[MAX_SIZE*MAX_SIZE+1];
    bool first = true;
    for (int d = 0; d < 2; d++)
        for (int xd = 0; xd < 2; xd++)
            for (int yd = 0; yd < 2; yd++)
            {
                int map[MAX_SIZE];
                for (int i = 0; i < n; i++)
                    map[i] = -1;
                int nexti = 0;
                
                char sol[MAX_SIZE*MAX_SIZE+1];
                char *s = sol;
                for (int x = 0; x < n; x++)
                    for (int y = 0; y < n; y++)
                    {
                        int vx = xd == 0 ? x : n-1 - x;
                        int vy = yd == 0 ? y : n-1 - y;
                        int v = matrix[d == 0 ? vx : vy][d == 0 ? vy : vx];
                        if (map[v] == -1)
                            map[v] = nexti++;
                        *s++ = '0' + map[v];
                    }
                *s = '\0';
                if (first || strcmp(sol, min_sol) < 0)
                    strcpy(min_sol, sol);
                first = false;
            }
    printf("%s\n", min_sol);
}

void fill(int x, int y, int nr_used)
{
    if (x >= n)
    {
        x = 0;
        y++;
        if (y >= n)
        {
            print_solution();
            return;
        }
    }
    for (int i = 0; i < n && i < nr_used+1; i++)
        if (   used[i] < n
            && (x-1 < 0 || neighbourPossible(matrix[x-1][y], i))
            && (y-1 < 0 || neighbourPossible(matrix[x][y-1], i))
            && (x-1 < 0 || y-1 < 0 || matrix[x-1][y-1] != i)
            && (x+1 >= n || y-1 < 0 || matrix[x+1][y-1] != i)
           )
        {
            matrix[x][y] = i;
            used[i]++;
            if (x > 0)
                neighboursAdd(matrix[x-1][y], i);
            if (y > 0)
                neighboursAdd(matrix[x][y-1], i);
            fill(x+1, y, i >= nr_used ? i+1 : nr_used);
            if (x > 0)
                neighboursRemove(matrix[x-1][y], i);
            if (y > 0)
                neighboursRemove(matrix[x][y-1], i);
            used[i]--;
        }
}


void fill_all()
{
    for (int i = 0; i < n; i++)
        used[i] = 0;
    for (int i = 1; i < n; i++)
        for (int j = 0; j < i; j++)
            neighbours[j][i] = 0;
    fill(0, 0, 0);
}

int main(int argc, char* argv[])
{
    n = 6;
    fill_all();
    return 0;
}