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

#define N 23
#define L 66

enum { up, left, down, right };

int board[L][L];
int num_up[N];
int num_left[N];
int num_down[N];
int num_right[N];
int num_flag[N+1];
int dir;
int start[5];
int *num[4];
int min;
time_t t0;

static void (*put[4])(int *);

void comb(int, int, int);

void display(void)
{
   int i, j;

   for (i = 0; i < L; i++) {
       for (j = 0; j < L; j++)
           if (board[i][j]) printf("%2d", board[i][j]);
           else             printf("  ");
       printf("\n");
   }
   printf("\n");
}

void take(int row, int col, int n)
{
   int i, j, a = row + n, b = col + n;

   for (i = row; i < a; i++)
       for (j = col; j < b; j++)
           board[i][j] = 0;
}

int check(int row, int col, int n)
{
   int i, j, a = row + n, b = col + n;

   for (i = row; i < a; i++)
       for (j = col; j < b; j++)
           if (board[i][j]) return 1;

   for (i = row; i < a; i++)
       for (j = col; j < b; j++)
           board[i][j] = n;
   return 0;
}

void search(int n)
{
   int i, j;

   for (; n > 0; n--)
       if (num_flag[n]) {
           for (i = L-n; i >= 0; i--)
               for (j = L-n; j >= 0; j--)
                   if (board[i][j] == 0 && check(i, j, n) == 0) {
                       search(n - 1);
                       take(i, j, n);
                   }
           return;
       }
   display();
   printf("  %.0f sec\n", difftime(time(NULL), t0));
   exit(0);
}

void put_right(int *num)
{
   int y, end = L - board[L-1][L-1];

   for (y = board[0][L-1]; y < end; y += *num++)
       if (check(y, L - *num, *num))
           goto BREAK;
   search(N);
BREAK:
   while (y > board[0][L-1]) {
       y -= *--num;
       take(y, L - *num, *num);
   }
}

void put_down(int *num)
{
   int x, len;

   for (x = board[L-1][0]; x < L; x += *num++)
       if (check(L - *num, x, *num))
           goto BREAK;
   dir = right;
   len = L - board[0][L-1] - board[L-1][L-1];
   comb(len < start[dir] ? len : start[dir], len, 0);
   dir = down;
BREAK:
   while (x > board[L-1][0]) {
       x -= *--num;
       take(L - *num, x, *num);
   }
}

void put_left(int *num)
{
   int y;

   for (y = board[0][0]; y < L; y += *num++)
       if (check(y, 0, *num))
           goto BREAK;
   dir = down;
   comb(start[dir], L - board[L-1][0], 0);
   dir = left;
BREAK:
   while (y > board[0][0]) {
       y -= *--num;
       take(y, 0, *num);
   }
}

void put_up(int *num)
{
   int x;

   for (x = 0; x < L; x += *num++)
       check(0, x, *num);
   dir = left;
   comb(start[dir], L - board[0][0], 0);
   dir = up;
   do {
       x -= *--num;
       take(0, x, *num);
   } while (x > 0);
}

void perm(int *a, int *num, int n)
{
   int i;

   if (n < 0) (put[dir])(a);
   else
       for (i = 0; i <= n; i++) {
           a[n] = num[i];
           num[i] = num[n];
           perm(a, num, n - 1);
           num[i] = a[n];
       }
}

void comb(int n, int len, int p)
{
   if (len == 0) {
       if (dir != right || num_flag[min]) {
           int x[N];
           start[dir + 1] = num[dir][0] - 1;
           perm(x, num[dir], p-1);
       }
       return;
   }
   for (len -= n; len <= (n-1)*n / 2; len++)
       if (n <= min) return;
       else if (num_flag[n]) {
           num_flag[num[dir][p] = n--] = 0;
           comb(len < n ? len : n, len, p + 1);
           num_flag[n + 1] = 1;
       }
       else n--;
}

int main(void)
{
   int i, len;

   t0 = time(NULL);

   for (i = 1; i <= N; i++)
       num_flag[i] = 1;

   num[up]    = num_up;
   num[down]  = num_down;
   num[right] = num_right;
   num[left]  = num_left;
   put[up]    = put_up;
   put[down]  = put_down;
   put[right] = put_right;
   put[left]  = put_left;

   dir = up;

   len = (N + N-1 + N-2 + N-3) * 2;
   for (min = N-4; len < L*4; min--)
       len += min;
   for (; min >= 0; min--)
       comb(N, L, 0);
   printf("NOT FOUND\n");
   printf("  %.0f sec\n", difftime(time(NULL), t0));
   return 0;
}