N-Queens

We place queens one by one in different columns, starting from the leftmost column. When we place a queen in a column, we check for clashes with already placed queens. If we find a row for which there is no clash, we mark this row and column as part of the solution. If we do not find such a row due to clashes, then we backtrack and return false.

Strategy: place one queen per column, left to right, and undo a placement the moment it leads nowhere.

1. If every column already has a queen, the board is a solution.
2. Otherwise take the next empty column and try each row in turn.
3. Skip any row where the new queen would share a row or a diagonal with a queen already placed. Columns never clash, because each column gets exactly one queen.
4. On a safe row, place the queen and solve the remaining columns recursively.
5. If that recursive call fails, remove the queen and try the next row.
6. If no row in this column works, report failure to the column before it, which then moves its own queen.

1. Define backtrack(col).
2. Base Case: If col == N, solution found.
3. Loop through rows row from 0 to N-1.
4. Check if placing queen at (row, col) is safe (check row and diagonals). (Note: We check previous columns).
5. If safe: Place queen, call backtrack(col + 1).
6. If recursive call returns (backtracks): Remove queen and try next row.

Example: N=4

• Place Q at (0,0).
• Try (1,0) - Attack. (1,1) - Attack. (1,2) - Safe. Place Q.
• Try (2,0)...(2,3) - All attacked. Backtrack.
• Remove Q from (1,2). Try (1,3) - Safe. Place Q.
• ...and so on until a valid arrangement is found.

"Place N items such that they don't conflict", "Constraint satisfaction".