赞
踩
八皇后问题,是一个古老而著名的问题,问题如下:
在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。
上边是一个8*8的国际棋盘,可以看到棋盘中的每个格子都标有数字。每个数字都是两位,十位数字表示该格子所在的行,而个位数字表示该格子所在的列。
这样不难发现,处在同一行的两个格子其十位数都相同,处在同一列的两个格子其个位数都相同,处在同一斜线的两个格子有:|两个数字个位数的差|=|两个数字十位数的差|。
主要的三个限制条件明白了,接下来我们选择一种数据结构对“皇后”进行存储。很明显,我们可以选择二维数组。但是还可以选择一维数组。在这里我们选择一维数组。
为什么选择一维数组呢?
1.因为一行只放一个皇后,很符合我们一维数组的存放特性,即一个索引对应一个元素。
2.相对于二维数组,一位数组比较简单,更适合初学者。
我们以皇后所在的行标作为一位数组的索引,皇后所在的列标作为该索引对应的元素,例如arr[3]=5,代表第三行的皇后在第五列。
下边我们以python为例来解决这个问题。
num=0 def eight_queen(arr,finish_line=0): if finish_line == len(arr): #如果放置皇后成功的行数与数组中的元素个数一致(即棋盘的行数)则认为完成了一种摆法 global num #将上边定义的num定义为全局变量 这样才能在后边对其进行自加操作 num+=1 print("第%s种摆法:" % num) for i in range(8): print((i,arr[i])) return # break for stand in range(len(arr)): #对整个列进行扫描,将列标的标号赋值给数组中对应的元素 arr[finish_line] = stand flag = True for line in range(finish_line): if arr[line] == stand or abs(arr[line]-stand) == finish_line-line: #有皇后与当前放置的皇后处于同一列或同一斜线上 flag = False # stand-=1 if flag==True: eight_queen(arr,finish_line+1) if __name__ == '__main__': eight_queen([None]*8) if num != 0: print("一共有%s种摆法" % num) else: print("无解")
对于初学者理解可能不是特别轻松,所以在这里我们总结一个的定式,再遇到此类问题时直接套用以下定式即可。下边再讲的相关问题我们就套用以下定式。
num=0 #全局变量代表方法的数量 def model(arr,finish_row=0): if finish_row == len(arr): #完成了一种方法 global num num+=1 return for x in range(循环边界): 具体操作 #对列表的需求操作 flag = True for y in range(循环边界): #找不符合条件的要求 if 找不符合要求的情况: flag = False if flag==True: #完成了一行摆放后递归调用 model(arr,finish_row+1) if __name__ == '__main__': model() #调用即可 print(num) #输出方法数
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。