N-Queens

Leetcode Problem 51: N-Queens

Problem Summary

Place n chess queens on an n by n board so that no two queens share the same row, column, or diagonal. Return all distinct board layouts that satisfy this constraint, representing each row as a string of Q (queen) and . (empty) characters.

Techniques

• Array
• Backtracking

Solution

function isValid(row: number, col: number, board: string[][]): boolean {
    for (let i = 0; i < row; i++) {
        if (board[i][col] === 'Q') {
            return false;
        }
    }

    for (let i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] === 'Q') {
            return false;
        }
    }

    for (let i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] === 'Q') {
            return false;
        }
    }

    return true;
};

function backtrackNQueens(results: string[][], board: string[][], row: number) {
    if (row === board.length) {
        results.push([...board.map(row => row.join(""))])
        return
    }

    for (let col = 0; col < board.length; col++) {
        if (isValid(row, col, board)) {
            board[row][col] = 'Q'
            backtrackNQueens(results, board, row + 1);
            board[row][col] = '.'
        }
    }
}

function solveNQueens(n: number): string[][] {
    const results: string[][] = []
    const board: string[][] = Array.from({ length: n }, () => Array(n).fill('.'));
    backtrackNQueens(results, board, 0)
    return results
}

console.log(solveNQueens(4)); // [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]