N-Queens

The N-Queens puzzle is a classic combinatorial problem that serves as an excellent example of the backtracking technique. The challenge is to place N chess queens on an N×N chessboard so that no two queens attack each other. This means that no two queens can be on the same row, same column, or same diagonal. The backtracking solution incrementally builds a solution by placing one queen in each row. We can define a recursive function, say `solve(row)`, which tries to place a queen in the current `row`. Inside this function, we iterate through all columns from 0 to N-1 for the current row. For each column `col`, we check if it's a 'safe' position to place a queen. A position `(row, col)` is safe if it's not under attack by any queen placed in the previous rows (from 0 to `row-1`). To check for safety, we need to verify that no other queen is in the same column or on the two main diagonals. Once we find a safe column, we 'place' the queen there (e.g., mark it in our board representation). Then, we make a recursive call to `solve(row + 1)` to handle the next row. If the recursive call successfully finds a solution for the rest of the board, we're good. If not, or after it returns, we must 'un-place' the queen (backtrack) and try placing it in the next safe column in the current row. The base case for the recursion is when `row == N`, which means we have successfully placed N queens, and we have found a valid solution.