// License: Public Domain

#include <iostream>

// q[y] = x  => queen is at pos x,y
int q[8]; 

// used during putqueen to keep track of
// occupied rows
bool vacant[8] = {true,true,true,true,
		  true,true,true,true};

// solution counter
int sols = 0;

// prints solution from array q in a not-so-pretty format
void printresult()
{
	for (int y=0;y<8;y++) {
		for (int x=0;x<8;x++)
			if (q[y] == x)
				std::cout << "O";
			else
				std::cout << (((y ^ x)&1) ? "X" : ".");	
		std::cout << std::endl;

	}
	std::cout << std::endl;
}

// places a queen on row r, assuming that queens has been
// placed on all rows up to but not including r already
// and locations are stored in q and vacancy information is
// up-to-date
void putqueen(int r)
{
	if (r == 8) {
		printresult();
		sols++;
		return;
	}
	
	// try all columns for this queen
	for (int v=0;v<8;v++) {
		// but only vacant ones
		if (vacant[v]) {
			// and if it does not collide diagonally
			// with an already placed queen
			bool ok = true;
			for (int c=0;c<r;c++) {
				if (v - q[c] == r - c) {
					ok = false;
					break;
				} else
				if (v - q[c] == c - r) {
					ok = false;
					break;
				}
				
			}
			if (!ok)
				continue;

			// place queen and continue with next
			q[r] = v;
			vacant[v] = false;
			putqueen( r + 1 );
			vacant[v] = true; 
		}
	}

}

int main(char **argv, char argc)
{
	putqueen( 0 );
	std::cout << "Solutions = " << sols << std::endl;
	return 0;
}