Several constraints at once

The unit's hardest problem, and it is the multi-set bookkeeping from Unit 1 with an undo step.

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.

1for row, col in [(0, 0), (1, 1), (2, 2), (0, 2), (1, 1)]:2    print((row, col), "down", row - col, "up", row + col)

Predict the output· 5 min

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.

Python

1cells = [(0, 0), (1, 1), (2, 0), (1, 3)]2 3print("row - col:", [r - c for r, c in cells])4print("row + col:", [r + c for r, c in cells])5print("(0,0) and (1,1) share a diagonal:", (0 - 0 == 1 - 1) or (0 + 0 == 1 + 1))

Printed output

Problem· 40 min

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.

1cells = [(0, 0), (1, 1), (2, 0), (1, 3)]2 3print("row - col:", [r - c for r, c in cells])4print("row + col:", [r + c for r, c in cells])5print("(0,0) and (1,1) share a diagonal:", (0 - 0 == 1 - 1) or (0 + 0 == 1 + 1))