#include <stdio.h>
#include <chrono>
#define N	13

FILE *fin, *fout;
//int N;
int numberOfSolutions = 0;
int solution[13];

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; i <= N && j >= 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) {
				solution[i] = j + 1;
				// printf("%d ", solution[i]);
				//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 col) {

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

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

		return true;
	}

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

			findAllSolutions(grid, col + 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) {

	//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;
			solution[j] = 14;
		}

	

	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");
	}

	fout = fopen("damesah.out", "w");
	for (int i = 0; i < N; i++) {
		fprintf(fout, "%d ", solution[i]);
	}

	fprintf(fout, "\n%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;
}