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

[leetcode]N-Queens II @ Python

原题地址: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