I_love_Eva_Green's blog

8 queens algorithm
By I_love_Eva_Green, history, 5 years ago, In English

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?).

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
5 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

No longer relevant.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    ...

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 3   Vote: I like it -8 Vote: I do not like it

      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, where row_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):

      row_occupied = [0, 0, 0, ...]
current_column = 1
while current_column <= N:
    // Try next row.
    row_occupied[current_column] += 1
    if (row_occupied[current_column] > N):
        // We've run out of valid rows, backtrack.
        row_occupied[current_column] = 0 // Reset the counter
        current_column -= 1
    else if (<queen in current_column does not clash with any queens in previous columns>):
        // We're good, go to the next column
        current_column += 1
    else:
        // Stay on the current column.

      Does that help with your problem? This does not use recursion, because it essentially stores everything needed on the stack (row_occupied).

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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? .

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -8 Vote: I do not like it

          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 if x1 != x2 AND y1 != y2 AND x1+y1 != x2+y2 AND x1-y1 != x2-y2. Try drawing out a coordinate grid and write down values for x+y and x-y to see why they indeed check the diagonals.

          → Reply