SimuVedaAlgorithms Lab Open in the lab

Backtracking / Advanced

N-Queens Visualizer

Place one queen per row. Try each column. If it is safe, move to the next row. If no column works, backtrack and move the previous queen.

Start the N-Queens simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n!)
Average timeO(n!)
Worst timeO(n!)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Place 4 queens, one per row, starting at the top row.
  2. Row 0, column 0 is safe. Place a queen.
  3. Row 1, column 0 is attacked by the queen in row 0.
  4. Row 1, column 1 is attacked by the queen in row 0.
  5. Row 1, column 2 is safe. Place a queen.
  6. Row 2, column 0 is attacked by the queen in row 0.
  7. Row 2, column 1 is attacked by the queen in row 1.
  8. Row 2, column 2 is attacked by the queen in row 0.
  9. Row 2, column 3 is attacked by the queen in row 1.
  10. Nothing worked below row 1. Remove this queen and try the next column.
  11. Row 1, column 3 is safe. Place a queen.
  12. Row 2, column 0 is attacked by the queen in row 0.
  13. Row 2, column 1 is safe. Place a queen.
  14. Row 3, column 0 is attacked by the queen in row 0.
  15. Row 3, column 1 is attacked by the queen in row 1.
  16. Row 3, column 2 is attacked by the queen in row 2.
  17. Row 3, column 3 is attacked by the queen in row 0.
  18. Nothing worked below row 2. Remove this queen and try the next column.
  19. Row 2, column 2 is attacked by the queen in row 0.
  20. Row 2, column 3 is attacked by the queen in row 1.
  21. … 8 more steps …
  22. Row 3, column 0 is attacked by the queen in row 2.
  23. Row 3, column 1 is attacked by the queen in row 0.
  24. Row 3, column 2 is safe. Place a queen.
  25. All 4 queens are placed. Solution found after 26 tries.

Try it with your own input →

Backtracking: N-Queens in Java, Python, C++, C and JavaScript

boolean solve(int row) {
  if (row == n) return true;
  for (int col = 0; col < n; col++) {
    if (isSafe(row, col)) {
      board[row][col] = 'Q';
      if (solve(row + 1)) return true;
      board[row][col] = '.';
    }
  }
  return false;
}
def solve(row):
    if row == n:
        return True
    for col in range(n):
        if is_safe(row, col):
            board[row][col] = 'Q'
            if solve(row + 1):
                return True
            board[row][col] = '.'
    return False
bool solve(int row) {
  if (row == n) return true;
  for (int col = 0; col < n; col++) {
    if (isSafe(row, col)) {
      board[row][col] = 'Q';
      if (solve(row + 1)) return true;
      board[row][col] = '.';
    }
  }
  return false;
}
int n;
char board[12][12];

int solve(int row) {
  if (row == n) return 1;
  for (int col = 0; col < n; col++) {
    if (isSafe(row, col)) {
      board[row][col] = 'Q';
      if (solve(row + 1)) return 1;
      board[row][col] = '.';
    }
  }
  return 0;
}
function solve(row) {
  if (row === n) return true;
  for (let col = 0; col < n; col++) {
    if (isSafe(row, col)) {
      board[row][col] = 'Q';
      if (solve(row + 1)) return true;
      board[row][col] = '.';
    }
  }
  return false;
}

In an interview

LeetCode 51, N-Queens: place n queens so that no two attack each other. This finds the first solution.

Keep three sets: used columns, row − col diagonals and row + col diagonals. Then isSafe is O(1) instead of a loop.

More backtracking