Python實(shí)現(xiàn)八皇后問題示例代碼

八皇后問題描述

問題： 國際象棋棋盤是8 * 8的方格，每個(gè)方格里放一個(gè)棋子?；屎筮@種棋子可以攻擊同一行或者同一列或者斜線（左上左下右上右下四個(gè)方向）上的棋子。在一個(gè)棋盤上如果要放八個(gè)皇后，使得她們互相之間不能攻擊（即任意兩兩之間都不同行不同列不同斜線），求出一種（進(jìn)一步的，所有）布局方式。

首先，我們想到遞歸和非遞歸兩類算法來解決這個(gè)問題。首先說說遞歸地算法。

很自然的，我們可以基于行來做判斷標(biāo)準(zhǔn)。八個(gè)皇后都不同行這是肯定的，也就說每行有且僅有一個(gè)皇后，問題就在于皇后要放在哪個(gè)列。當(dāng)然八個(gè)列下標(biāo)也都不能有相同，除此之外還要保證斜線上不能有重疊的皇后。

第一個(gè)需要解決的小問題就是，如何用數(shù)學(xué)的語言來表述斜線上重疊的皇后。其實(shí)我們可以看到，對于位于(i,j)位置的皇后而言，其四個(gè)方向斜線上的格子下標(biāo)分別是 (i-n,j+n), (i-n,j-n), (i+n,j-n), (i+n,j+n)。當(dāng)然i和j的±n都要在[0,7]的范圍內(nèi)，保持不越界。暫時(shí)拋開越界限制不管，這個(gè)關(guān)系其實(shí)就是： 目標(biāo)格子(a,b)和本格子(i,j)在同一條斜線上 等價(jià)于 |a - i| == |b - j| 。

然后，從遞歸的思想來看，我們在從第一行開始給每一行的皇后確定一個(gè)位置。每來到新的一行時(shí)，對本行的所有可能位置（皇后放在這個(gè)位置和前面所有已放置的皇后無沖突）分別進(jìn)行遞歸地深入；若某一行可能的位置數(shù)為0，則表明這是一條死路，返回上一層遞歸尋找其他辦法；若來到的這一行是第九行（不存在第九行，只不過是說明前八行都已經(jīng)正確配置，已經(jīng)得到一個(gè)解決方案），這說明得到解決方案。

可以看到，尋找一行內(nèi)皇后應(yīng)該擺放的位置這是個(gè)遞歸過程，并且在進(jìn)入遞歸時(shí)，應(yīng)該要告訴這個(gè)過程的東西包括兩個(gè)： 1. 之前皇后放置的狀態(tài)， 2. 現(xiàn)在是第幾行。

所以，遞歸主體函數(shù)可以設(shè)計(jì)為 EightQueen(board, row)，其中board表示的是當(dāng)前棋盤的狀態(tài)（比如一個(gè)二維數(shù)組，0表示未放置，1表示放有皇后的狀態(tài)）。另外還可以有一個(gè)check(board,pos)，pos可以是一個(gè)(x,y)元組，check函數(shù)用來返回以當(dāng)前的board棋盤狀態(tài)，如果在pos再放置一個(gè)皇后是否會(huì)有沖突。

基于上面的想法，初步實(shí)現(xiàn)如下：

def check(board,pos):
 # check函數(shù)暫時(shí)先不實(shí)現(xiàn)
 pass

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 來到不存在的第九行了
  print board
  return True # 一定要return一個(gè)True，理由在下面
 for possibleY in range(blen):
  if check(board,(row,possibleY)):
   board[row][possibleY] = 1 # 放置一個(gè)Queen
   if not EightQueen(board,row+1): # 這里其實(shí)是本行下面所有行放置皇后的遞歸入口。但是如果最終這條路沒有找到一個(gè)解，那么
    # 此時(shí)應(yīng)該將剛才放置的皇后收回，再去尋找下一個(gè)可能的解
    board[row][possibleY] = 0
   else:
    return True
 return False

最開始，可能在回歸返回條件那里面不會(huì)想到要return True，而只是return。對應(yīng)的，下面主循環(huán)中放置完Queen之后也只是簡單地遞歸調(diào)用EightQueen，不會(huì)做邏輯判斷。但是很快可以發(fā)現(xiàn)這樣做存在一個(gè)問題，即當(dāng)某一層遞歸中for possibleY這個(gè)循環(huán)走完卻沒有找到一個(gè)合適的解（即本行無合適位置），此時(shí)返回上一行，上一行的possibleY右移一格，此時(shí)之前放在這一行的Queen的位置仍然是1。這樣之后本行的所有check肯定都是通不過的。所以我們需要設(shè)計(jì)一個(gè)機(jī)制，使得第一個(gè)possibleY沒有找到合理的最終解決方案（這里就加上了一個(gè)判斷條件），要右移一格到下一個(gè)possibleY時(shí)將本格的Queen收回。

這個(gè)判斷條件就是如果某層遞歸for possibleY循環(huán)整個(gè)走完未找到結(jié)果返回False（EightQueen整個(gè)函數(shù)最后的返回），上一層根據(jù)這個(gè)False反饋把前一個(gè)Queen拿掉；如果找到了某個(gè)結(jié)果那么就可以一路return True回來，結(jié)束函數(shù)的運(yùn)行。

另外，如果只是獲取一個(gè)解的話，可以考慮在if row == blen的時(shí)候，打印出board，然后直接sys.exit(0)。此時(shí)就只需要for possibleY循環(huán)完了之后return一個(gè)False就可以了。當(dāng)然主循環(huán)中對于遞歸的返回的判斷 if not EightQueen還是需要的。

上面沒有實(shí)現(xiàn)check函數(shù)。其實(shí)仔細(xì)想一下，如果按照上面的設(shè)想來實(shí)現(xiàn)check函數(shù)還是有點(diǎn)困難的。比如令 x,y = pos，盡管此時(shí)我們只需要去檢查那些行下標(biāo)小于x的board中的行，但是對于每一行中我們還是要一個(gè)個(gè)去遍歷，找到相關(guān)行中值是1的那個(gè)格子（突然發(fā)現(xiàn)這個(gè)是one-hot模式誒哈哈），然后將它再和x,y這個(gè)位置做沖突判斷。所以但是這個(gè)check函數(shù)復(fù)雜度就可能會(huì)達(dá)到O(n^2)，再套上外面的循環(huán)，復(fù)雜度蹭蹭往上漲。下面是check函數(shù)的一個(gè)可能的實(shí)現(xiàn)：

def check(board,pos):
 x,y = pos
 blen = len(board)
 for i in range(x):
  for j in range(blen):
   if board[i][j] == 1:
    if j == y or abs(j-y) == abs(i-x):
     return False
 return True

其實(shí)可以看到，我們花了一層循環(huán)在尋找某行中的one-hot，那些大量的0值元素是我們根本不關(guān)心的。換句話說，對于board這個(gè)二維數(shù)組，其實(shí)我們真正關(guān)心的是每行中one-hot值的下標(biāo)值。自然我們就可以想到，能不能將board轉(zhuǎn)化為一個(gè)一維數(shù)組，下標(biāo)本身就代表了board中的某一行，然后值是指這一行中皇后放在第幾列。

如果是這樣的話，那么程序就需要改造，首先是check函數(shù)要根據(jù)新的board數(shù)據(jù)結(jié)構(gòu)做一些調(diào)整：

def check(board,row,col):
 i = 0
 while i < row:
  if abs(col-board[i]) in (0,abs(row-i)):
   return False
  i += 1
 return True

可以看到，改變二維數(shù)組board變?yōu)橐痪S數(shù)組之后，我們可以在O(1)的時(shí)間就確定row行之前每一行擺放的位置，并將其作為參考進(jìn)行每一行的沖突判斷。

然后是主函數(shù)的修改：

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 來到不存在的第九行了
  print board
  return True
 col = 0
 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):
 '''為了更友好地展示結(jié)果 方便觀察'''
 import sys
 for i,col in enumerate(board):
  sys.stdout.write('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))
  print ''

總的結(jié)構(gòu)，和沒修改之前是類似的，只不過在主循環(huán)中，從上面的possibleY作為游標(biāo)去設(shè)置 - 去除 一個(gè)位置的放置狀態(tài)，這種方式改為了簡單的col += 1。改成col+=1的好處就是當(dāng)某輪遞歸以失敗告終，返回上層遞歸之后，就不用再去特地收回之前放置好的Queen，而是可以直接讓col += 1,。

printBoard函數(shù)可以將一維數(shù)組的board狀態(tài)很直觀地展現(xiàn)出來：

■ □ □ □ □ □ □ □
□ □ □ □ ■ □ □ □
□ □ □ □ □ □ □ ■
□ □ □ □ □ ■ □ □
□ □ ■ □ □ □ □ □
□ □ □ □ □ □ ■ □
□ ■ □ □ □ □ □ □
□ □ □ ■ □ □ □ □

所有結(jié)果

上面的程序多只是生成了一個(gè)結(jié)果，而實(shí)際上八皇后可以有很多種可能的布局。如何才能求得所有結(jié)果？其實(shí)只要小小地修改一下上面的程序就可以了。

以上面修改過后一維數(shù)組維護(hù)棋盤狀態(tài)為例。程序在碰到一次row == blen的情況之后就返回了True，然后遞歸一層層地返回True直到最上層。所以找到一個(gè)解決方案之后，程序就會(huì)退出了。

反過來，如果獲得一個(gè)解決方案之后，不判斷EightQueen函數(shù)的返回，此時(shí)函數(shù)會(huì)繼續(xù)執(zhí)行col += 1,將狀態(tài)搜尋繼續(xù)下去，如此收集狀態(tài)的任務(wù)在row == blen的判斷中，（注意這里的return可不能刪，這里需要一個(gè)return來提示遞歸的終結(jié)條件），而對于每條遞歸路徑總是窮盡所有可能再回頭，這樣就可以獲得到所有可能了：

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 來到不存在的第九行了
  print board
  return True
 col = 0
 while col < blen:
  if check(board,row,col):
   board[row] = col
   if EightQueen(board,row+1):
    # return True 去掉這里即可，或者直接刪除掉整個(gè)判斷，只留下單一個(gè)EightQueen(board,row+1)
    pass
  col += 1
 return False

示例結(jié)果：

[0, 4, 7, 5, 2, 6, 1, 3]
[0, 5, 7, 2, 6, 3, 1, 4]
[0, 6, 3, 5, 7, 1, 4, 2]
[0, 6, 4, 7, 1, 3, 5, 2]
[1, 3, 5, 7, 2, 0, 6, 4]
[1, 4, 6, 0, 2, 7, 5, 3]
[1, 4, 6, 3, 0, 7, 5, 2]
[1, 5, 0, 6, 3, 7, 2, 4]
[1, 5, 7, 2, 0, 3, 6, 4]
…… 總共有92種布局方案

非遞歸

非遞歸解這個(gè)問題，很顯然是要去維護(hù)一個(gè)stack來保存一個(gè)路徑了。簡單來說，這個(gè)棧中維護(hù)的應(yīng)該是“尚未嘗試去探索的可能”，當(dāng)我開始檢查一個(gè)特定的位置，如果檢查通過，那么應(yīng)該做的是首先將本位置右邊一格加入棧，然后再把下一行的第一個(gè)格子加入棧。注意前半個(gè)操作很容易被忽視，但是如果不將本位置右邊一格入棧，那么如果基于本格有皇后的情況進(jìn)行的遞歸最終沒有返回一個(gè)結(jié)果的話，接下來就不知道往哪走了。如果使用了棧，那么用于掃描棋盤的游標(biāo)就不用自己在循環(huán)里+=1了，循環(huán)中游標(biāo)的移動(dòng)全權(quán)交給棧去維護(hù)。

代碼如下：

def EightQueen(board):
 blen = len(board)
 stack = Queue.LifoQueue()
 stack.put((0,0)) # 為了自洽的初始化
 while not stack.empty():
  i,j = stack.get()
  if check(board,i,j): # 當(dāng)檢查通過
   board[i] = j # 別忘了放Queen
   if i >= blen - 1:
    print board # i到達(dá)最后一行表明已經(jīng)有了結(jié)果
    break
   else:
    if j < blen - 1: # 雖然說要把本位置右邊一格入棧，但是如果本位置已經(jīng)是行末尾，那就沒必要了
     stack.put((i,j+1))
    stack.put((i+1,0)) # 下一行第一個(gè)位置入棧，準(zhǔn)備開始下一行的掃描
  elif j < blen - 1:
   stack.put((i,j+1)) # 對于未通過檢驗(yàn)的情況，自然右移一格即可

顯然，把break去掉就是求所有解了

C語言版

#include <stdio.h>

static int board[8] = {};
int board_size = sizeof(board)/sizeof(int);

int check(int *board,int row){
 int i = 0;
 while(i < row){
  if(board[i] == board[row] || row - i == board[row] - board[i] || row - i == board[i] - board[row]){
   return 0;
  }
  i++;
 }
 // printf("board[%d]: %d\n",row,board[row]);
 return 1;
}

void print_board(int *board){
 int i;
 int size = board_size;
 for(i=0;i<size;i++){
  printf("%d,",board[i]);
 }
 printf("\n");
 i = 0;
 while (i < size){
  int j;
  for (j=0;j<size;j++){
   if(j == board[i]){
    printf("%s ","■ ");
   }
   else{
    printf("%s ","□ ");
   }
  }
  printf("\n");
  i++;
 }
}

int eight_queen(int *board,int row){
 if (row == 8){
  print_board(board);
  return 1;
 }
 board[row] = 0;
 while (1){
  if (check(board,row) && eight_queen(board,row+1)){
    return 1;
  }
  else{
   if(++board[row] >= 8){
    break;
   }
  }
 }

 return 0; 
}

int main(){
 eight_queen(board,0);
 // print_board(board);
 return 0;
}

總結(jié)

以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，如果有疑問大家可以留言交流，謝謝大家對億速云的支持。