// nqueencount.cpp
// Glenn G. Chappell
// 5 Oct 2009
//
// For CS 311 Fall 2009
// 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>
using std::vector;
#include <string>
using std::string;
using std::getline;
#include <sstream>
using std::istringstream;
#include <cstdlib>
using std::size_t;


typedef vector<int> BoardType;  // Holds queen loc's on a chessboard

// We represent a partial queen placement on a chessboard as a BoardType
// object (board) and an int (n). The int (n) gives the size of the
// chessboard. Thus, n = 8 means an 8 x 8 chessboard. Object board is a
// listing of the queen positions (columns) on 0 or more rows of the
// chessboard (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, with n = 4 means a 4 x 4 chessboard
// with queens in its first 2 rows. The queen in the row 0 (1st row) lies
// in column 1 (the 2nd square), and the queen in row 1 (2nd row) lies in
// column 3 (the 4th & last square). This is pictured below:
//
// +---+---+---+---+
// |   | Q |   |   |
// +---+---+---+---+
// |   |   |   | Q |
// +---+---+---+---+
// |   |   |   |   |
// +---+---+---+---+
// |   |   |   |   |
// +---+---+---+---+

// We print a queen arrangement by printing the position of the queen in
// each column. For example, "1 3 0 2" represents the following arrangement
// of queens on a 4x4 chessboard:
//
// +---+---+---+---+
// |   | Q |   |   |
// +---+---+---+---+
// |   |   |   | Q |
// +---+---+---+---+
// | Q |   |   |   |
// +---+---+---+---+
// |   |   | Q |   |
// +---+---+---+---+


// checkQueen
// Given a partial solution to the n-Queens Problem (see above), determine
//  whether a proposed new queen placement is acceptable, that is, if it
//  cannot attack any any of the existing queens. If there is no possible
//  attack, then the return value is true.
// Pre:
//     board represents a placement of non-attacking queens on an n x n
//      chessboard (see above).
//     board.size() < n.
//     board.size() <= newRow < n.
//     0 <= newCol < n.
// Post:
//     Return value is true if, when a new queen is placed in row newRow
//      and column newCol, this new queen cannnot attack any other queen
//      on the chessboard. False otherwise.
// Does not throw.
bool checkQueen(const BoardType & board,
                int n,
                int newRow,
                int newCol)
{
    for (int oldRow = 0; oldRow < int(board.size()); ++oldRow)
    {
        int oldCol = board[oldRow];

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

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

        // NE-SW diagonal attack from existing queen?
        if (newRow + newCol == oldRow + oldCol)
            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 solution to the n-Queens Problem (see above), returns
//  number of non-attacking placements of n queens that include the given
//  queens.
// Recursive.
// Pre:
//     n > 0.
//     board.size() <= n.
//     Each entry of board is in [0 .. n-1].
//     board represents a placement of non-attacking queens on an n x n
//      chessboard (see above).
// Post:
//     Return is the number of solutions to the n-Queens Problem that can
//      be formed based on the given partial solution (see above).
//     b is equal to the value of b when the function was called.
// Does not throw.
int nQueenCount_recurse(BoardType & board,
                        int n)
// NOTE: We can pass b by reference since the function always restores it
//  to the same state it was in when the function was called. Because the
//  correct execution of the function now depends on this fact, it has
//  been added to the postconditions.
{
    // BASE CASE
    if (board.size() == size_t(n))
    {
        // A full solution! It counts as 1; return that.
        return 1;
    }

    // RECURSIVE CASE
    int total = 0;  // Running total of full solutions found

    // Try each position in next row
    for (int newCol = 0; newCol < n; ++newCol)
    {
        // If we can add a queen in position newColumn in the next row ...
        if (checkQueen(board, n, int(board.size()), newCol))
        {
            // ... then do it, and recurse.
            board.push_back(newCol);   // Add new queen
            total += nQueenCount_recurse(board, n);  // Recursive call
            board.pop_back();          // Remove queen
        }
    }
    return total;
}


// nQueenCount
// Counts solutions to the n-Queens Problem (see above) for a chessboard
//  of the given size. Returns this number.
// Pre:
//     n > 0.
// Post:
//     Return is the number of n-Queen arrangements on a chessboard of
//      the given size (see above).
// Does not throw.
int nQueenCount(int n)
{
    BoardType emptyBoard;
    return nQueenCount_recurse(emptyBoard, n);
}


// inputLoop
// Repeats the following until the user inputs a non-positive integer:
//     - Prompts for n, the size of a chessboard.
//     - Prints all n-Queen solutions, as described above, for an
//       n x n board.
// Pre: None.
// Post:
//     Interaction and output has been performed, as described.
// Does not throw.
void inputLoop()
{
    while (true)
    {
        // Print explanation
        cout << "n-Queen Counter" << endl;
        cout << endl;

        // Prompt & input chessboard size, with retry on bad input
        int n;
        while (true)
        {
            bool foundError = false;
            cout << "Chessboard size (0 to quit)? ";
            string line;
            getline(cin, line);
            if (!cin)
            {
                if (cin.eof())      // End of file
                    return;
                cin.clear();
                cin.ignore();
                foundError = true;  // Bad input
            }
            else
            {
                istringstream is(line);
                is >> n;
                if (!is)
                    foundError = true;  // Bad read from string
            }

            if (!foundError)
                break;
            cout << endl;
            cout << "Try again" << endl;
        }
        if (n <= 0)
            return;

        // Print solutions to n-Queens Problem
        cout << endl;
        cout << "Number of n-Queen Solutions for "
             << n << " x " << n << " chessboard:" << endl;
        cout << nQueenCount(n) << endl;
        cout << endl;
    }
}


// main
// Repeatedly inputs a number n and prints all n-Queen solutions.
// Terminates on n == 0.
// Uses inputLoop.
int main()
{
    inputLoop();
    return 0;
}