n皇后问题（回溯法）—

八皇后问题

问题：国际象棋棋盘是8 * 8的方格，每个方格里放一个棋子。皇后这种棋子可以攻击同一行或者同一列或者斜线（左上左下右上右下四个方向）上的棋子。在一个棋盘上如果要放八个皇后，使得她们互相之间不能攻击（即任意两两之间都不同行不同列不同斜线），求出一种（进一步的）布局方式。

【来源： https://www.cnblogs.com/franknihao/p/9416145.html 】具体讲解与实现

1 def check(board,row,col):

2     i = 0

3     while i < row:

4         if abs(col-board[i]) in (0,abs(row-i)):

5             return False

6         i += 1

7     return True

 1 def EightQueen(board,row):

 2     blen = len(board)

 3     if row == blen:

 4         print(board)

 5         return True

 6     col = 0

 7     while col < blen:

 8         if check(board,row,col):

 9             board[row] = col

10             if EightQueen(board,row+1):

11                 return True

12         col += 1

13     return False

1 def printBoard(board):

2     import sys

3     for i,col in enumerate(board):

4         sys.stdout.write('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))

5         print( )

主函数调用：

1 board = [ [0]*8 for row in range(8) ]

2 EightQueen(board,0)

3 printBoard(board)

运行结果：

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

2 ■ □ □ □ □ □ □ □

3 □ □ □ □ ■ □ □ □

4 □ □ □ □ □ □ □ ■

5 □ □ □ □ □ ■ □ □

6 □ □ ■ □ □ □ □ □

7 □ □ □ □ □ □ ■ □

8 □ ■ □ □ □ □ □ □

9 □ □ □ ■ □ □ □ □

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

巴特西

n皇后问题（回溯法）——Python实现

最新文章

热门文章