How do you solve the N-Queens problem, and what state does the search need to track?
You put one queen on each row, one row at a time, and you keep track of the columns and the diagonals that are already taken so that you never have to check the whole board.
So what state does the search need to track? Three sets.
the set what it holds
-------------------- --------------------------------------------
the columns the column of every queen already placed
one diagonal set row + column, for the "\" diagonals
the other diagonal set row - column, for the "/" diagonals
And here is why the diagonals work like that. Two queens are on the same diagonal when their row plus column is the same, or when their row minus column is the same. So if you store those two numbers for every queen you have placed, then you can ask in one step whether a new square is attacked.
And that is the point of the sets. Without them you would have to look at every queen on the board for every square you try, and that makes the search much slower. With them the check is one lookup in each set.
And how does the search work? You go through the rows in order. For each row you try every column. If the column is free and both diagonals are free then you place the queen, you update the three sets, and you call yourself for the next row. When you come back you take the queen off again and undo the three sets.
And that undoing is the part that makes it backtracking. You try a choice, you see what happens, and then you take the choice back so that the next choice starts from the same place.
And the complexity is worth knowing about. There are n to the power of n ways of putting a queen on each row, because there are n choices for the first row and n for the second and so on. Most of them are ruled out by the diagonals, and the backtracking search only walks through the ones that are still possible. For n of eight the search visits a manageable number of states, and for n of twenty it is too slow for most machines.
So the rule to remember is this. Keep three sets, and the diagonals are stored as row plus column and row minus column.
The next two questions in this topic show the code and the safety check on its own.