/*
 * Name: Owen Sullivan
 * Date Submitted: 11/14/22
 * Lab Section: 006
 * Assignment Name: Lab 9: Using Recursion to Solve the N-Queens Problem
*/

#include <iostream>
#include <vector>

using namespace std;

// Function to check if a row is occupied (already has a queen placed)
bool isRowOccupied(const vector<vector<int>> &board, const int &n, const int &row) {

    bool occupied = false;

    // Loop through each space in the row
    for (int pos = 0; pos < n; pos++) {

        // If a queen is found, stop looping
        if (board.at(row).at(pos)) {

            occupied = true;
            break;

        }
        
    }

    // Will return true if queen is found, false if not
    return occupied;

}

// Function to check if upper left diagonal space is occupied (already has a queen placed)
bool isUpperDiagonalOccupied(const vector<vector<int>> &board, const int &n, const int &row, const int &col) {

    bool occupied = false;

    // Loop through diagonal spaces by starting at the bottom row and the bottom
    // of the current column, then decrementing looping variables together
    for (int yPos = row, xPos = col; yPos >= 0 && xPos >= 0; yPos--, xPos--) {

        // If a queen is found, stop looping
        if (board.at(yPos).at(xPos)) {

            occupied = true;
            break;

        }

    }

    // Will return true if queen is found, false if not
    return occupied;

}

// Function to check if upper right diagonal space is occupied (already has a queen placed)
bool isLowerDiagonalOccupied(const vector<vector<int>> &board, const int &n, const int &row, const int &col) {

    bool occupied = false;

    // Loop through diagonal spaces by starting at the top row and the bottom of
    // the current column, then increment the row and decrement the column
    for (int yPos = row, xPos = col; yPos < n && xPos >= 0; yPos++, xPos--) {
        
        // If a queen is found, stop looping
        if (board.at(yPos).at(xPos)) {

            occupied = true;
            break;

        }

    }

    // Will return true if queen is found, false if not
    return occupied;

}

bool isSpaceOccupied(const vector<vector<int>> &board, const int &n, const int &row, const int &col) {

    bool occupied = false;

    // Check if current row is occupied
    if (isRowOccupied(board, n, row)) {

        occupied = true;

    }

    // Check if upper diagonal space is occupied (works because queens are
    // placed starting in left-most column)
    if (isUpperDiagonalOccupied(board, n, row, col)) {

        occupied = true;

    }

    // Check if lower diagonal space is occupied (works because queens are
    // placed starting in left-most column)
    if (isLowerDiagonalOccupied(board, n, row, col)) {

        occupied = true;

    }

    // Will return true if queen is found, false if not
    return occupied;

}

int getSolutions(vector<vector<int>> &board, const int &n, const int &col) {

    int numSolutions = 0;

    // Recursive base case to check if the last column has been reached
    if (col == n) {

        // A solution should exist here if the row and left diagonals
        // are not occupied, so add one to the recursive count
        return 1;

    }

    // Loop through each row
    for (int pos = 0; pos < n; pos++) {

        // If the row and left diagonals are not occupied, a queen can be placed
        // without being attacked
        if (!isSpaceOccupied(board, n, pos, col)) {

            // Place the queen at the space
            board.at(pos).at(col) = 1;

            // Recursively get the number of solutions by checking the next
            // column
            numSolutions = numSolutions + getSolutions(board, n, (col + 1));

            // Remove the previously placed so as not to break future
            // row and left diagonal checks
            board.at(pos).at(col) = 0;

        }

    }

    return numSolutions;

}

// Uses recursion to count how many solutions there are for
// placing n queens on an nxn chess board
int nQueens(int n) {
    
    int total = 0;
    
    // Create a 2D vector of size n and initialize values to 0
    vector<vector<int>> board(n, vector<int>(n, 0));

    // Call recursive function from starting position of 0, 0 on board
    total = getSolutions(board, n, 0);

    return total;

}

// int main() {
    
//     cout << "1: " << nQueens(1) << endl;
//     cout << "2: " << nQueens(2) << endl;
//     cout << "3: " << nQueens(3) << endl;
//     cout << "4: " << nQueens(4) << endl;
//     cout << "5: " << nQueens(5) << endl;
//     cout << "6: " << nQueens(6) << endl;
//     cout << "7: " << nQueens(7) << endl;
//     cout << "8: " << nQueens(8) << endl;
//     cout << "9: " << nQueens(9) << endl;
//     cout << "10: " << nQueens(10) << endl;
//     cout << "11: " << nQueens(11) << endl;
//     cout << "12: " << nQueens(12) << endl;
    
//     return 0;

// }