About the N-Queens Problem

The N-Queens problem is a classic challenge where you place N queens on an N×N chessboard without any two queens threatening each other. Queens attack in horizontal, vertical, and diagonal directions.

This visualiser uses a backtracking algorithm to find and display all solutions for a given number of queens. Adjust the number using the input or slider above, then click 'Play' to see the solutions unfold.

Algorithm Overview

The N-Queens Visualiser employs a recursive backtracking algorithm to solve the problem. It systematically places queens on the chessboard and checks if the current arrangement is valid by ensuring no two queens threaten each other. If a safe placement is found, it proceeds to place the next queen. If no such placement is possible, it backtracks and tries alternative configurations.

Time Complexity

The time complexity of the N-Queens problem using backtracking is typically O(N!), where N is the number of queens (and also the size of the chessboard). This represents the factorial growth of possibilities that need to be checked.

Space Complexity

The space complexity is O(N^2), where N is the size of the chessboard. This complexity arises primarily due to the space required to maintain the chessboard and the recursive call stack during the backtracking process.