python 使用递归回溯完美解决八皇后的问题

八皇后问题描述:在一个8✖️8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法。

规则分析:

任意两个棋子不能在同一行比较好办,设置一个队列,队列里的每个元素代表一行,就能达到要求

任意两个棋子不能在同一列也比较好处理,设置的队列里每个元素的数值代表着每行棋子的列号,比如(0,7,3),表示第一行的棋子放在第一列,第二行的棋子放在第8列,第3行的棋子放在第4列(从0开始计算列号)

任意两个棋子不能在同一斜线上,可以把整个棋盘当作是一个XOY平面,原点在棋盘的左上角,斜线的斜率为1或者-1,X为列号,Y为行号,推出斜线的表达式为Y=X+n或者Y=-X+n(n为常数,斜线确定下来之后n就确定了),进而可以推导出Y-X=n或者Y+X=n。也就是说在同一斜线上的两个棋子行号与列号之和或者之差相等。X1+Y1=X2+Y2或者X1-Y1=X2-Y2。再进行变换能够得到X1-X2=Y2-Y1或者X1-X2=Y1-Y2,也就是说|X1-Y1|=Y1-Y2。即判断两个棋子是否在同一斜线上,只要判断出两个棋子的列号之差是否等于两个棋子的行号之差的绝对值就行了。

如下图:

将上述文字分析转化为代码,就可以判断棋子之间是否符合规则了(abs(num)表示取num的绝对值)

def is_rule(queen_tup, new_queen):
 """
 :param queen_tup: 棋子队列,用于保存已经放置好的棋子,数值代表相应棋子列号
 :param new_queen: 被检测棋子,数值代表列号
 :return: True表示符合规则,False表示不符合规则
 """
 num = len(queen_tup)
 for index, queen in enumerate(queen_tup):

  if new_queen == queen: # 判断列号是否相等
   return False
  if abs(new_queen-queen) == num-index: # 判断列号之差绝对值是否与行号之差相等
   return False

 return True

事实上,这段代买还可以简写,判断列号之差也可以写作是列号之差是否为0,这样就可以使用一个in来完成整个判断。修改后如下

def is_rule(queen_tup, new_queen):
 """判断棋子是否符合规则"""
 for index, queen in enumerate(queen_tup):
  if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判断表达式
   return False
 return True

接下来写一下摆放棋子的函数

摆放棋子其实有两种方法,第一种,求出8✖️8棋盘上每行放置一个棋子的所有方法,也就相当于全排列。然后再用冲突函数逐个判断是否符合规则,如符合就放入队列

第二种,在一行放入棋子,然后判断是否符合规则,符合的情况下再去放下一行,下一行如果所有位置都不符合,退回到上一行,上一行的棋子再放置一个新的位置,然后再进去下一行判断有没有符合规则的棋子的位置。这种方法叫做递归回溯,每一行就相当于是一个回溯点

这里我使用第二种方法写个函数,先上代码,然后再解释

def arrange_queen(num, queen_tup=list()):
 """
 :param num:棋盘的的行数,当然数值也等于棋盘的列数
 :param queen_tup: 设置一个空队列,用于保存符合规则的棋子的信息
 """

 for new_queen in range(num): # 遍历一行棋子的每一列

  if is_rule(queen_tup, new_queen): # 判断是否冲突

   if len(queen_tup) == num-1:  # 判断是否是最后一行
    yield [new_queen] # yield关键字

   else:
    # 若果不是最后一行,递归函数接着放置棋子
    for result in arrange_queen(num, queen_tup+[new_queen]):
     yield [new_queen] + result

如果能够理解上边函数的可以不用看下面的分析了,如果不明白,接下来我将举几个代码例子来说明上面的函数

首先是yield,这个是python里的关键字,带有yield的函数被称作为生成器函数。函数在执行的时候,遇到yield关键字会暂停函数的执行,同时返回yield右边的对象到函数被调用的地方,直到函数下次被执行,将回到yield所在的地方继续执行,如果函数执行完毕还没有遇到yield,就会抛出一个异常StopIteration。而生成器函数需要使用next方法来执行。下面的代码将解释生成器函数的执行:

def demo():

 yield 1
 yield 2
 print('end')

b = demo()  # 将生成器函数的引用传递给变量b
print(next(b)) # 第一次执行生成器函数,返回 1 同时函数暂停,打印结果
print(next(b)) # 第二次执行生成器函数,返回 2 同时函数暂停,打印结果
print(next(b)) # 第三次执行生成器函数,因为没有再遇到yield,函数执行完毕,抛出异常StopIteration

但是上述放置棋子的代码中并没用调用next方法来执行生成器函数,而是使用了for循环遍历,并且在函数执行完毕之后也没有抛出StopIteration的错误。那是因为for循环在执行的时候,会不断的自动调用next方法,并且在遇到StopIteration的时候会捕捉异常并终止循环,以下代码我将模拟一下for循环来执行生成器函数

def demo():

 yield 1
 yield 2
 print('end')

# 模拟的for循环
b = demo()
while True:
 try:
  next(b)
  """
  此段区域写for下的代码块
  """
 except StopIteration:
  break

# 实际的for循环
for i in demo():
 """
 for 下的代码块
 """
 pass

通过这个可以知道,当使用for循环驱动生成器函数的时候,如果函数执行完毕还没有遇到yield关键字,就会直接退出for循环而不会执行for循环下的代码块。值得注意的是,上边两个循环分别是调用了两次生成器函数。生成器函数在一次执行完毕之后再继续调用是不会得到结果的

了解了生成器函数与for循环是怎么驱动生成器函数之后,关于棋子的递归函数里面还有一个就是递归函数了。以前上课的时候老师将递归函数使用的例子是数值的阶乘,这里我也使用阶乘来解释一下递归函数的执行。先介绍一下阶乘:给定一个正整数n,规定n的阶乘n!=n(n-1)(n-2).....1。也就是从1到n的累乘。(0!=1,这是规定,别问我为什么......)

def a(num):
 result = num*b(num-1)
 return result

def b(num):

 result = num*c(num-1)
 return result

def c(num):
 if num == 1:
  result = 1
 return result

result = a(3)
print(result)

上述代码是函数嵌套,只能用作计算3的阶乘,我使用它来理解递归函数

a函数被调用执行的时候,传参3,然后调用函数b,同时传参3-1=2,函数b执行在调用函数c同时传参2-1=1,函数c执行,判断传参结果符合,返回数值result到函数c被调用的地方,然后与b的参数2相乘,得到新的结果赋值给b里面的result,然后再将result返回到b被调用的地方,再乘a的参数3赋值给a里面的result,再将a里的result返回到函数a被调用的地方,然后打印结果。

这就是利用函数的嵌套来执行出3!,那么如果想算10000的函数呢?难道写10000个函数?

这里发现a函数和b函数除了变量名字不一样,其余的形式都一摸一样,那么直接在a里面调用a函数,写成如下形式

def a(num):
 result = num*a(num-1)
 return result

但是这样的话,函数将不断的被调用。所以加一个函数终止的条件,变成了

def a(num):
 if num == 1:
  return 1
 else:
  return num*a(num-1)

result = a(3)
print(result)

这就是一个最简单的递归函数

分析函数的运行,函数第一次被调用,传递参数3,判断不满足终止条件。继续执行,接下来再调用函数a,传递参数3-1=2,判断不满足终止条件。继续执行,接下来再调用函数a,传递参数2-1=1,判断满足终止条件,第三次被调用的函数结束,返回1到被调用的地方,与2相乘,第二次被调用的函数结束,结果再返回到第二次函数被调用的地方,与3相乘,第一次被调用的函数结束,结果返回

这就是这个最简单的递归函数的执行过程。总结就是递归函数不断的调用自身,直至满足函数终止的条件

搞定了含有yield的生成器函数,for循环驱动生成器函数的实质,递归函数的调用,我们再来看八皇后的棋子摆放的函数,为了方便观察,将‘八皇后'改为‘四皇后',就是只算4✖️4棋盘上放置4个棋子

def arrange_queen(num, queen_tup=list()):
 """
 :param num:棋盘的的行数,当然数值也等于棋盘的列数
 :param queen_tup: 设置一个空队列,用于保存符合规则的棋子的信息
 """

 for new_queen in range(num): # 遍历一行棋子的每一列

  if is_rule(queen_tup, new_queen): # 判断是否冲突

   if len(queen_tup) == num-1:  # 判断是否是最后一行
    yield [new_queen] # yield关键字

   else:
    # 若果不是最后一行,递归函数接着放置棋子
    for result in arrange_queen(num, queen_tup+[new_queen]):
     yield [new_queen] + result

for i in arrange_queen(4):
 print(i)

执行结果是

[1,3,0,2]

[2,0,3,1]

下面描述一下函数的执行过程:

1.放置第一行棋子。函数第一次被调用,传递参数4,空列表。放置棋子在第一行第一列,判断棋子放置符合规则,判断不是最后一行,将棋子位置信息放入列表,同时生成新的列表[0]

2.放置第二行棋子。函数第二次被调用,传递参数4,列表[0]。放置棋子在第二行第一列,判断棋子不符合规则,接着放置棋子在第二行第二列,判断棋子不符合规则,再放置棋子在第二行第三列,判断符合规则,将棋子位置信息放入列表,同时生成新的列表[0,2]

3.放置第三行棋子。函数第三次被调用,传递参数4,列表[0,2]。放置棋子在第三行第一列,判断棋子不符合规则,接着放置棋子在第三行第二列,判断不符合规则,再放置棋子到第三行第三列,判断不符合规则,再放置棋子到第三行第四列,判断还是不符合规则。第三次函数调用结束

4.回到函数第二次被调用的地方,第二次被调用的函数接着放置棋子,上一次放置到了第三列,这次放到第四列,判断符合规则,将棋子位置信息放入列表,同时生成新的列表[0,3]

5.函数被调用,用于放置第三行,从第一列再依次判断到最后一列,如果符合规则,放入棋子信息,同时生成新的列表[0,3,1]

6.函数被调用,用于放置第四行,从第一列判断到最后一列,都不符合规则,函数执行完毕,回到上一级

.......

N.当前三行的棋子放入都符合规则,而且第四行也符合规则了,此时第一次遇到yield关键字,第四级函数暂停,将棋子信息放入列表[2],返回到第三级,第三级函数也将第三级符合规则的棋子信息放入列表,同时与第四级返回的列表相加,得到一个新的列表,然后遇到第三级函数的关键字函数yield,第三级函数暂停,返回了[0,2]到第二级函数.......直到第一级函数暂停,返回结果[1,3,0,2],打印结果

然后第一级函数接着执行,驱动二级函数执行,二级驱动三级执行,三级驱动四级执行....

直到所有结果打印完毕,整个函数执行完毕

整个代码为

def is_rule(queen_tup, new_queen):
 """判断棋子是否符合规则"""
 for index, queen in enumerate(queen_tup):
  if abs(new_queen-queen) in (len(queen_tup)-index, 0): # 判断表达式
   return False
 return True

def arrange_queen(num, queen_tup=list()):
 """
 :param num:棋盘的的行数,当然数值也等于棋盘的列数
 :param queen_tup: 设置一个空队列,用于保存符合规则的棋子的信息
 """

 for new_queen in range(num): # 遍历一行棋子的每一列

  if is_rule(queen_tup, new_queen): # 判断是否冲突

   if len(queen_tup) == num-1:  # 判断是否是最后一行
    yield [new_queen] # yield关键字

   else:
    # 若果不是最后一行,递归函数接着放置棋子
    for result in arrange_queen(num, queen_tup+[new_queen]):
     yield [new_queen] + result

for i in arrange_queen(8):
 print(i)

整个代码最终要的就是递归回溯的思想,如果能真正的明白,不用用什么语法或者写什么样的函数,都能轻松解决这个八皇后的问题

接下来我贴出一个八皇后的的终极版(下面的代码来源百度百科),不使用yield关键字的。可以自行理解一下

def queen(A, cur=0):
 if cur == len(A):
  print(A)
  return 0
 for col in range(len(A)):
  A[cur], flag = col, True
  for row in range(cur):
   if A[row] == col or abs(col - A[row]) == cur - row:
    flag = False
    break
  if flag:
   queen(A, cur+1)
queen([None]*8)

八皇后的所有解

[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
[0, 6, 4, 7, 1, 3, 5, 2]
[1, 3, 5, 7, 2, 0, 6, 4]
[1, 4, 6, 0, 2, 7, 5, 3]
[1, 4, 6, 3, 0, 7, 5, 2]
[1, 5, 0, 6, 3, 7, 2, 4]
[1, 5, 7, 2, 0, 3, 6, 4]
[1, 6, 2, 5, 7, 4, 0, 3]
[1, 6, 4, 7, 0, 3, 5, 2]
[1, 7, 5, 0, 2, 4, 6, 3]
[2, 0, 6, 4, 7, 1, 3, 5]
[2, 4, 1, 7, 0, 6, 3, 5]
[2, 4, 1, 7, 5, 3, 6, 0]
[2, 4, 6, 0, 3, 1, 7, 5]
[2, 4, 7, 3, 0, 6, 1, 5]
[2, 5, 1, 4, 7, 0, 6, 3]
[2, 5, 1, 6, 0, 3, 7, 4]
[2, 5, 1, 6, 4, 0, 7, 3]
[2, 5, 3, 0, 7, 4, 6, 1]
[2, 5, 3, 1, 7, 4, 6, 0]
[2, 5, 7, 0, 3, 6, 4, 1]
[2, 5, 7, 0, 4, 6, 1, 3]
[2, 5, 7, 1, 3, 0, 6, 4]
[2, 6, 1, 7, 4, 0, 3, 5]
[2, 6, 1, 7, 5, 3, 0, 4]
[2, 7, 3, 6, 0, 5, 1, 4]
[3, 0, 4, 7, 1, 6, 2, 5]
[3, 0, 4, 7, 5, 2, 6, 1]
[3, 1, 4, 7, 5, 0, 2, 6]
[3, 1, 6, 2, 5, 7, 0, 4]
[3, 1, 6, 2, 5, 7, 4, 0]
[3, 1, 6, 4, 0, 7, 5, 2]
[3, 1, 7, 4, 6, 0, 2, 5]
[3, 1, 7, 5, 0, 2, 4, 6]
[3, 5, 0, 4, 1, 7, 2, 6]
[3, 5, 7, 1, 6, 0, 2, 4]
[3, 5, 7, 2, 0, 6, 4, 1]
[3, 6, 0, 7, 4, 1, 5, 2]
[3, 6, 2, 7, 1, 4, 0, 5]
[3, 6, 4, 1, 5, 0, 2, 7]
[3, 6, 4, 2, 0, 5, 7, 1]
[3, 7, 0, 2, 5, 1, 6, 4]
[3, 7, 0, 4, 6, 1, 5, 2]
[3, 7, 4, 2, 0, 6, 1, 5]
[4, 0, 3, 5, 7, 1, 6, 2]
[4, 0, 7, 3, 1, 6, 2, 5]
[4, 0, 7, 5, 2, 6, 1, 3]
[4, 1, 3, 5, 7, 2, 0, 6]
[4, 1, 3, 6, 2, 7, 5, 0]
[4, 1, 5, 0, 6, 3, 7, 2]
[4, 1, 7, 0, 3, 6, 2, 5]
[4, 2, 0, 5, 7, 1, 3, 6]
[4, 2, 0, 6, 1, 7, 5, 3]
[4, 2, 7, 3, 6, 0, 5, 1]
[4, 6, 0, 2, 7, 5, 3, 1]
[4, 6, 0, 3, 1, 7, 5, 2]
[4, 6, 1, 3, 7, 0, 2, 5]
[4, 6, 1, 5, 2, 0, 3, 7]
[4, 6, 1, 5, 2, 0, 7, 3]
[4, 6, 3, 0, 2, 7, 5, 1]
[4, 7, 3, 0, 2, 5, 1, 6]
[4, 7, 3, 0, 6, 1, 5, 2]
[5, 0, 4, 1, 7, 2, 6, 3]
[5, 1, 6, 0, 2, 4, 7, 3]
[5, 1, 6, 0, 3, 7, 4, 2]
[5, 2, 0, 6, 4, 7, 1, 3]
[5, 2, 0, 7, 3, 1, 6, 4]
[5, 2, 0, 7, 4, 1, 3, 6]
[5, 2, 4, 6, 0, 3, 1, 7]
[5, 2, 4, 7, 0, 3, 1, 6]
[5, 2, 6, 1, 3, 7, 0, 4]
[5, 2, 6, 1, 7, 4, 0, 3]
[5, 2, 6, 3, 0, 7, 1, 4]
[5, 3, 0, 4, 7, 1, 6, 2]
[5, 3, 1, 7, 4, 6, 0, 2]
[5, 3, 6, 0, 2, 4, 1, 7]
[5, 3, 6, 0, 7, 1, 4, 2]
[5, 7, 1, 3, 0, 6, 4, 2]
[6, 0, 2, 7, 5, 3, 1, 4]
[6, 1, 3, 0, 7, 4, 2, 5]
[6, 1, 5, 2, 0, 3, 7, 4]
[6, 2, 0, 5, 7, 4, 1, 3]
[6, 2, 7, 1, 4, 0, 5, 3]
[6, 3, 1, 4, 7, 0, 2, 5]
[6, 3, 1, 7, 5, 0, 2, 4]
[6, 4, 2, 0, 5, 7, 1, 3]
[7, 1, 3, 0, 6, 4, 2, 5]
[7, 1, 4, 2, 0, 6, 3, 5]
[7, 2, 0, 5, 1, 4, 6, 3]
[7, 3, 0, 2, 5, 1, 6, 4]

最后最后,对比其他语言解决八皇后的代码量

以上这篇python 使用递归回溯完美解决八皇后的问题就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • Python字符串的全排列算法实例详解

    本文实例讲述了Python字符串的全排列算法.分享给大家供大家参考,具体如下: 题目描述 输入一个字符串,按字典序打印出该字符串中字符的所有排列.例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba. 输入描述 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母. 注意有可能重复,因此需要判断 注意list的append方法和list的+方法的区别 append方法在list后面添加元素 +方法在list后面添加l

  • 如何通过python实现全排列

    这篇文章主要介绍了如何通过python实现全排列,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下 itertools模块现成的全排列: for i in itertools.permutations('abcd',4): print ''.join(i) 相关全排列算法: def perm(l): if(len(l)<=1): return [l] r=[] for i in range(len(l)): s=l[:i]+l[i+1:] p=pe

  • 基于Python数据结构之递归与回溯搜索

    目录 1. 递归函数与回溯深搜的基础知识 2. 求子集 (LeetCode 78) 3. 求子集2 (LeetCode 90) 4. 组合数之和(LeetCode 39,40) 5. 生成括号(LeetCode 22) 6. N皇后(LeetCode 51,52) 7. 火柴棍摆正方形(LeetCode 473) 1. 递归函数与回溯深搜的基础知识 递归是指在函数内部调用自身本身的方法.能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解

  • Python循环实现n的全排列功能

    描述: 输入一个大于0的整数n,输出1到n的全排列: 例如: n=3,输出[[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]] n=4,输出[[4, 3, 2, 1], [3, 4, 2, 1], [3, 2, 4, 1], [3, 2, 1, 4], [4, 2, 3, 1], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [4, 2, 1, 3], [2, 4, 1, 3],

  • Python实现全排列的打印

    本文为大家分享了Python实现全排列的打印的代码,供大家参考,具体如下 问题:输入一个数字:3,打印它的全排列组合:123 132 213 231 312 321,并进行统计个数. 下面是Python的实现代码: #!/usr/bin/env python # -*- coding: <encoding name> -*- ''' 全排列的demo input : 3 output:123 132 213 231 312 321 ''' total = 0 def permutationCo

  • python实现全排列代码(回溯、深度优先搜索)

    从n个不同元素中任取m(m≤n)个元素,按照一定的顺序排列起来,叫做从n个不同元素中取出m个元素的一个排列.当m=n时所有的排列情况叫全排列. 公式:全排列数f(n)=n!(定义0!=1) 1 递归实现全排列(回溯思想) 1.1 思想 举个例子,比如你要对a,b,c三个字符进行全排列,那么它的全排列有abc,acb,bac,bca,cba,cab这六种可能就是当指针指向第一个元素a时,它可以是其本身a(即和自己进行交换),还可以和b,c进行交换,故有3种可能,当第一个元素a确定以后,指针移向第二

  • python 回溯法模板详解

    什么是回溯法 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 无重复元素全排列问题 给定一个所有元素都不同的list,要求返回list元素的全排列. 设n = len(list),那么这个问题可以考虑为n叉树,对这个树进行dfs,这个问题里的回溯点就是深度(也就是templist的长度)为n时,回

  • python 使用递归回溯完美解决八皇后的问题

    八皇后问题描述:在一个8✖️8的棋盘上,任意摆放8个棋子,要求任意两个棋子不能在同一行,同一列,同一斜线上,问有多少种解法. 规则分析: 任意两个棋子不能在同一行比较好办,设置一个队列,队列里的每个元素代表一行,就能达到要求 任意两个棋子不能在同一列也比较好处理,设置的队列里每个元素的数值代表着每行棋子的列号,比如(0,7,3),表示第一行的棋子放在第一列,第二行的棋子放在第8列,第3行的棋子放在第4列(从0开始计算列号) 任意两个棋子不能在同一斜线上,可以把整个棋盘当作是一个XOY平面,原点在

  • Java使用递归回溯完美解决八皇后的问题

    八皇后问题 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例.该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即:任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 解决思路 ①第一个皇后先放第一行第一列. ②第二个皇后放在第二行第一列.然后判断是否OK,如果不0K, 继续放在第二列.第三列.依次把所有列都放完,找到一个合适. ③继续第三个皇后, 还是第一列.第二列-直到第8个皇后也能放在一个不冲突的位置,算是找

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • C语言基于回溯算法解决八皇后问题的方法

    本文实例讲述了C语言基于回溯算法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 问题描述: 八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行.同一列或同一斜线上,问有多少种摆法. 问题求解: 采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行:若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可

  • javascript递归回溯法解八皇后问题

    下面给大家分享的是回溯法解八皇后, 带详细注解,这里就不多废话了. function NQueens(order) { if (order < 4) { console.log('N Queens problem apply for order bigger than 3 ! '); return; } var nQueens = []; var backTracking = false; rowLoop: for (var row=0; row<order; row++) { //若出现ro

  • python 示例分享---逻辑推理编程解决八皇后

    可以和Haskell , Prolog 一样做到模式匹配, 建立逻辑推到规则,描述问题,得出答案. from pyDatalog import pyDatalog pyDatalog.create_atoms( 'N, N1, X, Y, X0, X1, X2, X3, X4, X5, X6, X7' ) pyDatalog.create_atoms( 'ok, queens, next_queen, pred, pred2' ) size = 8 ok( X1, N, X2 ) <= ( X1

  • Python解决八皇后问题示例

    本文实例讲述了Python解决八皇后问题的方法.分享给大家供大家参考,具体如下: 八皇后问题是一个以国际象棋为背景的问题:如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后?为了达到此目的,任两个皇后都不能处于同一条横行.纵行或斜线上.八皇后问题可以推广为更一般的n皇后摆放问题:这时棋盘的大小变为n1×n1,而皇后个数也变成n2.而且仅当 n2 = 1 或 n1 ≥ 3 时问题有解. 这是一个典型的回溯算法,我们可以将问题进行分解: 首先,我们要想到某种方

  • PHP基于回溯算法解决n皇后问题的方法示例

    本文实例讲述了PHP基于回溯算法解决n皇后问题的方法.分享给大家供大家参考,具体如下: 这里对于n皇后问题就不做太多的介绍,相关的介绍与算法分析可参考前面一篇C++基于回溯法解决八皇后问题. 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向

  • python基于右递归解决八皇后问题的方法

    本文实例讲述了python基于右递归解决八皇后问题的方法.分享给大家供大家参考.具体分析如下: 凡是线性回溯都可以归结为右递归的形式,也即是二叉树,因此对于只要求一个解的问题,采用右递归实现的程序要比回溯法要优美的多. def Test(queen,n): '''这个就不用说了吧,就是检验第n(下标,0-7)行皇后的位置是否合理''' q=queen[n] for i in xrange(n): if queen[i]==q or queen[i]-q==n-i or queen[i]-q==i

  • C语言回溯法解八皇后问题(八皇后算法)

    八皇后问题(N皇后问题)的回溯法求解 一.问题描述 在一个国际象棋棋盘上放置八个皇后,使得任何两个皇后之间不相互攻击,求出所有的布棋方法,并推广到N皇后情况. 二.参考资料 啥文字都不用看,B站上有个非常详细的动画视频解说,上链接!!! Click Here! 三.源代码 #include<iostream> #include<vector> #include<string> using namespace std; void put_queen(int x, int

随机推荐