Visualizers

N-Queens Visualizer

Step-through backtracking to place N non-attacking queens on a chessboard.

native Client-side

Board Size N (4-8)

Speed

Ready to solve.

Execution Log

Solutions Found: 0

Backtracks: 0

Current Action:

Idle

Legend:

♕ Queen Placed (Safe)

♕ Queen Conflict

Light Square

Dark Square

N-Queens Backtracking Problem

The N-Queens puzzle is the problem of placing $N$ chess queens on an $N \times N$ chessboard so that no two queens threaten each other. This means that no two queens can share the same row, column, or diagonal.

How Backtracking Solves It

The algorithm searches for a solution recursively by placing queens row-by-row:

Start in the top-left corner.
Place a queen in the first available cell in the current row.
Check if there are any conflicts (horizontal, vertical, diagonal) with previously placed queens.
If there are no conflicts, recursively try to place a queen in the next row.
If placing a queen leads to a dead end (no safe cells in a subsequent row), **backtrack**: remove the queen, and try the next column in the previous row.

Implementation

function solveNQueens(n) {
  const result = [];
  const board = Array(n).fill(-1); // board[r] = c
  
  function isSafe(row, col) {
    for (let i = 0; i < row; i++) {
      const otherCol = board[i];
      if (otherCol === col || 
          otherCol - i === col - row || 
          otherCol + i === col + row) {
        return false;
      }
    }
    return true;
  }
  
  function backtrack(row) {
    if (row === n) {
      result.push([...board]);
      return;
    }
    for (let col = 0; col < n; col++) {
      board[row] = col;
      if (isSafe(row, col)) {
        backtrack(row + 1);
      }
      board[row] = -1;
    }
  }
  
  backtrack(0);
  return result;
}

def solve_n_queens(n):
    result = []
    board = [-1] * n  # board[r] = c
    
    def is_safe(row, col):
        for i in range(row):
            other_col = board[i]
            if (other_col == col or 
                other_col - i == col - row or 
                other_col + i == col + row):
                return False
        return True
        
    def backtrack(row):
        if row == n:
            result.append(list(board))
            return
        for col in range(n):
            board[row] = col
            if is_safe(row, col):
                backtrack(row + 1)
            board[row] = -1
            
    backtrack(0)
    return result

import java.util.*;

public class NQueens {
    private List<int[]> result = new ArrayList<>();
    private int[] board;

    public List<int[]> solveNQueens(int n) {
        board = new int[n];
        Arrays.fill(board, -1);
        backtrack(0, n);
        return result;
    }

    private void backtrack(int row, int n) {
        if (row == n) {
            result.add(board.clone());
            return;
        }
        for (int col = 0; col < n; col++) {
            board[row] = col;
            if (isSafe(row, col)) {
                backtrack(row + 1, n);
            }
            board[row] = -1;
        }
    }

    private boolean isSafe(int row, int col) {
        for (int i = 0; i < row; i++) {
            int otherCol = board[i];
            if (otherCol == col || 
                otherCol - i == col - row || 
                otherCol + i == col + row) {
                return false;
            }
        }
        return true;
    }
}

#include <vector>
#include <cmath>

class NQueens {
private:
    std::vector<std::vector<int>> result;
    std::vector<int> board;

    bool isSafe(int row, int col) {
        for (int i = 0; i < row; ++i) {
            int otherCol = board[i];
            if (otherCol == col || 
                otherCol - i == col - row || 
                otherCol + i == col + row) {
                return false;
            }
        }
        return true;
    }

    void backtrack(int row, int n) {
        if (row == n) {
            result.push_back(board);
            return;
        }
        for (int col = 0; col < n; ++col) {
            board[row] = col;
            if (isSafe(row, col)) {
                backtrack(row + 1, n);
            }
            board[row] = -1;
        }
    }

public:
    std::vector<std::vector<int>> solveNQueens(int n) {
        board.assign(n, -1);
        backtrack(0, n);
        return result;
    }
};

Related Tools

Big-O Visualizer

Interactive growth-curve chart for common complexity classes.

Data Structure Visualizer

Animated operations on linked lists, trees, stacks and hash tables.

Algorithm Visualizer

Step-through animations for sorting and pathfinding algorithms.