// nqueen.cpp
// Glenn G. Chappell
// Version 2
// 25 Feb 2008
//
// For CS 311 Spring 2008
// Prints 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
// - - - -
// - - - -

// 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 board:
//
// - Q - -
// - - - Q
// Q - - -
// - - Q -


// nQueen_printBoard
// Given a board representing a full solution to the n-Queens problem,
//  print the board, as described above.
// Pre:
//     n > 0
//     b.size() == n
//     Each entry of b is in [0, n-1].
//     b, n represent a full solution to the n-Queens Problem (see
//      above).
// Post:
//     b has been printed to cout.
void nQueen_printBoard(const Board & b,
                       int n)
{
    for (int i = 0; i < n; ++i)
        cout << b[i] << " ";
    cout << endl;
}


// 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;
}


// nQueen_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.
void nQueen_recurse(Board & b,
                    int n)
{
    // BASE CASE
    if (b.size() == n)
    {
        // A full solution! Print it.
        nQueen_printBoard(b, n);
        return;
    }

    // RECURSIVE CASE
    // 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
            nQueen_recurse(b, n);  // Recursive call
            b.pop_back();          // Remove queen
        }
    }
}


// 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).
void nQueen(int n)
{
    Board emptyBoard;
    nQueen_recurse(emptyBoard, n);
}


// main
int main()
{
    while (true)
    {
        int n;
        cout << "n-Queen Solver" << endl;
        cout << "by Glenn G. Chappell" << endl;
        cout << "For CS 311" << endl;
        cout << endl;
        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 << endl;
        cout << "n-Queen Solutions for "
             << n << " x " << n << " board:" << endl;
        cout << "-----------------------" << endl;
        nQueen(n);
        cout << "-----------------------" << endl;
        cout << endl;
    }
}