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

int q[14];

int sol[3][14];

int r = 0,
	d1 = 0,
	d2 = 0;

int solP = 0;

int n;

void gen_sol(int col) {
	if (col == n) {
		if (solP < 3)
			memcpy(sol[solP], q, sizeof(int) * n);
		++solP;
		return;
	}

//NOTE Just calculating the non-admisible rows for this col every time is slightly faster than the "keep track of used rows and diagonals" solution
// 	int oc = 0;
// 	for (int i(0); i < col; ++i) {
// 		oc |= 1<<q[i];
// 		oc |= 1<<(q[i] - (col - i));
// 		oc |= 1<<(q[i] + (col - i));
// 	}


	int i;
	for (i = 0; i < n; ++i) {
		if (!(r & 1<<i) && !(d1 & 1<<(n - col - 1 + i)) && !(d2 & 1<<(i + col))) {
			r |= 1<<i;
			d1 |= 1<<(n - col - 1 + i);
			d2 |= 1<<(i + col);
			
			q[col] = i;
			gen_sol(col + 1);

			r ^= 1<<i;
			d1 ^= 1<<(n - col - 1 + i);
			d2 ^= 1<<(i + col);
		}
	}
}

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

	// Every solution's reflection is also a valid solution, so for the first
	// calculate only the first n/2 arrangements.
	int max = n;
	if (6 != n) {
		max = (n + 1) / 2;
	}
	
	// This complication appears because the odd values of n. Think about
	// it for a while and it will become obvious.
	int temp;
	int i;
	for (i = 0; i < max; ++i) {
		temp = solP;

		r |= 1<<i;
		d1 |= 1<<(n - 1 + i);
		d2 |= 1<<(i);

		q[0] = i;
		gen_sol(1);

		r ^= 1<<i;
		d1 ^= 1<<(n - 1 + i);
		d2 ^= 1<<(i);
	}

	int j;
	for (i = 0; i < 3; ++i) {
		for (j = 0; j < n; ++j)
			printf("%d ", sol[i][j] + 1);
		printf("\n");
	}

	if ((n % 2 == 0) && (6 < n))
		solP *= 2;
	else if ((n % 2 == 1) && (n > 6))
		solP += temp;
	printf("%d\n", solP);

	return 0;
}