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 皇后问题。

Open Compiler
#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; }
Open Compiler
#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(); }
Open Compiler
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(); } }
Open Compiler
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
广告