Python 求解N皇后问题

题目

　　需要将N个皇后放在N*N的棋盘上，条件是任何一个皇后都不能威胁其他皇后，即任何两个皇后都
不能吃掉对方。怎么实现这种情况呢？

思路

　　record[]来存储第i个皇后所在的列
　　设第i个皇后的位置为(i,record[i])，下一个摆放位置为(a,b)，当满足|record[i]-b|==|i-a|时，表示这两个皇后在一条对角线上，当满足record[i]==b时，表示在同一列，这两种情况下均不能放置皇后。
　　我们可以将递归过程设计成逐行放置皇后的过程，下面是实现代码：

解题过程

   
class Solution:
     def judge(self, record, i, j):## i 代表第几个皇后， j表示第i个皇后的列
        if i==0:
             return  True
         for k in range(0,i):
             if abs(record[k]-j)==abs(i-k) or j==record[k]:
                 return False
         return True
     def queen(self, record, i, n):#i代表第I个皇后
         if(i==n):
             return 1
         ans=0
         for j in range(n):
             if self.judge(record,i,j):
                 record[i]=j
                 ans+=self.queen(record,i+1,n)

         return ans


 a=Solution()
 n=input()
 x=int(n)
 record=[0]*x
 print(a.queen(record,0,x))

赏

很高兴和你分享