This visualization was AI-generated. Verify with LeetCode #51.

N-Queens

The N-Queens problem is a classic backtracking puzzle where you must place n chess queens on an n×n chessboard so that no two queens attack each other. Queens can attack any piece in the same row, column, or diagonal. This visualization shows how backtracking systematically explores possible placements, placing queens row by row and backtracking when conflicts are detected.

Backtracking LeetCode 51 ↗ Hard

Problem

Input: An integer n representing the size of the chessboard

Output: All distinct solutions where no two queens attack each other

Example:

Input: n = 4
Output: [
  [".Q..",
   "...Q",
   "Q...",
   "..Q."],
  ["..Q.",
   "Q...",
   "...Q",
   ".Q.."]
]

Constraints: 1 ≤ n ≤ 9

Visualization

Board Size (n):

Speed: 800ms

Current Row

Solutions Found

Backtracks

Chessboard

Solutions Found: 0

Code

fun solveNQueens(n: Int): List<List<String>> {    val result = mutableListOf<List<String>>()    val board = Array(n) { CharArray(n) { '.' } }        fun isSafe(row: Int, col: Int): Boolean {        for (i in 0 until row) {            if (board[i][col] == 'Q') return false            if (col-(row-i) >= 0 && board[i][col-(row-i)] == 'Q') return false            if (col+(row-i) < n && board[i][col+(row-i)] == 'Q') return false        }        return true    }    fun backtrack(row: Int) {        if (row == n) {            result.add(board.map { String(it) })            return }        for (col in 0 until n) {            if (isSafe(row, col)) {                board[row][col] = 'Q'                backtrack(row + 1)                board[row][col] = '.'            } } }    backtrack(0)    return result}

def solveNQueens(n):    result = []    board = [['.' for _ in range(n)] for _ in range(n)]        def is_safe(row, col):        for i in range(row):            if board[i][col] == 'Q':                return False            if col-(row-i) >= 0 and board[i][col-(row-i)] == 'Q':                return False            if col+(row-i) < n and board[i][col+(row-i)] == 'Q':                return False        return True        def backtrack(row):        if row == n:            result.append([''.join(r) for r in board])            return        for col in range(n):            if is_safe(row, col):                board[row][col] = 'Q'                backtrack(row + 1)                board[row][col] = '.'        backtrack(0)    return result

Status

Ready to start

How It Works

The N-Queens problem uses backtracking to systematically explore all possible queen placements. Starting from the first row, we try placing a queen in each column. For each placement, we check if it's safe (no conflicts with previously placed queens). If safe, we recursively move to the next row. If we reach the last row successfully, we've found a solution. When we can't place a queen safely in any column of a row, we backtrack to the previous row and try the next column.

Key Insight

The key optimization is that we only need to check for conflicts with queens in previous rows, not all rows. Since we place queens row by row, there can never be conflicts with rows below the current position. For each position, we check three directions: straight up (same column), diagonal up-left, and diagonal up-right.

Algorithm Steps

Initialize: Create an empty n×n board
Backtrack Function: Try to place queens starting from row 0
- If we've placed queens in all n rows, add the current board configuration to results
- For each column in the current row:
  - Check if placing a queen at (row, col) is safe
  - If safe, place the queen and recursively call backtrack for the next row
  - After recursion returns, remove the queen (backtrack)
Safety Check: A position is safe if no queen in previous rows attacks it
- Check the same column in all previous rows
- Check both diagonals in all previous rows

Complexity Analysis

Aspect	Complexity	Explanation
Time	O(n!)	In the worst case, we try n positions in the first row, at most n-1 in the second, etc. With pruning via is_safe(), many branches are eliminated early
Space	O(n²)	The board takes O(n²) space, and the recursion stack goes up to depth n