Place n queens on an n by n chessboard so that no two attack each other. Queens attack along rows, columns and both diagonals.
DSA Animator › DSA Revision › Backtracking › N-Queens
Remember: one queen per row, and check column and both diagonals. Row minus column and row plus column identify the diagonals. The video solves N-Queens (LeetCode 51, Hard) with the Backtracking on a Board pattern from the Backtracking topic, and you can replay every step in the interactive N-Queens animation.
Place n queens on an n by n chessboard so that no two attack each other. Queens attack along rows, columns and both diagonals.
For n equal to 4, there are 2 solutions. One has queens in columns 1, 3, 0 and 2 of rows 0 to 3.
Trying every way to place n queens on n squared cells is enormous. There is exactly one queen per row, so place them row by row.
For the current row, try each column. Skip a column if a queen above shares its column or one of its diagonals. Place the queen, recurse to the next row, then remove it.
Row 0 at column 0, then row 1 can only use column 2. Row 2 has no safe column, so backtrack, and try row 1 at column 3. Row 2 goes to column 1, but row 3 has no safe column, so backtrack all the way to row 0. Row 0 at column 1, then row 1 at column 3, row 2 at column 0 and row 3 at column 2. All 4 queens are safe, so that is a solution. Continuing the search finds the mirror image, 2, 0, 3, 1.
In code, use three boolean sets: columns, row minus column, and row plus column. For each column, skip it if any set already contains it. Otherwise mark all three, recurse to the next row, and unmark them. It's about O of n factorial time, and the sets make each check O of 1.
Remember: one queen per row, and check column and both diagonals. Row minus column and row plus column identify the diagonals.