/*

LeetCode 51. nQueens

Hard

The n-queens puzzle is the problem of placing n queens on an n x n
chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens
puzzle. You may return the answer in any order.

Each solution contains a distinct board configuration of the n-queens'
placement, where 'Q' and '.' both indicate a queen and an empty space,
respectively.

Example 1:

 -----------------------        ----------------------- 
|     |     |     |     |      |     |     |     |     |
|     |  Q  |     |     |      |     |     |  Q  |     |
|-----|-----|-----|-----|      |-----|-----|-----|-----|
|     |     |     |     |      |     |     |     |     |
|     |     |     |  Q  |      |  Q  |     |     |     |
|-----|-----|-----|-----|      |-----|-----|-----|-----|
|     |     |     |     |      |     |     |     |     |
|  Q  |     |     |     |      |     |     |     |  Q  |
|-----|-----|-----|-----|      |-----|-----|-----|-----|
|     |     |     |     |      |     |     |     |     |
|     |     |  Q  |     |      |     |  Q  |     |     |
|-----|-----|-----|-----|      |-----|-----|-----|-----|


Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:
Input: n = 1
Output: [["Q"]]
 
Constraints:

1 <= n <= 9
-------------------------

For a given row,col another queen cannot be in that row or col as well
as any adjacent (including diagonal cell.

Diagonal indices
----------------------
        Col 0     Col 1     Col 2     Col 3
Row 0   (0,3)     (1,2)     (2,1)     (3,0)
Row 1   (1,4)     (2,3)     (3,2)     (4,1)
Row 2   (2,5)     (3,4)     (4,3)     (5,2)
Row 3   (3,6)     (4,5)     (5,4)     (6,3)

First number = diag1 (row + col) → tracks \ diagonals (main diagonals, top-left to bottom-right)
Second number = diag2 (row - col + (n-1)) → tracks / diagonals (anti-diagonals, top-right to bottom-left)

main diagonal, top-left to bottom right = row + col
-------------------------------------------
        Col 0     Col 1     Col 2     Col 3
Row 0   0         1         2         3
Row 1   1         2         3         4
Row 2   2         3         4         5
Row 3   3         4         5         6

anti-diagonals, top-right to bottom-left = (row-col) + (n-1)
-------------------------------------------
        Col 0     Col 1     Col 2     Col 3
Row 0   3         2         1         0
Row 1   4         3         2         1
Row 2   5         4         3         2
Row 3   6         5         4         3

*/

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

class Solution_bs {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));

        // bitsets sized to maximum needed (n <= 9 → 2*9-1 = 17 bits)
        backtrack(0, bitset<4>{}, bitset<4>{}, bitset<4>{}, n, board, result);
        return result;
    }

    void backtrack(int row,
                   bitset<4> cols,      // occupied columns
                   bitset<4> diag1,     // main diagonals (row + col)
                   bitset<4> diag2,     // anti-diagonals (row - col + n-1)
                   int n,
                   vector<string>& board,
                   vector<vector<string>>& result) {
        
        if (row == n) {
            string b; for (auto i: board) b += i;
            cout << "   result: " << b << endl;
            cout << "-----------------\n";
            
            result.push_back(board);
            return;
        }

        string s; for (auto& i: board) s += i;
        cout << format("backtrack: row: {} cols: {}  diag1: {} diag2: {} board: {}\n", row, cols.to_string(), diag1.to_string(), diag2.to_string(), s);
        
        // Available positions in current row
        bitset<4> available = ~ (cols | diag1 | diag2);
        available &= ((1ULL << n) - 1);   // mask only first n bits
        cout << "  available curr row: " << available << endl;
        
        // Try every possible column using bitset
        for (int col = 0; col < n; ++col) {
            if (available[col]) {          // O(1) check with bitset
                // Place queen
                board[row][col] = 'Q';
                string s; for (auto& i: board) s += i;
                cout << format("  Place Queen: row={} col={:<28} board: {} -> backtrack\n", row, col, s);
                
                // Update masks for next row
                cout << "  update  cols=" << (cols | (bitset<4>(1) << col)) << endl;                
                cout << "  update diag1=" << ((diag1 | (bitset<4>(1) << col)) << 1) << endl;
                cout << "  update diag2=" << ((diag1 | (bitset<4>(1) << col)) >> 1) << endl;
                backtrack(row + 1,
                          cols | (bitset<4>(1) << col),
                          (diag1 | (bitset<4>(1) << col)) << 1,
                          (diag2 | (bitset<4>(1) << col)) >> 1,
                          n, board, result);
                
                string ss; for (auto& i: board) ss += i;                
                cout << format("  return from backtrack row: {:<24} board: {}\n", row + 1, ss);

                // Backtrack
                board[row][col] = '.';
            }
        }
    }
};

class Solution_bs_with_Find_first {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        
        // bitsets sized to maximum needed (n <= 9 → 2*9-1 = 17 bits)
        backtrack(0, 0, bitset<32>{}, bitset<32>{}, n, board, result);
        return result;
    }
    
private:
    void backtrack(int row,
                   bitset<32> cols,
                   bitset<32> diag1,
                   bitset<32> diag2,
                   int n,
                   vector<string>& board,
                   vector<vector<string>>& result) {
        
        if (row == n) {
            result.push_back(board);
            return;
        }
        
        bitset<32> available = ~(cols | diag1 | diag2);
        available &= ((1ULL << n) - 1);
        
        // Iterate only over set bits (more efficient)
        while (available.any()) {
            // Find lowest set bit position
            int col = available._Find_first(); // The function _Find_first() is
                                               // a non-standard extension
                                               // provided by the GCC libstdc++
                                               // implementation of std::bitset
                                               // to return the position of the
                                               // first set bit.  It accepts no
                                               // parameters and returns an
                                               // integer representing the index
                                               // of the first 1; if no bits are
                                               // set, it returns the size of
                                               // the bitset.
            if (col >= n) break;
            
            board[row][col] = 'Q';
            
            backtrack(row + 1,
                      cols | (bitset<32>(1) << col),
                      (diag1 | (bitset<32>(1) << col)) << 1,
                      (diag2 | (bitset<32>(1) << col)) >> 1,
                      n, board, result);
            
            board[row][col] = '.';
            
            // Clear this bit
            available[col] = 0;
        }
    }
};

class Solution_vec {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> result;
        vector<string> board(n, string(n, '.'));
        
        // Tracking arrays
        vector<bool> cols(n, false);
        vector<bool> diag1(2 * n - 1, false);  // row + col
        vector<bool> diag2(2 * n - 1, false);  // row - col + n - 1
        
        backtrack(0, n, board, cols, diag1, diag2, result);
        return result;
    }
    
    void backtrack(int row, int n, vector<string>& board,
                   vector<bool>& cols,
                   vector<bool>& diag1,
                   vector<bool>& diag2,
                   vector<vector<string>>& result) {
        
        // Base case: all queens placed
        if (row == n) {
            string b;
            for (auto i: board) b += i;
            cout << "   result: " << b << endl;            
            result.push_back(board);
            cout << "-----------------\n";
            return;
        }

        string cols_str, d1_str, d2_str, b_str;
        for (auto i: cols) cols_str += (cols[i]==true ? "1" : "0");
        for (auto i: diag1) d1_str += (diag1[i]==true ? "1" : "0");
        for (auto i: diag2) d2_str += (diag2[i]==true ? "1" : "0");
        for (auto i: board) b_str += i;
        
        cout << format("backtrack: row: {} cols: {}  diag1: {} diag2: {} board {}\n", row, cols_str, d1_str, d2_str, b_str);

        for (int col = 0; col < n; ++col) {
            int d1 = row + col;
            int d2 = row - col + n - 1;
            
            // Check if safe
            if (cols[col] || diag1[d1] || diag2[d2]) {
                continue;
            }
            
            // Place queen
            board[row][col] = 'Q';
            cols[col] = diag1[d1] = diag2[d2] = true;
            string b_str; for (auto i: board) b_str += i;
            cout << format("       place Q: col: {} diag1: {} diag2: {}   board: {}\n", col, d1, d2, b_str);
            
            // Recur to next row
            backtrack(row + 1, n, board, cols, diag1, diag2, result);
            cout << "  return from backtrack row: " << row + 1 << "\n";
            
            // Backtrack
            board[row][col] = '.';
            cols[col] = diag1[d1] = diag2[d2] = false;
        }
    }
};

int main(void)
{
    vector<tuple<int, vector<vector<string>>>> testCases = {

        { 4, {{".Q..", "...Q", "Q...", "..Q."}, {"..Q.", "Q...", "...Q", ".Q.."}} },
    };
    
    // Solution_vec s;
    Solution_bs s;
    // Solution_bs_with_Find_first s;
    
    auto printVec = [](const vector<vector<string>>& v)
    {
        for (size_t i = 0; i < v.size(); i++)
        {
            for (size_t j = 0; j < v[i].size(); j++)
            {
                cout << v[i][j];
            }
            cout << endl;
        }
    };

    for (auto& tc: testCases)
    {
        cout << "----------- Start ----------------\n";
        int n = get<0>(tc);        
        vector<vector<string>> result = s.solveNQueens(n);        
        cout << "test case: n=" << n << endl;
        cout << ">>> expected: \n";
        const vector<vector<string>>& expected = get<1>(tc);
        printVec(expected);
        cout << ">>> result: \n";
        printVec(result);
        EXPECT_EQ(expected, result);        
    }


    cout << "-----  test available rows logic ------ " << endl;
    bitset<4> cols;      // occupied columns
    bitset<4> diag1;     // main diagonals (row + col)
    bitset<4> diag2;     // anti-diagonals (row - col + n-1)

    int n = 4;    
    vector<string> board(n, string(n, '.'));
    cout << "board: ";
    for (auto i: board) cout << i << " ";
    cout << endl;    

    int row = 0;    
    bitset<4> available = ~ (cols | diag1 | diag2);
    available &= ((1ULL << n) - 1);   // mask only first n bits
    cout << format("  available row[{}]: {}\n", row, available.to_string());
    
    return 0;
}