Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

n皇后问题(回溯法)——Python实现

点灯非烛伊丶 2019-10-18 00:17:00 阅读数:23 评论数:0 点赞数:0 收藏数:0

八皇后问题
问题: 国际象棋棋盘是8 * 8的方格,每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线(左上左下右上右下四个方向)上的棋子。在一个棋盘上如果要放八个皇后,使得她们互相之间不能攻击(即任意两两之间都不同行不同列不同斜线),求出一种(进一步的)布局方式。
 
【来源: https://www.cnblogs.com/franknihao/p/9416145.html 】具体讲解与实现
 
 def check(board,row,col):
     i =     while i < row:
         if abs(col-board[i]) in (0,abs(row-i)):
             return False
         i += 1
     return True
 def EightQueen(board,row):
     blen = len(board)
     if row == blen:
         print(board)
         return True
     col =     while col < blen:
         if check(board,row,col):
             board[row] = col
             if EightQueen(board,row+1):
                 return True
         col += 1
     return False
 def printBoard(board):
     import sys
     for i,col in enumerate(board):
         sys.stdout.write('' * col + '' + '' * (len(board) - 1 - col))
         print( )

主函数调用:

 board = [ [0]*8 for row in range(8) ]  
 EightQueen(board,0)
 printBoard(board)

运行结果:

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

 此代码只能输出一种结果,实际上n皇后问题的解有多种。

版权声明
本文为[点灯非烛伊丶]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/aiyou-3344520/p/11696015.html