Блог пользователя I_love_Eva_Green

8 queens algorithm
Автор I_love_Eva_Green, история, 6 лет назад, По-английски

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

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

»
6 лет назад, # |
← Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

No longer relevant.

→ Ответить
  • »
    »
    6 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    ...

    → Ответить
    • »
      »
      »
      6 лет назад, # ^ |
      ← Rev. 3   Проголосовать: нравится -8 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
            Проголосовать: нравится -8 Проголосовать: не нравится

          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.

          → Ответить