Hi. In the college we are looking at two basic examples of backtracking (sudoku and n-queens) and a question arose: How program the algorithm of the 8 queens in a non-recursive way?
more specifically it must be done through a stack or through a queue counting the steps to reach the solution.
My problem is born with the code they give us and with the algorithm itself (here). I understand that du and dd are the main diagonals but I do not understand the line 16... (specifically du [c + 7 -r]) where that seven comes from(should not move one square per diagonal?).
No longer relevant.
...
No worries! If you're interested, this was the task in question, where you are asked to come up with a sequencial way to place queens in every cell of the board, so that each queen placed cannot be hit by the previous one.
As for your question, for backtracking, you can note that you need to place 1 queen in every column. So you could store the array
row_occupied
, whererow_occupied[i]
indicates the row in which you placed the queen in the i-th column. Then you want to essentially start filling it, with code might be looking like this (everything is 1-based):Does that help with your problem? This does not use recursion, because it essentially stores everything needed on the stack (
row_occupied
).Yes, it's very helpful, thank you very much. So if I understand correctly, it is not necessary to create two other arrangements to see the availability in the diagonals? .
You will check whether queens do not clash diagonally in that if statement, but there is no need for any additional data storage, since you already know grid coordinates for queens.
If you know coordinates of two queens
(x1, y1)
and(x2, y2)
, then they do not clash if and only ifx1 != x2 AND y1 != y2 AND x1+y1 != x2+y2 AND x1-y1 != x2-y2
. Try drawing out a coordinate grid and write down values forx+y
andx-y
to see why they indeed check the diagonals.