首页 > 代码库 > [leetcode]N-Queens II @ Python

[leetcode]N-Queens II @ Python

2024-07-05 18:57:57   224人阅读

原题地址：https://oj.leetcode.com/problems/n-queens-ii/

题意：和N-Queens这道题其实是一样的，只不过这次要求返回的时N皇后的解的个数的问题。

解题思路：上道题使用了递归回溯的解法，这道题我们可以使用非递归回溯来解决，因为如果使用递归回溯来解决，那么代码和上道题几乎一样。在非递归的编程中，比较有技巧性的是如何来进行回溯。

代码：

class Solution:
    # @return an integer
    def totalNQueens(self, n):
        def check(k, j):  # check if the kth queen can be put in column j!
            for i in range(k):
                if board[i]==j or abs(k-i)==abs(board[i]-j):
                    return False
            return True
        board=[-1 for i in range(n)]
        row=0; col=0; sum=0
        while row<n:
            while col<n:
                if check(row, col):
                    board[row]=col
                    col=0
                    break
                else:
                    col+=1
            if board[row]==-1:　　　　　　　　　　　　　　　　　 #如果为真，即为在这一行找不到位置放置皇后
                if row==0:　　　　　　　　　　　　　　　　　　　　#如果在第0行也找不到位置放置皇后了，说明所有的情况已经迭代完毕了，执行break跳出操作。
                    break
                else:
                    row-=1                                  #这条语句用来回溯到上一行
                    col=board[row]+1　　　　　　　　　　　　　　#回溯到上一行时，皇后放置的位置要加1，也就是开始试验下一列
                    board[row]=-1　　　　　　　　　　　　　　　 #然后将这一行的值重置为-1，也就是说要重新寻找皇后的位置了
                    continue
            if row==n-1:　　　　　　　　　　　　　　　　　　　　　#当row==n-1时，说明最后一行的皇后位置也确定了，得到了一个解
                sum+=1
                col=board[row]+1
                board[row]=-1
                continue
            row+=1
        return sum

 


联系
我们