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

#define LADY 0
#define NONE 1

int N;
int *solution;
int nr_solutions;
int printed;

int is_ok(int, int *, int);
void print_array(int *, int);

void backtrack(int position, int *solution, int N){
	int i = 0; 
	for (i = 0; i < N; ++i){
		solution[position] = i;
		if (is_ok(position, solution, N)){
			if (position != N-1){
				backtrack(position+1, solution, N);
			}else{
				//print
				nr_solutions++;
				if (!printed){
					print_array(solution, N);
					printed = 1;
				}
			}
		}
	}
}

int is_ok(int position, int *solution, int N){
	int i, j;
	if (position >  0){
		if (abs(solution[position-1] - solution[position]) <= 1){
			return 0; //FALSE
		}
	}
	if (position < N-1){
		if (abs(solution[position] - solution[position + 1]) <= 1){
			return 0; //FALSE
		}
	}
	return 1;//TRUE;
}

void print_array(int * array, int N){
	int i =0;
	FILE * out_file =fopen("damesah.out", "a+");
	for (i = 0; i < N; ++i){
		fprintf(out_file, "%d ", array[i]);
	}
	fprintf(out_file, "\n");
	fclose(out_file);
}

void print_nr_solutions(){
	FILE * out_file = fopen("damesah.out", "a+");
	fprintf(out_file, "%d\n", nr_solutions);
	fclose(out_file);
}

/*
 * Problema functioneaza astfel.
 * Pentru fiecare linie, tin minte coloana unde am pus regina intr-un array de "coloane unde am pus regine"
 * Conditia de validare este ca orice diferenta dintre "coloana unde am pus regina"
 * si vecinii din array-ul de "coloane unde am pus regine" sa fie mai mare ca 1"
 * pentru ca daca in array doua elemente alaturate au valori ce au diferenta
 * mai mica ca 1 inseamna ca se afla la cel mult o casuta distanta, deci se
 * vor bate reginele.
 */

int main(){
	FILE * file = fopen("damesah.in", "r");
	int i;
	
	if (file == NULL){
		perror("Inexistent file\n");
		return -1;
	}

	fscanf(file, "%d", &N);
	solution=(int *)calloc(N, sizeof(int));
	for (i = 0; i < N; ++i) solution[i] = -10;
	backtrack(0, solution, N);
	print_nr_solutions();
	return 0;
}