// Execute as ./a.out 8
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define EMPTY '_'
#define QUEEN 'Q'

void print(int nq, char board[][nq]) {
	for (int ii = 0; ii < nq; ++ii) {
		for (int jj = 0; jj < nq; ++jj)
			putchar(board[ii][jj]), putchar(' ');
		putchar('\n');
	}
}
void init(int nq, char board[][nq], int row, int col) {
	if (row < nq) {
		if (col < nq) {
			board[row][col] = EMPTY;
			init(nq, board, row, col + 1);
		}
		init(nq, board, row + 1, 0);
	}
}
bool safeRow(int nq, char board[][nq], int row, int col) {
	// col is not necessary for this function, but helps to keep all function interfaces uniform.
	for (int jj = 0; jj < nq; ++jj)
		if (board[row][jj] == QUEEN) return false;
	return true;
}
bool safeCol(int nq, char board[][nq], int row, int col) {
	for (int ii = 0; ii < nq; ++ii)
		if (board[ii][col] == QUEEN) return false;
	return true;
}
bool safeDia(int nq, char board[][nq], int row, int col) {
	for (int ii = row - 1, jj = col - 1; ii >= 0 && jj >= 0; --ii, --jj) {
		if (board[ii][jj] == QUEEN) return false;
	}
	for (int ii = row - 1, jj = col + 1; ii >= 0 && jj < nq; --ii, ++jj) {
		if (board[ii][jj] == QUEEN) return false;
	}
	return true;
}
bool safe(int nq, char board[][nq], int row, int col) {
	// check that placing a queen at board[row][col] is safe or not
	return 
		safeRow(nq, board, row, col) &&
	    	safeCol(nq, board, row, col) &&
	    	safeDia(nq, board, row, col);
}
int solve(int nq, char board[][nq], int row, int col) {
	static int nsol = 0;
	static int nqadded = 0;

	if (row == nq) {
		if (nqadded == nq) {
			++nsol;
			printf("\nSolution %d:\n", nsol);
			print(nq, board);	// one solution
		} else {
			// not a solution.
		}
	} else {
		if (col == nq) {
			solve(nq, board, row + 1, 0);
		} else {
			if (safe(nq, board, row, col)) {
				board[row][col] = QUEEN;
				//printf("queen at %d,%d\n", row, col);
				//getchar();
				++nqadded;

				solve(nq, board, row + 1, 0);
				board[row][col] = EMPTY;
				//printf("emptied at %d,%d\n", row, col);
				--nqadded;
			}
			solve(nq, board, row, col + 1);
		}
	}
	return nsol;
}
int main(int argc, char	*argv[]) {
	int nq = atoi(argv[1]);
	char board[nq][nq];

	init(nq, board, 0, 0);
	//print(nq, board);
	solve(nq, board, 0, 0);

	return 0;
}