- def queene(n):
- #生成一个一维数组, 下标存储行, 值存储列
- helpQueene([-1]*n,0,n)
- def helpQueene(columnPositions,rowIndex,n):
- global count
- #回溯标志, 即 N 个皇后都找到了相应的位置
- if rowIndex == n:
- #计算总共有多少种
- count+=1
- #打印输出
- printSolution(columnPositions,n)
- return
- #0-7 共 8 列
- for column in range(n):
- #rowIndex 的值先从 0 开始, 相当于 (rowIndex,column) 是一个皇后的坐标, 共(0,0)...(7,7)
- columnPositions[rowIndex]=column
- #放置一个就判断是否有效, 如果有效, 就到下一行放置
- if isValid(columnPositions,rowIndex):
- helpQueene(columnPositions,rowIndex+1,n)
- def isValid(columnPositions,rowIndex):
- #rowIndex: 目前放置的行数, 遍历这几行皇后的坐标
- for i in range(rowIndex):
- #如果位于同一列, 则返回 False
- if columnPositions[i] == columnPositions[rowIndex]:
- return False
- #如果位于对角线上, 就返回 False
- elif abs(columnPositions[i]-columnPositions[rowIndex])==(rowIndex-i):
- return False
- #否则返回 True
- return True
- def printSolution(columnPositions,n):
- for row in range(n):
- line=""
- for column in range(n):
- if columnPositions[row]==column:
- line+="Q"
- else:
- line+='_'
- print(line)
- print("\n")
- queene(8)
- print(count)
部分输出:
最后有: 92 种
来源: http://www.bubuko.com/infodetail-3301247.html