#include <iostream>
using namespace std;

#include "tmatrix.h"
#include "prompt.h"

class Queens
{
  public:
    Queens(int size);
    
    int Solve();
    
    void Print(ostream& out) const;
  private:
  
    bool NoQueensAttackingAt(int r, int c) const;
    int SolveAtCol(int col);
    tmatrix<bool> myBoard;
};

bool Queens::NoQueensAttackingAt(int r, int c) const
// pre: column c is clear
// post: return true if row clear and diagonals crossing at
//       (r,c) clear
{
    int k, row,col;

    // check row r
    for(k=0; k < myBoard.numcols(); k++) {
	if (k != c && myBoard[r][k]) return false;
    }

    // check diagonal northwest
    row = r-1; col = c-1;
    while (0 <= row && 0 <= col) {
	if (myBoard[row][col]) return false;
        row--; col--;
    }

    // check diagonal southeast
    row = r+1; col = c+1;
    while (row < myBoard.numrows() && col < myBoard.numcols()) {
	if (myBoard[row][col]) return false;
        row++; col++;
    }

    // check diagonal northeast
    row = r-1; col = c+1;
    while (0 <= row && col < myBoard.numcols()) {
	if (myBoard[row][col]) return false;
        row--; col++;
    }

    // check diagonal southwest
    row = r+1; col = c-1;
    while (row < myBoard.numrows() && 0 <= col) {
	if (myBoard[row][col]) return false;
        row++; col--;
    }
    
    return true;
}

Queens::Queens(int size)
  : myBoard(size,size,false)
// post: board initialized to hold no queens    
{ }

int Queens::Solve()
// post: returns true if n queens can be placed, false otherwise    
{
    int result = SolveAtCol(0);
    return result;
}

int Queens::SolveAtCol(int col)
// pre: queens placed at columns 0,1,...,col-1
// post: returns number of ways to place n queens
//       if col == size of board, then n queens are placed
{
    int k;
    int rows = myBoard.numrows();
    
    if (col == rows) {
//	Print(cout);
//	cout << "-----" << endl;
	return 1;
    }


    int count = 0;
    
    for(k=0; k < rows; k++) {
	if (NoQueensAttackingAt(k,col)) {  // row k is clear, try it
	    myBoard[k][col] = true;        // place the queen

	    count += SolveAtCol(col+1);    // how many ways?

            myBoard[k][col] = false;       // couldn't place, remove queen
        }
    }
    return count;
}

void Queens::Print(ostream& out) const
// post: board printed, 'X' for queen    
{
    int j,k;
    for(j=0; j < myBoard.numrows(); j++) {
	for(k=0; k < myBoard.numcols(); k++) {
	    out << (myBoard[j][k] ? 'X' : '.');
        }
        out << endl;
    }
}

int main()
{
    int size = PromptRange("size of board: ",2,100);
    
    Queens nq(size);

    int count = nq.Solve();
    cout << "# ways to place queens = " << count << endl;

    return 0;
}