// nqueencount.cpp
// Glenn G. Chappell
// 25 Feb 2008
//
// For CS 311 Spring 2008
// Counts solutions to the n-Queens Problem
// Example of Recursive Search with Backtracking


#include <iostream>
using std::cout;
using std::endl;
using std::cin;

#include <vector>  // for std::vector


typedef std::vector<int> Board;  // Type for "board"

// We represent a partial queen placement on a chessboard as a Board
// and an int. The int ("n") gives the size of the board. Thus, n = 8
// means an 8x8 chessboard. The Board is a listing of the queen
// positions (columns) on 0 or more rows of the board (at most n rows).
// There is at most one queen per row. Its position (column) is given
// by a number from 0 to n-1, inclusive.
//
// For example, a Board holding 1, 3 and n = 4 means a 4x4 board with
// queens in its first 2 rows. The queen in the row 0 (1st row) is in
// column 1 (the 2nd square), and the queen in row 1 (2nd row) is in
// column 3 (the 4th & last square). This is pictured below:
//
// - Q - -
// - - - Q
// - - - -
// - - - -

// nQueen_nonAttacking
// Given a partial board (see above), determine whether a proposed
//  new queen placement is non-attacking.
// Pre:
//     b represents a placement of non-attacking queens on an
//      nxn chessboard (see above).
//     b.size() < n.
//     newRow >= b.size().
// Post:
//     Return value is true if given board with a queen added in row
//      newRow and column newCol is a non-attacking arrangement
//      of queens; false otherwise.
bool nQueen_nonAttacking(const Board & b,
                        int n,
                        int newRow,
                        int newCol)
{
    for (int oldRow = 0; oldRow < b.size(); ++oldRow)
    {
        int oldCol = b[oldRow];

        // vertical attack from existing queen?
        if (newCol == oldCol)
            return false;

        // NW-SE diagonal attack from existing queen?
        if (newRow - oldRow == newCol - oldCol)
            return false;

        // NE-SW diagonal attack from existing queen?
        if (newRow - oldRow == oldCol - newCol)
            return false;

        // NOTE: We do not need to check for horizontal attacks,
        //  because of the assumption that there is at most one
        //  queen in each row.
    }
    return true;
}


// nQueenCount_recurse
// Given a partial board (see above), print out all non-attacking
//  placements of n queens that use the given queens.
// Recursive.
// Pre:
//     n > 0.
//     b.size() <= n.
//     Each entry of b is in [0 .. n-1].
//     b represents a placement of non-attacking queens on an
//      nxn chessboard (see above).
// Post:
//     All solutions printed (see above).
//     b is in the same state as when the function was called.
int nQueenCount_recurse(Board & b,
                        int n)
{
    // BASE CASE
    if (b.size() == n)
    {
        // A full solution! Return 1.
        return 1;
    }

    // RECURSIVE CASE
    int total = 0;  // Number of full solns based on given partial soln.
    // Try each position in next row
    int newRow = b.size();
    for (int newCol = 0; newCol < n; ++newCol)
    {
        // If we can add a queen in position newColumn in the next row ...
        if (nQueen_nonAttacking(b, n, newRow, newCol))
        {
            // ... then do it, and recurse.
            b.push_back(newCol);   // Add new queen
            total += nQueenCount_recurse(b, n);  // Recursive call
            b.pop_back();          // Remove queen
        }
    }
    return total;
}


// nQueen
// Prints all solutions to the n-Queens problem for a board of the given
//  size. That is, prints a representation of every placement of n
//  mututally non-attacking queens on an n x n board.
// Pre:
//     n > 0.
// Post:
//     All solutions printed (see above).
int nQueen(int n)
{
    Board emptyBoard;
    return nQueenCount_recurse(emptyBoard, n);
}


// main
int main()
{
    cout << "n-Queen Solution Counter" << endl;
    cout << "by Glenn G. Chappell" << endl;
    cout << "For CS 311" << endl;
    cout << endl;
    while (true)
    {
        int n;
        cout << "Board size? ";
        cin >> n;
        while (!cin || n <= 0)  // Bad input
        {
            if (!cin)
            {
                cin.clear();   // Reset cin for re-try of input
                cin.ignore();
            }
            cout << "Try again - Board size? ";
            cin >> n;
        }
        cout << "Number of n-Queen Solutions for "
             << n << " x " << n << " board: ";
        cout << nQueen(n) << endl;;
        cout << endl;
    }
}