Почему мой алгоритм N Queens достигает последней строки? - PullRequest
Новая
       74

Почему мой алгоритм N Queens достигает последней строки?

4 голосов
/ 08 апреля 2020

Мне кажется, я понимаю смысл алгоритма NQueens - вы проверяете каждую строку на наличие доступных пробелов и, если они существуют, ставите ферзь там и рекурсивно вызываете алгоритм для следующей строки. Вот мой алгоритм (с размером N 3) 

from typing import List
import pdb
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        self.solutions = 0 
        self.attack_zone = [[0]*n for i in range(n)]
        self.size = n
        self.backtrack_nqueens(0,0) #start on row 0 
        return self.solutions
    def backtrack_nqueens(self,row,iteration):
        #starting at row
        for col in range(self.size):
            if self.is_not_under_attack(row,col):
                print("on iteration",iteration,row,col,"was a safe place for some reason")
                #adds queen to this row
                self.place_or_remove_queen(row,col,True)
                if row + 1 == self.size:
                    ## THIS SHOULD NEVER HAPPEN 
                    self.solutions += 1
                else:
                    self.backtrack_nqueens(row+1,iteration+1)
                #removes queen from this row
                self.place_or_remove_queen(row,col,False)

    def place_or_remove_queen(self,row,col,place):
        flag = 1 if place else 0 
        self.attack_zone[row] = [flag]*self.size
        #for col
        for r in range(self.size):
            self.attack_zone[r][col] = flag
        #lower right
        for r,c in zip(range(row,self.size,1),range(col,self.size,1)):
            self.attack_zone[r][c] = flag
        #upper right
        for r,c in zip(range(row,-1,-1),range(col,self.size,1)):
            self.attack_zone[r][c] = flag
        #lower left
        for r,c in zip(range(row,self.size,1),range(col,-1,-1)):
            self.attack_zone[r][c] = flag
        #upper left
        for r,c in zip(range(row,-1,-1),range(col,-1,-1)):
            self.attack_zone[r][c] = flag

    def is_not_under_attack(self,row,col):
        return self.attack_zone[row][col] == 0
s = Solution()
print(s.solveNQueens(3))

Когда я запускаю это, self.solutions заканчивается на 3 - в основном он находит 3 места для королевы, которые, как мы все знаем, не должны происходить. Я не понимаю, как это добраться до того ряда, где я сказал, ## ЭТО НЕ ДОЛЖНО БЫТЬ.

Единственное, о чем я могу думать, это то, что я каким-то образом удаляю королеву, которую не следует удалять? Так что в моей attack_zone есть пустые места, когда этого не должно быть. Может кто-то указать, что я делаю неправильно в рекурсии, которая может вызвать это и почему?

1 Ответ

5 голосов
/ 14 апреля 2020

Проблема в том, что когда вы удаляете ферзя, вы отмечаете соответствующие квадраты как «свободные», то есть устанавливаете их «счетчик угроз» равным нулю, независимо от того, угрожает ли этот квадрат другой королеве. С учетом вашего примера происходит следующее: 

# Iteration 1     # Iteration 2     # Iteration 3

| 1 | 1 | Q |     | 1 | 1 | Q |     | 0 | 0 | Q |
+---+---+---+     +---+---+---+     +---+---+---+
| 0 | 1 | 1 |     | Q | 1 | 1 |     | 0 | 0 | 0 |
+---+---+---+     +---+---+---+     +---+---+---+
| 1 | 0 | 1 |     | 1 | 1 | 1 |     | 0 | 0 | 1 |

На итерации № 3 ферзь на (1, 0) удаляется, и все соответствующие квадраты помечаются как 0, а также те, которым на самом деле угрожает королева на (0, 2). То же самое происходит с ферзями на (1, 1) и (1, 2), и последняя в конечном итоге приводит к свободному квадрату на (2, 0), который является последней строкой.

Чтобы заставить алгоритм работать, вы можете сохранить " Угроза ", которая отслеживает, на сколько королев угрожает квадрат. Размещение королевы увеличивает это число на единицу, а удаление королевы уменьшает его на единицу. Вы можете реализовать это, изменив значение flag на flag = 1 if place else -1 и затем использовать self.attack_zone[r][c] += flag везде вместо self.attack_zone[r][c] = flag. Это дает тогда следующую картину: 

# Iteration 1     # Iteration 2     # Iteration 3

| 1 | 1 | Q |     | 2 | 2 | Q |     | 1 | 1 | Q |
+---+---+---+     +---+---+---+     +---+---+---+
| 0 | 1 | 1 |     | Q | 2 | 2 |     | 0 | 1 | 1 |
+---+---+---+     +---+---+---+     +---+---+---+
| 1 | 0 | 1 |     | 2 | 1 | 1 |     | 1 | 0 | 1 |
...