#define DBG

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


#define NMAX  50
#define NNMAX 395  /* = NMAX^2 - 5 */

struct {
	int x,y,d2,d3;
} a[NNMAX];
int inext[NNMAX];

struct {
	int x,y;
} f0[NMAX];

int t0[NMAX],     /* t0[c] = 0..n^2-7 */
    t1[NMAX],     /* t1[c] = 0..k     */
    t2[NMAX],     /* t2[c] = 0..k     */

    c0,c1,c2,
    d1_f0[NMAX+1], d1_f1[NMAX],   d1_f2[NMAX],
    d2_f0[2*NMAX], d2_f1[2*NMAX], d2_f2[2*NMAX],
    d3_f0[2*NMAX], d3_f1[2*NMAX], d3_f2[2*NMAX],

    k,n,                  /* 3k  in  n x n  */
    nmk,imax;

int not_end;

FILE *OUT, *data;
char out[20];

clock_t start;

#ifdef DBG
	unsigned long tf0,tf1;
#endif

void init(void);
void FASE0(void);
void FASE1(void);
void FASE2(void);
void print_sol(void);
void to_exit(void);
void quit(int);
int  read_data(void);
void write_data(void);
void clear_data(void);

int main(int argc, char *argv[])
{
#ifdef DBG
	tf0=tf1=0;
	if (argc==1) { n=8; k=8; OUT=NULL; }
	else
#endif
	if (argc<3) {
		printf("Usage: %s n k [file]\n", argv[0]);
		return 0;
	} else {
		n=atoi(argv[1]);
		k=atoi(argv[2]);
		if (argc>=4) OUT=fopen(strcpy(out,argv[3]),"w");
		        else OUT=NULL;
	}
	
	signal(SIGINT,quit); /* trap ctrl-c call quit fn */
	not_end=1;

	start = clock();

	if (!read_data()) {
	   init();
	   c0=0;
	   t0[0]=-1;
	}

	FASE0();
	to_exit();
	
	return 0;
}

void init(void)
{
	int i,ix,iy,in;

	k--;
	nmk=n-k;
	i=0;
	in = n-3 -2;
	for (iy=2; iy<=n-3; iy++) {
		a[i].x =0;
		a[i].y =iy;
		a[i].d2=iy-2;
		a[i].d3=-iy+n-3;
		inext[i++]=in;
	}
	in+= n-2 -1 +1;
	for (iy=1; iy<=n-2; iy++) {
		a[i].x =1;
		a[i].y =iy;
		a[i].d2=1+iy-2;
		a[i].d3=1-iy+n-3;
		inext[i++]=in;
	}
        for (ix=2; ix<=n-3; ix++) {
		in+= n-1 +1;
		for (iy=0; iy<=n-1; iy++) {
			a[i].x =ix;
			a[i].y =iy;
			a[i].d2=ix+iy-2;
			a[i].d3=ix-iy+n-3;
			inext[i++]=in;
		}
	}
	in+= n-2 -1 +1;
	for (iy=1; iy<=n-2; iy++) {
		a[i].x =n-2;
		a[i].y =iy;
		a[i].d2=n-2+iy-2;
		a[i].d3=n-2-iy+n-3;
		inext[i++]=in;
	}
	in+= n-3 -2 +1;
	for (iy=2; iy<=n-3; iy++) {
		a[i].x =n-1;
		a[i].y =iy;
		a[i].d2=n-1+iy-2;
		a[i].d3=n-1-iy+n-3;
		inext[i++]=in;
	}
	a[i].y = n;
	a[i].d2= 2*n-5;
	a[i].d3= 2*n-5;
	imax=i;

	for (i=0; i<=n; i++) d1_f0[i] = 0;
	for (i=0; i<=2*n; i++) { d2_f0[i] = 0; d3_f0[i] = 0; }
	/* implies that:
	 *     d1_f0[a[imax]].y  is 0
	 * and d1_f0[a[imax]].d2 is 0
	 * and d1_f0[a[imax]].d3 is 0
	 */
}

void FASE0(void)
{
	int i;

	while (not_end) {
		do t0[c0]++; while (d1_f0[a[t0[c0]].y]  ||
		   		    d2_f0[a[t0[c0]].d2] ||
				    d2_f0[(a[t0[c0]].d2+n)%(2*n-1)-1] || 
				    d3_f0[(a[t0[c0]].d3+n)%(2*n-1)-1] || 
				    d3_f0[a[t0[c0]].d3]);

		if (t0[c0]<imax && nmk>a[t0[c0]].x-c0) {	/*   nmk is n-k;   */
			d1_f0[a[t0[c0]].y ]++;
			d2_f0[a[t0[c0]].d2]++;
			d3_f0[a[t0[c0]].d3]++;
				    

			if (c0<k) {
				c0++;
				t0[c0]=inext[t0[c0-1]];
				continue;			/*   goto "while (not_end)"   */
			} else {
				for (i=0; i<=k; i++) {
					f0[i].x=a[t0[i]].x;
					f0[i].y=a[t0[i]].y;
				}
				FASE1();
			}
		} else {
			t0[c0]=inext[t0[c0]];
			c0--;
			if (c0<0) {			/*   no solution    */
			   clear_data();	
			   return;			/*   exit FASE0()   */
			}
		}

		d1_f0[a[t0[c0]].y ]--;
		d2_f0[a[t0[c0]].d2]--;
		d3_f0[a[t0[c0]].d3]--;
			
	}
	write_data();
}


void FASE1(void)
{
	int i;
	for (i=0; i<n; i++)
		d1_f1[i] = d1_f0[i];
	for (i=0; i<2*n; i++) {
		d2_f1[i] = d2_f0[i];
		d3_f1[i] = d3_f0[i];
	}

	#ifdef DBG
	tf0++;
	#endif

	c1=0;
	t1[c1]=-1;

	for (;;) {
		do t1[c1]++;
		while (t1[c1]<=k &&
		       (d1_f1[         f0[t1[c1]].y    ] !=1 ||
			d2_f1[f0[c1].x+f0[t1[c1]].y-2  ] !=1 ||
		        d3_f1[f0[c1].x-f0[t1[c1]].y+n-3] !=1 ||
			t1[c1]==c1)
		      );

		if (t1[c1]<=k) {
			d1_f1[         f0[t1[c1]].y    ]++;
			d2_f1[f0[c1].x+f0[t1[c1]].y-2  ]++;
			d3_f1[f0[c1].x-f0[t1[c1]].y+n-3]++;

			if (c1<k) {
				c1++;
				t1[c1]=-1;
				continue;			/*   goto "for (;;)"   */
			} print_sol(); /* aqui mandaba a fase 2 */
		} else {
			t1[c1]=-1;
			c1--;
			if (c1<0) return;			/*   exit FASE1()   */
		}

		d1_f1[         f0[t1[c1]].y    ]--;
		d2_f1[f0[c1].x+f0[t1[c1]].y-2  ]--;
		d3_f1[f0[c1].x-f0[t1[c1]].y+n-3]--;
	}
}


void FASE2(void)
{
	int i;
	for (i=0; i<n; i++)
		d1_f2[i] = d1_f1[i];
	for (i=0; i<2*n-5; i++) {
		d2_f2[i] = d2_f1[i];
		d3_f2[i] = d3_f1[i];
	}

	#ifdef DBG
	tf1++;
	#endif

	c2=0;
	t2[c2]=-1;

	for(;;) {
		do t2[c2]++;
		while (t2[c2]<=k &&
		       (d1_f2[         f0[t2[c2]].y    ] !=1 ||
		        d2_f2[f0[c2].x+f0[t2[c2]].y-2  ] !=1 ||
		        d3_f2[f0[c2].x-f0[t2[c2]].y+n-3] !=1 ||
		    	t2[c2]==c2 || t2[c2]==t1[c2])
		       );

		if (t2[c2]<=k) {
			d1_f2[         f0[t2[c2]].y    ]++;
			d2_f2[f0[c2].x+f0[t2[c2]].y-2  ]++;
			d3_f2[f0[c2].x-f0[t2[c2]].y+n-3]++;

			if (c2<k) {
				c2++;
				t2[c2]=-1;
				continue;			/*   goto "for (;;)"   */
			} else print_sol(); /*EUREKA*/

		} else {
			t2[c2]=-1;
			c2--;
			if (c2<0) return;			/*   exit FASE2()   */
		}

		d1_f2[         f0[t2[c2]].y    ]--;
		d2_f2[f0[c2].x+f0[t2[c2]].y-2  ]--;
		d3_f2[f0[c2].x-f0[t2[c2]].y+n-3]--;
	}
}


char p[NMAX][NMAX+1];
void print_sol(void)
{
	int i,j;
	char c;

	for (i=0; i<n; i++) {
	  for (j=0; j<n; j++) p[i][j]='-';
	  p[i][j]='\0';
	}

	for (i=0; i<=c0; i++)
	  p[a[t0[i]].x][a[t0[i]].y]='0';
  	for (i=0; i<=c1; i++)
	  p[a[t0[i]].x][a[t0[t1[i]]].y]='1';
	for (i=0; i<=c2; i++)
	  p[a[t0[i]].x][a[t0[t2[i]]].y]='2';

	if (OUT) {
		for (i=0; i<n; i++) fprintf(OUT,"%s\n",p[i]);
 		fprintf(OUT,"\n");
	} else {
		for (i=0; i<n; i++) printf("%s\n",p[i]);
		printf("\n");
	}

	if ( (c=getchar())=='e' || c=='E') {
		printf("Exit at user request\n");
		exit(0);
	}
}

void to_exit(void)
{
#ifdef DBG
	printf("%lu\t%lu\n",tf0,tf1);
#endif
	printf("%f seconds\n",
           ((double)clock()-(double)start)/(double)CLOCKS_PER_SEC);
	if (OUT) fclose(OUT);
}

void quit(int dummy)
{
  printf("ctrl-c caught, please wait.\n\n");
  not_end=0;
}

void write_data(void)
{
	printf("Saving computations.\n\n");

	data=fopen("trifig.dat","wb");

	fwrite(&n,	sizeof(int), 1,		data);
	fwrite(&k,	sizeof(int), 1, 	data);
	if (OUT) {
		fprintf(data,"%s\n",out);
		fclose(OUT);
	}

	fwrite(d1_f0,	sizeof(int), NMAX+1, 	data);
	fwrite(d1_f1,	sizeof(int), NMAX, 	data);
	fwrite(d1_f2,	sizeof(int), NMAX, 	data);

	fwrite(d2_f0,	sizeof(int), 2*NMAX, 	data);
	fwrite(d2_f1,	sizeof(int), 2*NMAX, 	data);
	fwrite(d2_f2,	sizeof(int), 2*NMAX, 	data);

	fwrite(d3_f0,	sizeof(int), 2*NMAX, 	data);
	fwrite(d3_f1,	sizeof(int), 2*NMAX, 	data);
	fwrite(d3_f2,	sizeof(int), 2*NMAX, 	data);

	fwrite(f0,	2*sizeof(int), NMAX,	data);

	fwrite(t0,	sizeof(int), NMAX, 	data);
	fwrite(t1,	sizeof(int), NMAX, 	data);
	fwrite(t2,	sizeof(int), NMAX,	data);

	fwrite(&c0,	sizeof(int), 1,		data);
	fwrite(&c1,	sizeof(int), 1,		data);
	fwrite(&c2,	sizeof(int), 1,		data);

#ifdef DBG
	fwrite(&tf0,	sizeof(int), 1,		data);
	fwrite(&tf1,	sizeof(int), 1,		data);
#endif

	fclose(data);
}

int read_data(void)
{
	int nn,kk;

	if (access("trifig.dat",0)==0)
	   data=fopen("trifig.dat","rb");
	else
	   return 0;

	fread(&nn,	sizeof(int), 1,		data);
	fread(&kk,	sizeof(int), 1,		data);
	
	if (nn!=n || kk!=k-1) {
	   fclose(data);
	   return 0;
	}

	printf("Resuming a previously stopped computation... \n\n");
	
	if (OUT) {
		fscanf(data,"%s",out);
		OUT=fopen(out,"w");
	}

	init();

	fread(d1_f0,	sizeof(int), NMAX+1, 	data);
	fread(d1_f1,	sizeof(int), NMAX, 	data);
	fread(d1_f2,	sizeof(int), NMAX, 	data);

	fread(d2_f0,	sizeof(int), 2*NMAX, 	data);
	fread(d2_f1,	sizeof(int), 2*NMAX, 	data);
	fread(d2_f2,	sizeof(int), 2*NMAX, 	data);

	fread(d3_f0,	sizeof(int), 2*NMAX, 	data);
	fread(d3_f1,	sizeof(int), 2*NMAX, 	data);
	fread(d3_f2,	sizeof(int), 2*NMAX, 	data);

	fread(f0,       2*sizeof(int), NMAX,	data);

	fread(t0,	sizeof(int), NMAX,	data);
	fread(t1,	sizeof(int), NMAX, 	data);
	fread(t2,	sizeof(int), NMAX, 	data);

	fread(&c0,	sizeof(int), 1,		data);
	fread(&c1,	sizeof(int), 1, 	data);
	fread(&c2,	sizeof(int), 1, 	data);

#ifdef DBG
	fread(&tf0,	sizeof(int), 1,		data);
	fread(&tf1,	sizeof(int), 1, 	data);
#endif

	fclose(data);

	return 1;
}

void clear_data(void)
{
	if (access("trifig.dat",0)==0) unlink("trifig.dat");
}