N-Queens

class Solution {
private:
    int boardSize;
    vector<vector<string>> resultSets;
    
    vector<string> generateBoard(vector<vector<char>> layout) {
        vector<string> chessboard;
        for (int i = 0; i < boardSize; ++i) {
            string row(layout[i].begin(), layout[i].end());
            chessboard.push_back(row);
        }
        return chessboard;
    }
    void placeQueens(int currentRow, unordered_set<int> diag,
                     unordered_set<int> antiDiag, unordered_set<int> columns,
                     vector<vector<char>> boardState) {
        if (currentRow == boardSize) {
            resultSets.push_back(generateBoard(boardState));
            return;
        }
        for (int currentCol = 0; currentCol < boardSize; ++currentCol) {
            int diagKey = currentRow - currentCol;
            int antiDiagKey = currentRow + currentCol;
            if (columns.count(currentCol) || diag.count(diagKey) ||
                antiDiag.count(antiDiagKey)) {
                continue;
            }
            columns.insert(currentCol);
            diag.insert(diagKey);
            antiDiag.insert(antiDiagKey);
            boardState[currentRow][currentCol] = 'Q';
            placeQueens(currentRow + 1, diag, antiDiag, columns, boardState);
            columns.erase(currentCol);
            diag.erase(diagKey);
            antiDiag.erase(antiDiagKey);
            boardState[currentRow][currentCol] = '.';
        }
    }
    
public:
    vector<vector<string>> solveNQueens(int n) {
        boardSize = n;
        vector<vector<char>> initialBoard(boardSize, vector<char>(boardSize, '.'));
        placeQueens(0, unordered_set<int>(), unordered_set<int>(),
                    unordered_set<int>(), initialBoard);
        return resultSets;
    }
};

The N-Queens problem is a classic algorithmic challenge that involves placing n queens on an n x n chessboard such that no two queens threaten each other. The provided C++ solution utilizes backtracking to explore possible valid queen placements and uses sets to track column, diagonal, and anti-diagonal attacks for efficient validation.

Key Components and their roles:

• generateBoard: Converts the current state of the chessboard from a 2D character array to a vector of strings representing each row.
• placeQueens: A recursive function that attempts to place queens row by row. It uses three hash sets (columns, diag, antiDiag) to check the feasibility of placing a queen in any column of the current row. The function inserts a queen if the current position is valid and recursively attempts to place the next queen.
• solveNQueens: Initializes the chessboard and starts the recursive placement of queens.

Backtracking Approach Explained:

1. Start from the first row and attempt to place a queen in each column.
2. For each placement, calculate the corresponding diagonal and anti-diagonal keys and check against the sets. If the placement is conflict-free, recursively attempt to place a queen in the next row.
3. If a queen is placed in the last row, convert the board layout into its string representation and add it to the result set.
4. Backtrack by removing the queen and trying the next possible column.
5. Continue this until all rows are tried.

Outcome:

The function solveNQueens returns all possible solutions as a vector of string vectors. Each inner vector represents a unique configuration of the chessboard. This approach efficiently explores all potential configurations while pruning invalid placements early through the use of sets, significantly reducing the number of possibilities to examine.

class NQueensSolver {
    private int dimension;
    private List<List<String>> results = new ArrayList<>();
    
    public List<List<String>> solveQueens(int n) {
        dimension = n;
        char[][] board = new char[dimension][dimension];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = '.';
            }
        }
    
        search(0, new HashSet<>(), new HashSet<>(), new HashSet<>(), board);
        return results;
    }
    
    private List<String> formatBoard(char[][] currentState) {
        List<String> formattedBoard = new ArrayList<>();
        for (int i = 0; i < dimension; i++) {
            formattedBoard.add(String.valueOf(currentState[i]));
        }
        return formattedBoard;
    }
    
    private void search(int row, Set<Integer> diagonal, Set<Integer> antiDiagonal, Set<Integer> columns, char[][] currentState) {
        if (row == dimension) {
            results.add(formatBoard(currentState));
            return;
        }
    
        for (int col = 0; col < dimension; col++) {
            int currDiagonal = row - col;
            int currAntiDiagonal = row + col;
    
            if (columns.contains(col) || diagonal.contains(currDiagonal) || antiDiagonal.contains(currAntiDiagonal)) {
                continue;
            }
    
            columns.add(col);
            diagonal.add(currDiagonal);
            antiDiagonal.add(currAntiDiagonal);
            currentState[row][col] = 'Q';
    
            search(row + 1, diagonal, antiDiagonal, columns, currentState);
    
            columns.remove(col);
            diagonal.remove(currDiagonal);
            antiDiagonal.remove(currAntiDiagonal);
            currentState[row][col] = '.';
        }
    }
}

The provided Java solution addresses the N-Queens problem, which involves placing N queens on an N x N chessboard so that no two queens threaten each other. The approach adopted in the solution uses backtracking, a common technique for solving constraint satisfaction problems.

Here's a concise breakdown of the code's functionality:

• Class and Variables: The NQueensSolver class contains an instance variable for the board dimension (dimension) and a list (results) to store all possible arrangements that meet the conditions.

• Method - solveQueens(int n):

  • Initializes the board with all cells set to '.' indicating that they are empty.
  • Calls the search method from the first row onwards to place the queens.

• Method - search(int row, Set<Integer> diagonal, Set<Integer> antiDiagonal, Set<Integer> columns, char[][] currentState):

  • Implements a recursive function to place a queen row by row.
  • Uses three sets to track which columns, diagonals, and anti-diagonals are threatened by previously placed queens.
  • If a queen is placed, it recursively attempts to place further queens in subsequent rows.
  • Backtracks by removing the queen and undoing the marks in the tracking sets when encountering a dead end.

• Method - formatBoard(char[][] currentState):

  • Converts the current state of the board configuration with queens into a list of strings to be added to the results.

This solution ensures an efficient exploration of all possible placements of queens, leveraging sets to quickly check and update the conditions required for a valid placement. The implementation efficiently manages the state without modifying the original board directly, using temporary structures to handle state during recursion.

int* columnMarkers;
int* majorDiagonal;
int* minorDiagonal;
char*** solutions;
char** chessboard;
int solutionsCount;
    
void search(int n, int row) {
    if (row == n) {
        char** boardCopy = (char**)malloc(n * sizeof(char*));
        for (int i = 0; i < n; ++i) {
            char* newRow = (char*)calloc(n + 1, sizeof(char));
            memcpy(newRow, chessboard[i], n);
            newRow[n] = '\0';
            boardCopy[i] = newRow;
        }
        solutions[solutionsCount++] = boardCopy;
        return;
    }
    for (int col = 0; col < n; ++col) {
        if (columnMarkers[col] || majorDiagonal[col - row + n - 1] || minorDiagonal[col + row])
            continue;
        columnMarkers[col] = majorDiagonal[col - row + n - 1] = minorDiagonal[col + row] = 1;
        chessboard[row][col] = 'Q';
        search(n, row + 1);
        chessboard[row][col] = '.';
        columnMarkers[col] = majorDiagonal[col - row + n - 1] = minorDiagonal[col + row] = 0;
    }
}
    
char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    solutionsCount = 0;
    if (n < 1) {
        *returnSize = 0;
        return NULL;
    }
    solutions = (char***)malloc(n * n * n * sizeof(char**));
    majorDiagonal = (int*)calloc(2 * n - 1, sizeof(int));
    minorDiagonal = (int*)calloc(2 * n - 1, sizeof(int));
    columnMarkers = (int*)calloc(n, sizeof(int));
    chessboard = (char**)malloc(n * sizeof(char*));
    for (int i = 0; i < n; ++i) {
        chessboard[i] = (char*)calloc(n + 1, sizeof(char));
        memset(chessboard[i], '.', n);
    }
    search(n, 0);
    *returnSize = solutionsCount;
    *returnColumnSizes = (int*)malloc(solutionsCount * sizeof(int));
    for (int i = 0; i < solutionsCount; ++i) {
        (*returnColumnSizes)[i] = n;
    }
    return solutions;
}

This comprehensive solution tackles the classic N-Queens problem using C programming language, focusing on a backtracking method to find all possible configurations where n queens can be positioned on an n x n chessboard without threatening each other. To achieve this, the solution employs arrays to track the status of columns and both diagonals for conflicts, while recursively placing queens on the board.

Here's how the solution works:

• Initialize arrays for column, major diagonal, and minor diagonal checks, which help in determining if a queen can be placed without conflict.

• Use recursion to attempt placing a queen in every column of each row until the board is either filled or deemed impossible for the current configuration. If a queen placement leads to a valid arrangement, the recursion proceeds to place a queen in the next row. If not, it backtracks to try new positions.

• When a valid solution is found (i.e., all queens are placed), a copy of the board configuration is saved. This ensures that each unique solution is recorded.

• Continue the search until all possible board configurations are explored for the given size.

• Return all collected solutions along with their count and the size of each board.

This solution is memory efficient and fast, able to dynamically allocate and deallocate resources as needed during the queen placement and backtracking process. Moreover, it ensures that all potential solutions are explored thoroughly by checking all constraints before placing a queen.

var queensSolver = function (n) {
    const results = [];
    const initBoard = Array.from({ length: n }, () => Array(n).fill("."));
    const generateBoard = (layout) => {
        const board = [];
        for (let i = 0; i < n; i++) {
            board.push(layout[i].join(""));
        }
        return board;
    };
    const placeQueens = (row, diagonals, antiDiagonals, columns, boardState) => {
        if (row === n) {
            results.push(generateBoard(boardState));
            return;
        }
        for (let col = 0; col < n; col++) {
            let diag = row - col;
            let antiDiag = row + col;
            if (
                columns.has(col) ||
                diagonals.has(diag) ||
                antiDiagonals.has(antiDiag)
            ) {
                continue;
            }
            columns.add(col);
            diagonals.add(diag);
            antiDiagonals.add(antiDiag);
            boardState[row][col] = "Q";
            placeQueens(row + 1, diagonals, antiDiagonals, columns, boardState);
            columns.delete(col);
            diagonals.delete(diag);
            antiDiagonals.delete(antiDiag);
            boardState[row][col] = ".";
        }
    };
    placeQueens(0, new Set(), new Set(), new Set(), initBoard);
    return results;
};

The provided JavaScript function, queensSolver, solves the N-Queens problem, where the goal is to place n queens on an n x n chessboard so that no two queens threaten each other. The function returns all possible solutions as an array of boards, each represented as a list of strings.

• The function starts by initializing an empty board (using dots "." to signify empty spaces) and creating separate sets to track the columns, diagonals, and anti-diagonals on which queens have been placed. This helps in checking if a cell is attacked by any queen.
• Next, it defines placeQueens, a recursive function, that attempts to place queens row by row:
  • If all rows are filled (row === n), it converts the current board state into a readable format using generateBoard and adds it to the results.
  • For each cell in the current row, it checks if placing a queen is valid (i.e., the column, diagonal, and anti-diagonal are not already threatened by another queen).
  • If valid, it places a queen and recursively tries to place queens in the next row.
  • After returning from recursion, it backtracks by removing the queen and thus marking that position, column, diagonal, and anti-diagonal as free again.

The entire board search is initiated by calling placeQueens with the initial parameters and state. The solution set results, containing all valid configurations, is returned at the end. This approach efficiently explores all board configurations using backtracking, significantly decreasing the number of possibilities to examine by cutting off invalid paths early through the constraint checks.

class ChessSolution:
    def findNQueenSolutions(self, size):
        def build_board(configuration):
            board_layout = []
            for positions in configuration:
                board_layout.append("".join(positions))
            return board_layout
    
        def search_queens(c_row, diag, anti_diag, columns, current_state):
            if c_row == size:
                solutions.append(build_board(current_state))
                return
    
            for c in range(size):
                diag_id = c_row - c
                anti_diag_id = c_row + c
                if c in columns or diag_id in diag or anti_diag_id in anti_diag:
                    continue
    
                columns.add(c)
                diag.add(diag_id)
                anti_diag.add(anti_diag_id)
                current_state[c_row][c] = "Q"
    
                search_queens(c_row + 1, diag, anti_diag, columns, current_state)
    
                columns.remove(c)
                diag.remove(diag_id)
                anti_diag.remove(anti_diag_id)
                current_state[c_row][c] = "."
    
        solutions = []
        init_board = [["."] * size for _ in range(size)]
        search_queens(0, set(), set(), set(), init_board)
        return solutions

The N-Queens problem is a well-known challenge where the goal is to place N queens on an N×N chessboard so that no two queens threaten each other. The solution involves placing one queen in each row where none can attack another using vertical, horizontal, or diagonal movements.

The provided Python solution utilizes a backtracking algorithm encapsulated within a class ChessSolution. The findNQueenSolutions function is the primary method that finds all possible solutions for a given board size. Here's a breakdown of how the code works:

• Board Initialization:

  • An N×N board is initialized with all cells set to "." indicating an empty cell.

• Recursive Backtracking Function (search_queens):

  • This function attempts to place queens row by row. The current row is denoted by c_row.
  • For each column in the current row, the function checks if placing a queen there would lead to a conflict using three sets: columns, diag, and anti_diag. These sets track columns and diagonals already threatened by previously placed queens.
  • If a valid position is found, the queen is placed ("Q"), and the function recursively attempts to place the next queen.
  • After recursive calls, it backtracks by removing the queen and clearing the threats, thereby allowing for new possibilities.

• Building the Board Layout:

  • Once a valid configuration of queens is found for all rows, the build_board function converts the current state configuration into a list of strings representing the board configuration.

• Solution Collection:

  • All valid board configurations are collected into the list solutions.

When executed, the function findNQueenSolutions returns all possible solutions as a list of N×N boards, where each board is represented as a list of strings. This implementation efficiently explores all potential board configurations using backtracking, ensuring that all solutions satisfy the conditions of the N-Queens problem.