Place n queens on an n × n chessboard so that no two queens share a row, a column, or either diagonal. Return every distinct solution. Example: for n = 4, exactly two boards satisfy every constraint.
The diagonal constraint is the deceptive one. Rows and columns are “at most one per line”; the two diagonal families add four MORE lines each queen must stay off. Brute-force checking 4^4 = 256 placements misses the point — the symmetry of the constraints is what collapses the search.
Place four queens on a four-by-four chessboard. No two queens can share a row, a column, or either diagonal. The puzzle is from 1848. The German chess magazine that published it offered a prize. Thousands of readers tried; most sent in wrong answers. Good luck.
Here is the fair warning: I am going to set you up. In the next screen I place two queens for you — and the board I hand you is already cornered. You will try every square in a single row, and every square will be rejected. That feeling — “I tried all of them; none work” — is the problem that invented backtracking.
You do not need to remember what backtracking means yet. You need to FEEL the wall. We will name the rescue after you have lived the corner.