Pattern visualizer
N-Queens
Two queens in one row always attack each other, so every valid board has exactly one queen per row. That turns a board search into a much smaller one: decide row 0, then row 1, and so on, and the only thing to check for a candidate column is whether an earlier queen sits in the same column or on one of its two diagonals. Cells on a diagonal all share the same row - col, and cells on an anti-diagonal share the same row + col, so three sets answer that in O(1). When a row has no safe column, the choice in the row above was wrong: undo it (backtrack) and try the next column there. Reaching row n means a full board, which is recorded, and the search keeps going until every branch is explored. Animated on: n = 4. Place 4 queens on a 4x4 board so no two share a row, column or diagonal; return every distinct board. Answer: 2 solutions, cols [[1, 3, 0, 2], [2, 0, 3, 1]]..
Row-by-row backtracking with column and diagonal sets
n = 4. Every row must hold exactly one queen, so the board collapses to one number per row: cols[r] is the column of the queen in row r. Placing row by row means rows can never clash, leaving only columns and the two diagonals to check. Start at row 0 with nothing placed.
1FUNCTION solveNQueens(n)2 out <- EMPTY LIST3 cols <- ARRAY OF n EMPTY SLOTS4 FUNCTION place(row)5 IF row = n6 APPEND BOARD(cols) TO out7 RETURN8 FOR c <- 0 TO n - 19 IF c IN usedCols OR row - c IN diag1 OR row + c IN diag210 CONTINUE11 cols[row] <- c12 ADD c TO usedCols, row - c TO diag1, row + c TO diag213 place(row + 1)14 REMOVE c FROM usedCols, row - c FROM diag1, row + c FROM diag215 place(0)16 RETURN out
← / → step · space play · Home restart