N 皇后問題

上一頁
下一頁

什麼是 N 皇后問題？

在N 皇后問題中，我們給定一個NxN的棋盤，我們必須在棋盤上放置N個皇后，使得任何兩個皇后都不互相攻擊。如果皇后位於其路徑上的水平、垂直或對角線上，則一個皇后將攻擊另一個皇后。解決 N 皇后難題最流行的方法是回溯法。

輸入輸出場景

假設給定的棋盤大小為 4x4，我們必須在其中排列正好 4 個皇后。解決方案排列如下圖所示：

N Queen Problem

最終的解決方案矩陣將是：

0 0 1 0 
1 0 0 0 
0 0 0 1 
0 1 0 0

解決 N 皇后問題的回溯法

在解決 N 皇后問題的樸素方法中，演算法會生成所有可能的解決方案。然後，它逐一探索所有解決方案。如果生成的解決方案滿足問題的約束條件，則列印該解決方案。

按照以下步驟使用回溯法解決 N 皇后問題：

  • 將第一個皇后放在棋盤的左上角單元格中。

  • 將皇后放在第一個單元格後，將該位置標記為解決方案的一部分，然後遞迴檢查這是否會導致解決方案。

  • 現在，如果放置皇后不會導致解決方案，則返回第一步，並將皇后放置在其他單元格中。重複此過程，直到嘗試完所有單元格。

  • 如果放置皇后返回導致解決方案，則返回 TRUE。

  • 如果所有皇后都已放置，則返回 TRUE。

  • 如果嘗試完所有行但未找到解決方案，則返回 FALSE。

示例

以下示例說明如何在各種程式語言中使用 5 個皇后解決 N 皇后問題。

C C++ Java Python
#include<stdio.h>
#define BOARD_SIZE 5
void displayChess(int chBoard[BOARD_SIZE][BOARD_SIZE]) {
   for (int row = 0; row < BOARD_SIZE; row++) {
      for (int col = 0; col < BOARD_SIZE; col++)
         printf("%d ", chBoard[row][col]);
      printf("\n");
   }
}
int isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
   // checking if queen is in the left or not    
   for (int i = 0; i < crntCol; i++)    
      if (chBoard[crntRow][i])
         return 0;
   for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
      //checking if queen is in the left upper diagonal or not
      if (chBoard[i][j])       
         return 0;
   for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
      //checking if queen is in the left lower diagonal or not
      if (chBoard[i][j])      
         return 0;
   return 1;
}
int solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
   //when N queens are placed successfully
   if (crntCol >= BOARD_SIZE)           
      return 1;
   // checking placement of queen is possible or not
   for (int i = 0; i < BOARD_SIZE; i++) {     
      if (isQueenPlaceValid(chBoard, i, crntCol)) {
         //if validate, place the queen at place (i, col)
         chBoard[i][crntCol] = 1;     
         //Go for the other columns recursively
         if (solveProblem(chBoard, crntCol + 1))    
            return 1;          
         //When no place is vacant remove that queen   
         chBoard[i][crntCol] = 0;        
      }
   }
   return 0;      
}
int displaySolution() {
   int chBoard[BOARD_SIZE][BOARD_SIZE];
   for(int i = 0; i < BOARD_SIZE; i++)
      for(int j = 0; j < BOARD_SIZE; j++)
         //set all elements to 0
         chBoard[i][j] = 0;      
   //starting from 0th column
   if (solveProblem(chBoard, 0) == 0) {     
      printf("Solution does not exist");
      return 0;
   }
   displayChess(chBoard);
   return 1;
}
int main() {
   displaySolution();
   return 0;
}

#include<iostream>
using namespace std;
#define BOARD_SIZE 5
void displayChess(int chBoard[BOARD_SIZE][BOARD_SIZE]) {
   for (int row = 0; row < BOARD_SIZE; row++) {
      for (int col = 0; col < BOARD_SIZE; col++)
         cout << chBoard[row][col] << " ";
      cout << endl;
   }
}
bool isQueenPlaceValid(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntRow, int crntCol) {
   // checking if queen is in the left or not
   for (int i = 0; i < crntCol; i++)    
      if (chBoard[crntRow][i])
         return false;
   for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
      //checking if queen is in the left upper diagonal or not
      if (chBoard[i][j])       
         return false;
   for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
      //checking if queen is in the left lower diagonal or not
      if (chBoard[i][j])      
         return false;
   return true;
}
bool solveProblem(int chBoard[BOARD_SIZE][BOARD_SIZE], int crntCol) {
   //when N queens are placed successfully
   if (crntCol >= BOARD_SIZE)           
      return true;
   // checking placement of queen is possible or not
   for (int i = 0; i < BOARD_SIZE; i++) {     
      if (isQueenPlaceValid(chBoard, i, crntCol)) {
         //if validate, place the queen at place (i, col)
         chBoard[i][crntCol] = 1;     
         //Go for the other columns recursively
         if (solveProblem(chBoard, crntCol + 1))    
            return true;          
         //When no place is vacant remove that queen   
         chBoard[i][crntCol] = 0;        
      }
   }
   return false;      
}
bool displaySolution() {
   int chBoard[BOARD_SIZE][BOARD_SIZE];
   for(int i = 0; i < BOARD_SIZE; i++)
      for(int j = 0; j < BOARD_SIZE; j++)
         //set all elements to 0
         chBoard[i][j] = 0;      
   //starting from 0th column
   if (solveProblem(chBoard, 0) == false) {     
      cout << "Solution does not exist";
      return false;
   }
   displayChess(chBoard);
   return true;
}
int main() {
   displaySolution();
}

public class Main {
   static final int BOARD_SIZE = 5;
   static void displayChess(int chBoard[][]) {
      for (int row = 0; row < BOARD_SIZE; row++) {
         for (int col = 0; col < BOARD_SIZE; col++)
            System.out.print(chBoard[row][col] + " ");
         System.out.println();
      }
   }
   static boolean isQueenPlaceValid(int chBoard[][], int crntRow, int crntCol) {
      // checking if queen is in the left or not
      for (int i = 0; i < crntCol; i++)
         if (chBoard[crntRow][i] == 1)
            return false;
      for (int i = crntRow, j = crntCol; i >= 0 && j >= 0; i--, j--)
         //checking if queen is in the left upper diagonal or not
         if (chBoard[i][j] == 1)
            return false;
      for (int i = crntRow, j = crntCol; j >= 0 && i < BOARD_SIZE; i++, j--)
         //checking if queen is in the left lower diagonal or not
         if (chBoard[i][j] == 1)
            return false;
      return true;
   }
   static boolean solveProblem(int chBoard[][], int crntCol) {
      //when N queens are placed successfully
      if (crntCol >= BOARD_SIZE)
         return true;
      // checking placement of queen is possible or not
      for (int i = 0; i < BOARD_SIZE; i++) {
         if (isQueenPlaceValid(chBoard, i, crntCol)) {
            //if validate, place the queen at place (i, col)
            chBoard[i][crntCol] = 1;
            //Go for the other columns recursively
            if (solveProblem(chBoard, crntCol + 1))
               return true;
            //When no place is vacant remove that queen
               chBoard[i][crntCol] = 0;
         }
      }
      return false;
   }
   static boolean displaySolution() {
      int chBoard[][] = new int[BOARD_SIZE][BOARD_SIZE];
      for(int i = 0; i < BOARD_SIZE; i++)
         for(int j = 0; j < BOARD_SIZE; j++)
            //set all elements to 0
            chBoard[i][j] = 0;
      //starting from 0th column
      if (!solveProblem(chBoard, 0)) {
         System.out.println("Solution does not exist");
         return false;
      }
      displayChess(chBoard);
      return true;
   }
   public static void main(String[] args) {
      displaySolution();
   }
}

BOARD_SIZE = 5

def displayChess(chBoard):
    for row in range(BOARD_SIZE):
        for col in range(BOARD_SIZE):
            print(chBoard[row][col], end=" ")
        print()

def isQueenPlaceValid(chBoard, crntRow, crntCol):
    # checking if queen is in the left or not
    for i in range(crntCol):
        if chBoard[crntRow][i]:
            return False
    for i, j in zip(range(crntRow, -1, -1), range(crntCol, -1, -1)):
        #checking if queen is in the left upper diagonal or not
        if chBoard[i][j]:
            return False
    for i, j in zip(range(crntRow, BOARD_SIZE), range(crntCol, -1, -1)):
        #checking if queen is in the left lower diagonal or not
        if chBoard[i][j]:
            return False
    return True

def solveProblem(chBoard, crntCol):
    #when N queens are placed successfully
    if crntCol >= BOARD_SIZE:
        return True
    # checking placement of queen is possible or not
    for i in range(BOARD_SIZE):
        if isQueenPlaceValid(chBoard, i, crntCol):
            #if validate, place the queen at place (i, col)
            chBoard[i][crntCol] = 1
            #Go for the other columns recursively
            if solveProblem(chBoard, crntCol + 1):
                return True
            #When no place is vacant remove that queen
            chBoard[i][crntCol] = 0
    return False

def displaySolution():
    chBoard = [[0 for _ in range(BOARD_SIZE)] for _ in range(BOARD_SIZE)]
    #starting from 0th column
    if not solveProblem(chBoard, 0):
        print("Solution does not exist")
        return False
    displayChess(chBoard)
    return True

if __name__ == "__main__":
    displaySolution()

輸出

1 0 0 0 0 
0 0 0 1 0 
0 1 0 0 0 
0 0 0 0 1 
0 0 1 0 0
列印頁面
上一頁
下一頁
廣告