Watch the N-Queens problem being solved using a recursive backtracking algorithm. See how the computer searches for valid queen placements.
A classic combinatorial problem that demonstrates the power of recursive trial-and-error (Backtracking).
Place N queens on an N×N board such that no two queens attack each other. This means no two queens can be in the same row, column, or diagonal.
We place queens one row at a time, starting from the top. Each row has its own queen, which slides along the row trying every column from left to right.
Before placing, we check the queens in the rows above: 1) Same column, 2) Upper-left diagonal, 3) Upper-right diagonal. We don't need to check the rows below as we haven't placed any queens there yet.
If every column of the current row is attacked, its queen goes home and we return false to the previous recursive call (the "backtrack"), and the queen in the row above moves on to its next column.
While the state space is N^N, backtracking prunes huge branches of the search tree, making it much faster than brute force. For N=8, there are 92 distinct solutions.