52. N-Queens II

Problem link: https://leetcode.com/problems/n-queens-ii/ (opens new window)

The N-Queens problem is about placing n queens on an n×n chessboard in such a way that no two queens can attack each other.

Above is a solution for the 8-queens problem.

Given an integer n, return the number of distinct solutions to the n-queens problem.

Example:

Input: 4

Output: 2

Explanation: There are two distinct solutions to the 4-queens problem.

Solution 1

[ ["Q...", "...Q", "Q...", "..Q."],

Solution 2

["..Q.", "Q...", "...Q", ".Q.."] ]

Approach

For more details, see: 51.N-Queens (opens new window), which is basically the same.

class Solution {
private:
int count = 0;
void backtracking(int n, int row, vector<string>& chessboard) {
    if (row == n) {
        count++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isValid(row, col, chessboard, n)) {
            chessboard[row][col] = 'Q'; // Place the queen
            backtracking(n, row + 1, chessboard);
            chessboard[row][col] = '.'; // Backtrack
        }
    }
}
bool isValid(int row, int col, vector<string>& chessboard, int n) {
    int count = 0;
    // Check the column
    for (int i = 0; i < row; i++) { // This is a pruning step
        if (chessboard[i][col] == 'Q') {
            return false;
        }
    }
    // Check the 45-degree angle
    for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    // Check the 135-degree angle
    for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
        if (chessboard[i][j] == 'Q') {
            return false;
        }
    }
    return true;
}

public:
    int totalNQueens(int n) {
        std::vector<std::string> chessboard(n, std::string(n, '.'));
        backtracking(n, 0, chessboard);
        return count;

    }
};

Additional Languages

JavaScript

var totalNQueens = function(n) {
    let count = 0;
    const backtracking = (n, row, chessboard) => {
        if(row === n){
            count++;
            return;
        }
        for(let col = 0; col < n; col++){
            if(isValid(row, col, chessboard, n)) { // If valid, place the queen
                chessboard[row][col] = 'Q'; // Place the queen
                backtracking(n, row + 1, chessboard);
                chessboard[row][col] = '.'; // Backtrack
            }
        }
    }

    const isValid = (row, col, chessboard, n) => {
        // Check the column
        for(let i = 0; i < row; i++){ // This is a pruning step
            if(chessboard[i][col] === 'Q'){
                return false;
            }
        }
        // Check the 45-degree angle
        for(let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--){
            if(chessboard[i][j] === 'Q'){
                return false;
            }
        }
        // Check the 135-degree angle
        for(let i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++){
            if(chessboard[i][j] === 'Q'){
                return false;
            }
        }
        return true;
    }
    const chessboard = new Array(n).fill([]).map(() => new Array(n).fill('.'));
    backtracking(n, 0, chessboard);
    return count;
};

TypeScript

// 0 indicates the cell is empty, 1 indicates the cell has a queen
type GridStatus = 0 | 1;
function totalNQueens(n: number): number {
    let resCount: number = 0;
    const chess: GridStatus[][] = new Array(n).fill(0)
        .map(_ => new Array(n).fill(0));
    backTracking(chess, n, 0);
    return resCount;
    function backTracking(chess: GridStatus[][], n: number, startRowIndex: number): void {
        if (startRowIndex === n) {
            resCount++;
            return;
        }
        for (let j = 0; j < n; j++) {
            if (checkValid(chess, startRowIndex, j, n) === true) {
                chess[startRowIndex][j] = 1;
                backTracking(chess, n, startRowIndex + 1);
                chess[startRowIndex][j] = 0;
            }
        }
    }
};
function checkValid(chess: GridStatus[][], i: number, j: number, n: number): boolean {
    // Check vertically upwards
    let tempI: number = i - 1,
        tempJ: number = j;
    while (tempI >= 0) {
        if (chess[tempI][tempJ] === 1) return false;
        tempI--;
    }
    // Check diagonally upwards to the left
    tempI = i - 1;
    tempJ = j - 1;
    while (tempI >= 0 && tempJ >= 0) {
        if (chess[tempI][tempJ] === 1) return false;
        tempI--;
        tempJ--;
    }
    // Check diagonally upwards to the right
    tempI = i - 1;
    tempJ = j + 1;
    while (tempI >= 0 && tempJ < n) {
        if (chess[tempI][tempJ] === 1) return false;
        tempI--;
        tempJ++;
    }
    return true;
}

C

// path[i] indicates there is a queen at column path[i] in row i
int *path;
int pathTop;
int answer;
// Check if placing a queen at row `level`, column `index` is valid
int isValid(int index, int level) {
    int i;
    // updater indicates the column position a diagonal queen should occupy
    // Check 45-degree diagonal
    int lCornerUpdater = index - level;
    // Check 135-degree diagonal
    int rCornerUpdater = index + level;
    for(i = 0; i < pathTop; ++i) {
        // path[i] == index checks if there's a queen in column `index`
        // path[i] == lCornerUpdater checks the 45-degree diagonal
        // path[i] == rCornerUpdater checks the 135-degree diagonal
        if(path[i] == index || path[i] == lCornerUpdater || path[i] == rCornerUpdater)
            return 0;
        // Update `updater` to next row's position
        ++lCornerUpdater;
        --rCornerUpdater;
    }
    return 1;
}

// Backtracking: level is the current row
void backTracking(int n, int level) {
    // If path has n elements, there is one solution. Increment answer.
    if(pathTop == n) {
        ++answer;
        return;
    }

    int i;
    for(i = 0; i < n; ++i) {
        // If it's valid to place a queen at `level` row, `i` column, add `i` to path
        if(isValid(i, level)) {
            path[pathTop++] = i;
            backTracking(n, level + 1);
            // Backtrack
            --pathTop;
        }
    }
}

int totalNQueens(int n){
    answer = 0;
    pathTop = 0;
    path = (int *)malloc(sizeof(int) * n);

    backTracking(n, 0);

    return answer;
}

Java

class Solution {
    int count = 0;
    public int totalNQueens(int n) {
        char[][] board = new char[n][n];
        for (char[] chars : board) {
            Arrays.fill(chars, '.');
        }
        backTrack(n, 0, board);
        return count;
    }
    private void backTrack(int n, int row, char[][] board) {
        if (row == n) {
            count++;
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col, n, board)) {
                board[row][col] = 'Q';
                backTrack(n, row + 1, board);
                board[row][col] = '.';
            }
        }
    }
    private boolean isValid(int row, int col, int n, char[][] board) {
        // Check the column
        for (int i = 0; i < row; ++i) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        // Check the 45-degree diagonal
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        // Check the 135-degree diagonal
        for (int i = row - 1, j = col + 1; i >= 0 && j <= n - 1; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
}