#include <stdio.h>
#include <chrono>
// #define N	4

FILE *fin, *fout;
int N;
int numberOfSolutions = 0;

/* Check row traversal */
bool isSafeQ(int grid[13][13], int row, int col) {
	int i, j;

	/* Check row and column */
	for (i = 0; i < N; i++)
		if (grid[row][i] == 1 || grid[i][col] == 1)
			return false;

	/* Check first diag */
	for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
		if (grid[i][j] == 1)
			return false;

	/* Second */
	for (i = row, j = col; j <= N && i >= 0; i--, j++)
		if (grid[i][j] == 1)
			return false;
	return true;
}

void printSolution(int grid[13][13]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			char c = grid[i][j] == 1 ? 'Q' : '-';
			printf("%c ", c);
		}
		printf("\n");
	}
}

void printRowSolution(int grid[13][13]) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (grid[i][j] == 1) {
				//printf("%d ", j + 1);
				fprintf(fout, "%d ", j + 1);
			}
		}
	}
	//printf("\n");
	fprintf(fout, "\n");
}


bool solveQueens(int grid[13][13], int col) {

	if (col >= N) {
		printSolution(grid);
		return true;
	}

	for (int row = 0; row < N; row++) {
		if (isSafeQ(grid, row, col)) {
			grid[row][col] = 1;

			if (solveQueens(grid, col + 1))
				return true;

			grid[row][col] = 0;
		}
	}

	return false;
}

bool findAllSolutions(int grid[13][13], int row) {

	if (row >= N) {
		numberOfSolutions++;
		printf("Solution %d:\n", numberOfSolutions);
		printSolution(grid);

		if (numberOfSolutions == 1) {
			printRowSolution(grid);
		}

		return true;
	}

	for (int col = 0; col < N; col++) {
		if (isSafeQ(grid, row, col)) {
			grid[row][col] = 1;

			findAllSolutions(grid, row + 1);

			grid[row][col] = 0;
		}
	}

	return false;
}

/*
	Example for N == 4, first solution
x	x	Q	x
Q	x	x	x
x	x	x	Q
x	Q	x	x

(1, 0), (3, 1), (0, 2), (2, 3)
*/

int main(void) {
	fout = fopen("damesah.out", "w");
	fin = fopen("damesah.in", "r");
	fscanf(fin, "%d", &N);
	fclose(fin);

	int grid[13][13];

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			grid[i][j] = 0;

	

	auto start = std::chrono::high_resolution_clock::now();

	// Finding first solution
	//if (!solveQueens(grid, 0)) {
	//	printf("No solutions found..\n");
	//}

	// Finding ALL solutions
	findAllSolutions(grid, 0);
	if (numberOfSolutions == 0) {
		printf("No solutions found..\n");
	}

	fprintf(fout, "%d\n", numberOfSolutions);
	fclose(fout);

	auto end = std::chrono::high_resolution_clock::now();

	//printf("Time: %f ms\n", std::chrono::duration<double, std::milli>(end - start));

	return 0;
}