# 回溯法求解八皇后问题（python实现）

① 根据 8 皇后问题，可以把其设想为一个数组；
② 根据 8 皇后的规则，可以设想为数组上同一直线，横线，斜线的数字都 不 能相同，由此可以得出判断条件；
③ 根据判断条件之后，建立回溯点，即可解决问题。

① 检索当前行是否可以放置一个皇后；
② 利用检索过程，通过递归的方式，来确定每个皇后的位置———回溯的思想。

``````import time

def show(queen):
for i in range(0, 8):
print("(" + str(i + 1) + ", " + str(queen[i] + 1) + ")", end = " ")
print("\n")

def isNotConfict(queen, row):   #判断是否冲突
for i in range(0, row):
if queen[i] == queen[row] or abs(i - row) == abs(queen[i] - queen[row]):
return False
return True

sum = 0                         #记录解法总数

def put_queen(queen, row):      #回溯法放置皇后
if row == len(queen):       #如果到达最后一行，那么肯定得到一种新解法
show(queen)             #输出皇后位置
global sum
sum += 1                #更新解法总数
return sum
for column in range(0, len(queen)):#循环判断每列是否可以放置皇后
queen[row] = column
if isNotConfict(queen, row):
put_queen(queen, row + 1)

def main():
queen = [None] * 8
start = time.time()
put_queen(queen, 0)
end = time.time()
print("共耗时:\n" + str(end - start) + " s\n")
print("一共有" + str(sum) + "种解法")

if __name__ == '__main__':
main()
``````

``````(1, 1) (2, 5) (3, 8) (4, 6) (5, 3) (6, 7) (7, 2) (8, 4)

(1, 1) (2, 6) (3, 8) (4, 3) (5, 7) (6, 4) (7, 2) (8, 5)

(1, 1) (2, 7) (3, 4) (4, 6) (5, 8) (6, 2) (7, 5) (8, 3)

(1, 1) (2, 7) (3, 5) (4, 8) (5, 2) (6, 4) (7, 6) (8, 3)

(1, 2) (2, 4) (3, 6) (4, 8) (5, 3) (6, 1) (7, 7) (8, 5)

(1, 2) (2, 5) (3, 7) (4, 1) (5, 3) (6, 8) (7, 6) (8, 4)

(1, 2) (2, 5) (3, 7) (4, 4) (5, 1) (6, 8) (7, 6) (8, 3)

(1, 2) (2, 6) (3, 1) (4, 7) (5, 4) (6, 8) (7, 3) (8, 5)

(1, 2) (2, 6) (3, 8) (4, 3) (5, 1) (6, 4) (7, 7) (8, 5)

(1, 2) (2, 7) (3, 3) (4, 6) (5, 8) (6, 5) (7, 1) (8, 4)

(1, 2) (2, 7) (3, 5) (4, 8) (5, 1) (6, 4) (7, 6) (8, 3)

(1, 2) (2, 8) (3, 6) (4, 1) (5, 3) (6, 5) (7, 7) (8, 4)

(1, 3) (2, 1) (3, 7) (4, 5) (5, 8) (6, 2) (7, 4) (8, 6)

(1, 3) (2, 5) (3, 2) (4, 8) (5, 1) (6, 7) (7, 4) (8, 6)

(1, 3) (2, 5) (3, 2) (4, 8) (5, 6) (6, 4) (7, 7) (8, 1)

(1, 3) (2, 5) (3, 7) (4, 1) (5, 4) (6, 2) (7, 8) (8, 6)

(1, 3) (2, 5) (3, 8) (4, 4) (5, 1) (6, 7) (7, 2) (8, 6)

(1, 3) (2, 6) (3, 2) (4, 5) (5, 8) (6, 1) (7, 7) (8, 4)

(1, 3) (2, 6) (3, 2) (4, 7) (5, 1) (6, 4) (7, 8) (8, 5)

(1, 3) (2, 6) (3, 2) (4, 7) (5, 5) (6, 1) (7, 8) (8, 4)

(1, 3) (2, 6) (3, 4) (4, 1) (5, 8) (6, 5) (7, 7) (8, 2)

(1, 3) (2, 6) (3, 4) (4, 2) (5, 8) (6, 5) (7, 7) (8, 1)

(1, 3) (2, 6) (3, 8) (4, 1) (5, 4) (6, 7) (7, 5) (8, 2)

(1, 3) (2, 6) (3, 8) (4, 1) (5, 5) (6, 7) (7, 2) (8, 4)

(1, 3) (2, 6) (3, 8) (4, 2) (5, 4) (6, 1) (7, 7) (8, 5)

(1, 3) (2, 7) (3, 2) (4, 8) (5, 5) (6, 1) (7, 4) (8, 6)

(1, 3) (2, 7) (3, 2) (4, 8) (5, 6) (6, 4) (7, 1) (8, 5)

(1, 3) (2, 8) (3, 4) (4, 7) (5, 1) (6, 6) (7, 2) (8, 5)

(1, 4) (2, 1) (3, 5) (4, 8) (5, 2) (6, 7) (7, 3) (8, 6)

(1, 4) (2, 1) (3, 5) (4, 8) (5, 6) (6, 3) (7, 7) (8, 2)

(1, 4) (2, 2) (3, 5) (4, 8) (5, 6) (6, 1) (7, 3) (8, 7)

(1, 4) (2, 2) (3, 7) (4, 3) (5, 6) (6, 8) (7, 1) (8, 5)

(1, 4) (2, 2) (3, 7) (4, 3) (5, 6) (6, 8) (7, 5) (8, 1)

(1, 4) (2, 2) (3, 7) (4, 5) (5, 1) (6, 8) (7, 6) (8, 3)

(1, 4) (2, 2) (3, 8) (4, 5) (5, 7) (6, 1) (7, 3) (8, 6)

(1, 4) (2, 2) (3, 8) (4, 6) (5, 1) (6, 3) (7, 5) (8, 7)

(1, 4) (2, 6) (3, 1) (4, 5) (5, 2) (6, 8) (7, 3) (8, 7)

(1, 4) (2, 6) (3, 8) (4, 2) (5, 7) (6, 1) (7, 3) (8, 5)

(1, 4) (2, 6) (3, 8) (4, 3) (5, 1) (6, 7) (7, 5) (8, 2)

(1, 4) (2, 7) (3, 1) (4, 8) (5, 5) (6, 2) (7, 6) (8, 3)

(1, 4) (2, 7) (3, 3) (4, 8) (5, 2) (6, 5) (7, 1) (8, 6)

(1, 4) (2, 7) (3, 5) (4, 2) (5, 6) (6, 1) (7, 3) (8, 8)

(1, 4) (2, 7) (3, 5) (4, 3) (5, 1) (6, 6) (7, 8) (8, 2)

(1, 4) (2, 8) (3, 1) (4, 3) (5, 6) (6, 2) (7, 7) (8, 5)

(1, 4) (2, 8) (3, 1) (4, 5) (5, 7) (6, 2) (7, 6) (8, 3)

(1, 4) (2, 8) (3, 5) (4, 3) (5, 1) (6, 7) (7, 2) (8, 6)

(1, 5) (2, 1) (3, 4) (4, 6) (5, 8) (6, 2) (7, 7) (8, 3)

(1, 5) (2, 1) (3, 8) (4, 4) (5, 2) (6, 7) (7, 3) (8, 6)

(1, 5) (2, 1) (3, 8) (4, 6) (5, 3) (6, 7) (7, 2) (8, 4)

(1, 5) (2, 2) (3, 4) (4, 6) (5, 8) (6, 3) (7, 1) (8, 7)

(1, 5) (2, 2) (3, 4) (4, 7) (5, 3) (6, 8) (7, 6) (8, 1)

(1, 5) (2, 2) (3, 6) (4, 1) (5, 7) (6, 4) (7, 8) (8, 3)

(1, 5) (2, 2) (3, 8) (4, 1) (5, 4) (6, 7) (7, 3) (8, 6)

(1, 5) (2, 3) (3, 1) (4, 6) (5, 8) (6, 2) (7, 4) (8, 7)

(1, 5) (2, 3) (3, 1) (4, 7) (5, 2) (6, 8) (7, 6) (8, 4)

(1, 5) (2, 3) (3, 8) (4, 4) (5, 7) (6, 1) (7, 6) (8, 2)

(1, 5) (2, 7) (3, 1) (4, 3) (5, 8) (6, 6) (7, 4) (8, 2)

(1, 5) (2, 7) (3, 1) (4, 4) (5, 2) (6, 8) (7, 6) (8, 3)

(1, 5) (2, 7) (3, 2) (4, 4) (5, 8) (6, 1) (7, 3) (8, 6)

(1, 5) (2, 7) (3, 2) (4, 6) (5, 3) (6, 1) (7, 4) (8, 8)

(1, 5) (2, 7) (3, 2) (4, 6) (5, 3) (6, 1) (7, 8) (8, 4)

(1, 5) (2, 7) (3, 4) (4, 1) (5, 3) (6, 8) (7, 6) (8, 2)

(1, 5) (2, 8) (3, 4) (4, 1) (5, 3) (6, 6) (7, 2) (8, 7)

(1, 5) (2, 8) (3, 4) (4, 1) (5, 7) (6, 2) (7, 6) (8, 3)

(1, 6) (2, 1) (3, 5) (4, 2) (5, 8) (6, 3) (7, 7) (8, 4)

(1, 6) (2, 2) (3, 7) (4, 1) (5, 3) (6, 5) (7, 8) (8, 4)

(1, 6) (2, 2) (3, 7) (4, 1) (5, 4) (6, 8) (7, 5) (8, 3)

(1, 6) (2, 3) (3, 1) (4, 7) (5, 5) (6, 8) (7, 2) (8, 4)

(1, 6) (2, 3) (3, 1) (4, 8) (5, 4) (6, 2) (7, 7) (8, 5)

(1, 6) (2, 3) (3, 1) (4, 8) (5, 5) (6, 2) (7, 4) (8, 7)

(1, 6) (2, 3) (3, 5) (4, 7) (5, 1) (6, 4) (7, 2) (8, 8)

(1, 6) (2, 3) (3, 5) (4, 8) (5, 1) (6, 4) (7, 2) (8, 7)

(1, 6) (2, 3) (3, 7) (4, 2) (5, 4) (6, 8) (7, 1) (8, 5)

(1, 6) (2, 3) (3, 7) (4, 2) (5, 8) (6, 5) (7, 1) (8, 4)

(1, 6) (2, 3) (3, 7) (4, 4) (5, 1) (6, 8) (7, 2) (8, 5)

(1, 6) (2, 4) (3, 1) (4, 5) (5, 8) (6, 2) (7, 7) (8, 3)

(1, 6) (2, 4) (3, 2) (4, 8) (5, 5) (6, 7) (7, 1) (8, 3)

(1, 6) (2, 4) (3, 7) (4, 1) (5, 3) (6, 5) (7, 2) (8, 8)

(1, 6) (2, 4) (3, 7) (4, 1) (5, 8) (6, 2) (7, 5) (8, 3)

(1, 6) (2, 8) (3, 2) (4, 4) (5, 1) (6, 7) (7, 5) (8, 3)

(1, 7) (2, 1) (3, 3) (4, 8) (5, 6) (6, 4) (7, 2) (8, 5)

(1, 7) (2, 2) (3, 4) (4, 1) (5, 8) (6, 5) (7, 3) (8, 6)

(1, 7) (2, 2) (3, 6) (4, 3) (5, 1) (6, 4) (7, 8) (8, 5)

(1, 7) (2, 3) (3, 1) (4, 6) (5, 8) (6, 5) (7, 2) (8, 4)

(1, 7) (2, 3) (3, 8) (4, 2) (5, 5) (6, 1) (7, 6) (8, 4)

(1, 7) (2, 4) (3, 2) (4, 5) (5, 8) (6, 1) (7, 3) (8, 6)

(1, 7) (2, 4) (3, 2) (4, 8) (5, 6) (6, 1) (7, 3) (8, 5)

(1, 7) (2, 5) (3, 3) (4, 1) (5, 6) (6, 8) (7, 2) (8, 4)

(1, 8) (2, 2) (3, 4) (4, 1) (5, 7) (6, 5) (7, 3) (8, 6)

(1, 8) (2, 2) (3, 5) (4, 3) (5, 1) (6, 7) (7, 4) (8, 6)

(1, 8) (2, 3) (3, 1) (4, 6) (5, 2) (6, 5) (7, 7) (8, 4)

(1, 8) (2, 4) (3, 1) (4, 3) (5, 6) (6, 2) (7, 7) (8, 5)

0.05162310600280762 s

``````
• 03:06