Backtracking
Several constraints at once
The unit's hardest problem, and it is the multi-set bookkeeping from Unit 1 with an undo step.
Key idea
You have done the bookkeeping before
Unit 1 validated a grid by keeping one collection per constraint and updating all of them in the same pass. The constraints there were rows, columns, and blocks.
This is that idea with two additions: the placements are being searched for rather than read, so each one must be undone, and the constraint keys involve diagonals rather than blocks.
Why it works
Naming a diagonal with arithmetic
Two cells lie on the same downward diagonal exactly when row - col is equal for both. They lie on the same upward diagonal exactly when row + col is equal.
That is worth checking rather than believing. Moving one step down and one step right increases both coordinates by one, leaving the difference unchanged, which is the downward diagonal. Moving down and left increases the row and decreases the column, leaving the sum unchanged.
So three sets suffice: occupied columns, occupied differences, and occupied sums. Rows need no set at all if the search places exactly one item per row.
Key idea
One row per level removes a whole constraint
Structuring the search so that level k places into row k means two items can never share a row, by construction. No set is needed for it and no check either.
That is a recurring move in constrained search: arrange the decision order so that one of the constraints becomes impossible to violate. It shrinks both the code and the search tree.
Why it works
Three additions, three removals
Placing an item adds to three sets and records the position. Undoing removes from all three and clears the position. Same counting discipline as the permutation lesson, with more state.
The failure mode when one removal is missed is that the search finds too few solutions, because a phantom occupancy blocks later branches. If a constrained search returns fewer results than expected, count the additions against the removals first.
Cost
Why the pruning matters so much
Without any constraint checking, placing one item per row on an n by n board is n to the n arrangements. With the three checks, the vast majority of branches die at the first or second level.
The pruned search is still exponential and it is dramatically smaller. This is the clearest demonstration in the course of pruning changing what is feasible rather than merely what is fast, and it is worth saying that explicitly when discussing the solution.
Edge cases
Building the output board
The search naturally tracks positions rather than a picture. Converting to whatever output format is wanted is a separate step at the moment a full solution is found, and doing it there rather than maintaining a board throughout keeps the undo simple.
Read the required format carefully. Producing correct placements in the wrong shape is a frustrating way to fail a problem you actually solved.
Predict the output: naming the diagonals
Two cells share a falling diagonal when their row minus column is equal, and a rising diagonal when their row plus column is equal. Type the three lines it prints.
N Queens
Read the constraints first and let them tell you what complexity is expected. Derive the approach, implement it, run the tests, and submit when it passes.