#include <stdio.h>

#define MAX_N 20

int queen_positions[MAX_N];
int col[MAX_N], first_diagonal[MAX_N * 2], secundary_diagonal[MAX_N * 2];
int number_of_solutions;
int n;
int found;

void backtrack(FILE *fout, int number_of_queens) {
	if (number_of_queens >= n) { //if we have the max queens
		if (number_of_solutions < 1) { // if it is first solution we print it
			for (int i = 0; i < n; i++)
				fprintf(fout, "%d ", queen_positions[i] +1);
			fprintf(fout, "\n");
		}
        //found = 1;
        //return;
		number_of_solutions++;
	}
	else {
		for (int i = 0; i < n; i++) { //for every row
			if (col[i] == 0 && first_diagonal[i - number_of_queens + n - 1] == 0 && secundary_diagonal[number_of_queens + i] == 0) {
				queen_positions[number_of_queens] = i;

                //We mark as used the column, first diagonal
				col[i] = 1;
				first_diagonal[i - number_of_queens + n - 1] = 1;
				secundary_diagonal[number_of_queens + i] = 1;

				backtrack(fout, number_of_queens + 1);

                /* I left this is for testing purpose, ignore it
                if(found == 1)
                {
                    return;
                }
                */

                //We deselect the used columns and diagonals
				col[i] = 0;
				first_diagonal[i - number_of_queens + n - 1] = 0;
				secundary_diagonal[number_of_queens + i] = 0;
			}
		}
	}
}

void read()
{
	FILE *fin;   //get a file
	fin = fopen("dame.in", "r"); //we open it for reading
	fscanf(fin, "%d", &n);
	fclose(fin);
	found = 0;

}

void print()
{
	FILE *fout;
	fout = fopen("dame.out", "w"); //open a file for writing

	backtrack(fout, 0);

	fprintf(fout, "%d\n", number_of_solutions); //write the number of solutions
	fclose(fout);
}

int main() {
    read();
    print();

    return 0;
}