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
打印页面
上一页
下一页
广告
© . All rights reserved.