/*set ts=4 ; autoindent */

using System;
/*
 * The classic n-queens problem 
 */
public class chessboard
{
	public int n;
	public int rows;
	public int[] positions;
	public bool[] columns;
	public bool[] diags;
	public bool[] counterdiags;
	/*
	 * Initialize an nxn chessboard with no queens
	 */
	public chessboard(int n)
	{
		this.n=n;
		rows=0; // no queens added yet
		positions = new int[n];
		columns = new bool[n];
  		diags = new bool[2*n-1];
		counterdiags = new bool[2*n-1];
  		for (int i = 0; i < n; i++) positions[i] = -1;
  		for (int i = 0; i < n; i++) columns[i] = false;
		for (int i = 0; i < 2*n-1; i++) 
		{
	    	diags[i] = false;
	    	counterdiags[i] = false;
		}   // no columns or diagonals covered yet
	}	
	public chessboard (chessboard q)
	{
		n=q.n;
		rows=q.rows;
		positions = new int[n];
		columns = new bool[n];
		diags = new bool[2*n-1];
		counterdiags = new bool[2*n-1];
		for (int i = 0; i < n; i++) positions[i] = q.positions[i];
		for (int i = 0; i < n; i++) columns[i] = q.columns[i];
		for (int i = 0; i < 2*n-1; i++) 
		{
			diags[i] = q.diags[i];
			counterdiags[i] = q.counterdiags[i];
		}  
	}
	public void addQueen(int pos)
	{
		positions[rows]=pos; 		// place queen in current row
		columns[pos]=true;			// cover the column
		diags[pos-rows+n-1]=true;	// cover the diagonal
		counterdiags[pos+rows]=true;// cover the counter diagonal
		rows++;						// advance to next row
	}
	public override String ToString()
	{
		String retval="";
		for(int i=0;i<this.n ; i++)
		{
			retval=retval+" _";
		}
		retval=retval+"\n";
		for (int row = 0; row < this.n; row++) 
		{		  
			for (int col = 0; col < this.n; col++) 
			{
				retval=retval+(col == this.positions[row] ? "|Q" : "|_");
			}
		    retval=retval+"|\n";
  		}
		return retval;
	}
	public int findSolutions() 
	{
		if (this.rows == this.n) // if the board is complete...
	  	{ 		 
			Console.WriteLine(this.ToString());
			return 1;     // and count it
		}
		// else, recursively count solutions from here
		int count = 0;  // how many solutions
		for (int pos = 0; pos < this.n; pos++) 
		{
		    if (!this.columns[pos] && !this.diags[pos-this.rows+this.n-1] 
    	                   && !this.counterdiags[pos+this.rows]) 
			{
				chessboard newboard=new chessboard(this);
				newboard.addQueen(pos); // add queen to new board
				count += newboard.findSolutions();
    		}
		}
	  return count;
	}
	public static void Main()
	{
		chessboard a =new chessboard(8);
		Console.WriteLine(a.findSolutions()+" solutions ......");
	}
}