这个 皇后之谜 是放置N的问题吗 国际象棋 皇后区 在N×N棋盘上，这样就不会有两个皇后互相威胁。因此，解决方案要求两个皇后不共享同一行、列或对角线。
null
N-Queen的回溯算法已经讨论过了 在这里 .在回溯解决方案中，我们遇到死角时会回溯。 在分枝定界解中，在建立了部分解之后，我们发现没有必要再深入下去，因为我们将进入死胡同 .
让我们从描述回溯解决方案开始。“我们的想法是从最左边的列开始，在不同的列中逐个放置皇后。当我们在列中放置皇后时，我们会检查与已放置皇后的冲突。在当前列中，如果我们找到一行没有冲突，我们会将此行和列标记为解决方案的一部分。如果由于冲突而找不到这样的行，我们会回溯并返回false。”
- 对于第一个皇后，共有8种可能性，因为我们可以将第一个皇后放置在第一列的任何一行中。让我们把皇后一号放在第三排。
- 排在第一位女王之后，第二位女王还有7种可能性。但是等等，我们真的没有7种可能性。我们不能将Queen 2放在第2、3或4行，因为这些单元格正受到Queen 1的攻击。因此，Queen 2只剩下8–3=5个有效位置。
- 在为Queen 2选择了一个位置后，Queen 3的选择就更少了，因为其列中的大多数单元都受到前两个Queen的攻击。
我们需要找出一种有效的方法来跟踪哪些细胞受到攻击。在之前的解决方案中，我们保留了一个8×8的布尔矩阵，并在每次放置皇后时更新它，但这需要线性时间来更新，因为我们需要检查安全单元。 基本上，我们必须确保四件事： 1.没有两个女王共用一个专栏。 2.没有两个皇后在一起。 3.没有两个皇后共享从右上到左下的对角线。 4.没有两个皇后共享从左上到右下的对角线。
第一是自动的，因为我们存储解决方案的方式。对于数字2、3和4，我们可以在O（1）时间内执行更新。我们的想法是保持 三个布尔数组告诉我们哪些行和哪些对角线被占用 .
让我们先做一些预处理。让我们创建两个nxn矩阵，一个用于/对角线，另一个用于对角线。让我们分别称它们为slashCode和backslashCode。诀窍是用这样一种方式来填充它们：两个皇后共享同一个/对角线，在矩阵slashCode中具有相同的值，如果它们共享相同的-对角线，则在反斜杠码矩阵中具有相同的值。 对于N x N矩阵，使用以下公式填写斜杠代码和反斜杠代码矩阵—— slashCode[row][col]=行+列 反斜杠代码[行][列]=行–列+（N-1）
使用上述公式将得到以下矩阵
反斜杠代码中的“N–1”用于确保代码永远不会为负，因为我们将使用这些代码作为数组中的索引。 现在，在我们将queen i放在j行之前，我们首先检查是否使用了j行（使用数组存储行信息）。然后我们检查是否使用了斜杠代码（j+i）或反斜杠代码（j–i+7）（保留两个数组，它们将告诉我们哪些对角线被占用）。如果是，那么我们必须尝试皇后i的不同位置。如果不是，那么我们将该行和两条对角线标记为已使用，并在皇后i+1上递归。在递归调用返回之后，在尝试queen i的另一个位置之前，我们需要再次将行、斜杠代码和反斜杠代码重置为未使用，就像前面注释中的代码一样。
以下是上述想法的实施情况——
C++
/* C++ program to solve N Queen Problem using Branch and Bound */ #include <iostream> # include <string.h> using namespace std; #define N 8 /* A utility function to print solution */ void printSolution( int board[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) cout << " " << board[i][j]; cout << "" ; } } /* A Optimized function to check if a queen can be placed on board[row][col] */ bool isSafe( int row, int col, int slashCode[N][N], int backslashCode[N][N], bool rowLookup[], bool slashCodeLookup[], bool backslashCodeLookup[] ) { if (slashCodeLookup[slashCode[row][col]] || backslashCodeLookup[backslashCode[row][col]] || rowLookup[row]) return false ; return true ; } /* A recursive utility function to solve N Queen problem */ bool solveNQueensUtil( int board[N][N], int col, int slashCode[N][N], int backslashCode[N][N], bool rowLookup[N], bool slashCodeLookup[], bool backslashCodeLookup[] ) { /* base case: If all queens are placed then return true */ if (col >= N) return true ; /* Consider this column and try placing this queen in all rows one by one */ for ( int i = 0; i < N; i++) { /* Check if queen can be placed on board[i][col] */ if ( isSafe(i, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) ) { /* Place this queen in board[i][col] */ board[i][col] = 1; rowLookup[i] = true ; slashCodeLookup[slashCode[i][col]] = true ; backslashCodeLookup[backslashCode[i][col]] = true ; /* recur to place rest of the queens */ if ( solveNQueensUtil(board, col + 1, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) ) return true ; /* If placing queen in board[i][col] doesn't lead to a solution, then backtrack */ /* Remove queen from board[i][col] */ board[i][col] = 0; rowLookup[i] = false ; slashCodeLookup[slashCode[i][col]] = false ; backslashCodeLookup[backslashCode[i][col]] = false ; } } /* If queen can not be place in any row in this column col then return false */ return false ; } /* This function solves the N Queen problem using Branch and Bound. It mainly uses solveNQueensUtil() to solve the problem. It returns false if queens cannot be placed, otherwise return true and prints placement of queens in the form of 1s. Please note that there may be more than one solutions, this function prints one of the feasible solutions.*/ bool solveNQueens() { int board[N][N]; memset (board, 0, sizeof board); // helper matrices int slashCode[N][N]; int backslashCode[N][N]; // arrays to tell us which rows are occupied bool rowLookup[N] = { false }; //keep two arrays to tell us // which diagonals are occupied bool slashCodeLookup[2*N - 1] = { false }; bool backslashCodeLookup[2*N - 1] = { false }; // initialize helper matrices for ( int r = 0; r < N; r++) for ( int c = 0; c < N; c++) { slashCode[r] = r + c, backslashCode[r] = r - c + 7; } if (solveNQueensUtil(board, 0, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) == false ) { cout << "Solution does not exist" ; return false ; } // solution found printSolution(board); return true ; } // Driver program to test above function int main() { solveNQueens(); return 0; } // this code is contributed by shivanisinghss2110 |
C
/* C++ program to solve N Queen Problem using Branch and Bound */ #include<stdio.h> #include<string.h> #include<stdbool.h> #define N 8 /* A utility function to print solution */ void printSolution( int board[N][N]) { for ( int i = 0; i < N; i++) { for ( int j = 0; j < N; j++) printf ( "%2d " , board[i][j]); printf ( "" ); } } /* A Optimized function to check if a queen can be placed on board[row][col] */ bool isSafe( int row, int col, int slashCode[N][N], int backslashCode[N][N], bool rowLookup[], bool slashCodeLookup[], bool backslashCodeLookup[] ) { if (slashCodeLookup[slashCode[row][col]] || backslashCodeLookup[backslashCode[row][col]] || rowLookup[row]) return false ; return true ; } /* A recursive utility function to solve N Queen problem */ bool solveNQueensUtil( int board[N][N], int col, int slashCode[N][N], int backslashCode[N][N], bool rowLookup[N], bool slashCodeLookup[], bool backslashCodeLookup[] ) { /* base case: If all queens are placed then return true */ if (col >= N) return true ; /* Consider this column and try placing this queen in all rows one by one */ for ( int i = 0; i < N; i++) { /* Check if queen can be placed on board[i][col] */ if ( isSafe(i, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) ) { /* Place this queen in board[i][col] */ board[i][col] = 1; rowLookup[i] = true ; slashCodeLookup[slashCode[i][col]] = true ; backslashCodeLookup[backslashCode[i][col]] = true ; /* recur to place rest of the queens */ if ( solveNQueensUtil(board, col + 1, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) ) return true ; /* If placing queen in board[i][col] doesn't lead to a solution, then backtrack */ /* Remove queen from board[i][col] */ board[i][col] = 0; rowLookup[i] = false ; slashCodeLookup[slashCode[i][col]] = false ; backslashCodeLookup[backslashCode[i][col]] = false ; } } /* If queen can not be place in any row in this column col then return false */ return false ; } /* This function solves the N Queen problem using Branch and Bound. It mainly uses solveNQueensUtil() to solve the problem. It returns false if queens cannot be placed, otherwise return true and prints placement of queens in the form of 1s. Please note that there may be more than one solutions, this function prints one of the feasible solutions.*/ bool solveNQueens() { int board[N][N]; memset (board, 0, sizeof board); // helper matrices int slashCode[N][N]; int backslashCode[N][N]; // arrays to tell us which rows are occupied bool rowLookup[N] = { false }; //keep two arrays to tell us // which diagonals are occupied bool slashCodeLookup[2*N - 1] = { false }; bool backslashCodeLookup[2*N - 1] = { false }; // initialize helper matrices for ( int r = 0; r < N; r++) for ( int c = 0; c < N; c++) { slashCode[r] = r + c, backslashCode[r] = r - c + 7; } if (solveNQueensUtil(board, 0, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) == false ) { printf ( "Solution does not exist" ); return false ; } // solution found printSolution(board); return true ; } // Driver program to test above function int main() { solveNQueens(); return 0; } |
JAVA
// Java program to solve N Queen Problem // using Branch and Bound import java.io.*; import java.util.Arrays; class GFG{ static int N = 8 ; // A utility function to print solution static void printSolution( int board[][]) { int N = board.length; for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < N; j++) System.out.printf( "%2d " , board[i][j]); System.out.printf( "" ); } } // A Optimized function to check if a queen // can be placed on board[row][col] static boolean isSafe( int row, int col, int slashCode[][], int backslashCode[][], boolean rowLookup[], boolean slashCodeLookup[], boolean backslashCodeLookup[]) { if (slashCodeLookup[slashCode[row][col]] || backslashCodeLookup[backslashCode[row][col]] || rowLookup[row]) return false ; return true ; } // A recursive utility function to // solve N Queen problem static boolean solveNQueensUtil( int board[][], int col, int slashCode[][], int backslashCode[][], boolean rowLookup[], boolean slashCodeLookup[], boolean backslashCodeLookup[]) { // Base case: If all queens are placed // then return true int N = board.length; if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for ( int i = 0 ; i < N; i++) { // Check if queen can be placed on board[i][col] if (isSafe(i, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup)) { // Place this queen in board[i][col] board[i][col] = 1 ; rowLookup[i] = true ; slashCodeLookup[slashCode[i][col]] = true ; backslashCodeLookup[backslashCode[i][col]] = true ; // recur to place rest of the queens if (solveNQueensUtil( board, col + 1 , slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup)) return true ; // If placing queen in board[i][col] doesn't // lead to a solution, then backtrack // Remove queen from board[i][col] board[i][col] = 0 ; rowLookup[i] = false ; slashCodeLookup[slashCode[i][col]] = false ; backslashCodeLookup[backslashCode[i][col]] = false ; } } // If queen can not be place in any row // in this column col then return false return false ; } /* * This function solves the N Queen problem using Branch * and Bound. It mainly uses solveNQueensUtil() to solve * the problem. It returns false if queens cannot be * placed, otherwise return true and prints placement of * queens in the form of 1s. Please note that there may * be more than one solutions, this function prints one * of the feasible solutions. */ static boolean solveNQueens() { int board[][] = new int [N][N]; // Helper matrices int slashCode[][] = new int [N][N]; int backslashCode[][] = new int [N][N]; // Arrays to tell us which rows are occupied boolean [] rowLookup = new boolean [N]; // Keep two arrays to tell us // which diagonals are occupied boolean slashCodeLookup[] = new boolean [ 2 * N - 1 ]; boolean backslashCodeLookup[] = new boolean [ 2 * N - 1 ]; // Initialize helper matrices for ( int r = 0 ; r < N; r++) for ( int c = 0 ; c < N; c++) { slashCode[r] = r + c; backslashCode[r] = r - c + 7 ; } if (solveNQueensUtil(board, 0 , slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) == false ) { System.out.printf( "Solution does not exist" ); return false ; } // Solution found printSolution(board); return true ; } // Driver code public static void main(String[] args) { solveNQueens(); } } // This code is contributed by sujitmeshram |
Python3
""" Python3 program to solve N Queen Problem using Branch or Bound """ N = 8 """ A utility function to print solution """ def printSolution(board): for i in range (N): for j in range (N): print (board[i][j], end = " " ) print () """ A Optimized function to check if a queen can be placed on board[row][col] """ def isSafe(row, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup): if (slashCodeLookup[slashCode[row][col]] or backslashCodeLookup[backslashCode[row][col]] or rowLookup[row]): return False return True """ A recursive utility function to solve N Queen problem """ def solveNQueensUtil(board, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup): """ base case: If all queens are placed then return True """ if (col > = N): return True for i in range (N): if (isSafe(i, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup)): """ Place this queen in board[i][col] """ board[i][col] = 1 rowLookup[i] = True slashCodeLookup[slashCode[i][col]] = True backslashCodeLookup[backslashCode[i][col]] = True """ recur to place rest of the queens """ if (solveNQueensUtil(board, col + 1 , slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup)): return True """ If placing queen in board[i][col] doesn't lead to a solution,then backtrack """ """ Remove queen from board[i][col] """ board[i][col] = 0 rowLookup[i] = False slashCodeLookup[slashCode[i][col]] = False backslashCodeLookup[backslashCode[i][col]] = False """ If queen can not be place in any row in this column col then return False """ return False """ This function solves the N Queen problem using Branch or Bound. It mainly uses solveNQueensUtil()to solve the problem. It returns False if queens cannot be placed,otherwise return True or prints placement of queens in the form of 1s. Please note that there may be more than one solutions,this function prints one of the feasible solutions.""" def solveNQueens(): board = [[ 0 for i in range (N)] for j in range (N)] # helper matrices slashCode = [[ 0 for i in range (N)] for j in range (N)] backslashCode = [[ 0 for i in range (N)] for j in range (N)] # arrays to tell us which rows are occupied rowLookup = [ False ] * N # keep two arrays to tell us # which diagonals are occupied x = 2 * N - 1 slashCodeLookup = [ False ] * x backslashCodeLookup = [ False ] * x # initialize helper matrices for rr in range (N): for cc in range (N): slashCode[rr][cc] = rr + cc backslashCode[rr][cc] = rr - cc + 7 if (solveNQueensUtil(board, 0 , slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) = = False ): print ( "Solution does not exist" ) return False # solution found printSolution(board) return True # Driver Cde solveNQueens() # This code is contributed by SHUBHAMSINGH10 |
Javascript
<script> // JavaScript program to solve N Queen Problem // using Branch and Bound let N = 8; // A utility function to print solution function printSolution(board) { let N = board.length; for (let i = 0; i < N; i++) { for (let j = 0; j < N; j++) document.write(board[i][j]+ " " ); document.write( "<br>" ); } } // A Optimized function to check if a queen // can be placed on board[row][col] function isSafe(row,col,slashCode,backslashCode,rowLookup,slashCodeLookup,backslashCodeLookup) { if (slashCodeLookup[slashCode[row][col]] || backslashCodeLookup[backslashCode[row][col]] || rowLookup[row]) return false ; return true ; } // A recursive utility function to // solve N Queen problem function solveNQueensUtil(board,col,slashCode, backslashCode,rowLookup,slashCodeLookup,backslashCodeLookup) { // Base case: If all queens are placed // then return true //let N = board.length; if (col >= N) return true ; // Consider this column and try placing // this queen in all rows one by one for (let i = 0; i < N; i++) { // Check if queen can be placed on board[i][col] if (isSafe(i, col, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup)) { // Place this queen in board[i][col] board[i][col] = 1; rowLookup[i] = true ; slashCodeLookup[slashCode[i][col]] = true ; backslashCodeLookup[backslashCode[i][col]] = true ; // recur to place rest of the queens if (solveNQueensUtil( board, col + 1, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup)) return true ; // If placing queen in board[i][col] doesn't // lead to a solution, then backtrack // Remove queen from board[i][col] board[i][col] = 0; rowLookup[i] = false ; slashCodeLookup[slashCode[i][col]] = false ; backslashCodeLookup[backslashCode[i][col]] = false ; } } // If queen can not be place in any row // in this column col then return false return false ; } /* * This function solves the N Queen problem using Branch * and Bound. It mainly uses solveNQueensUtil() to solve * the problem. It returns false if queens cannot be * placed, otherwise return true and prints placement of * queens in the form of 1s. Please note that there may * be more than one solutions, this function prints one * of the feasible solutions. */ function solveNQueens() { let board = new Array(N); // Helper matrices let slashCode = new Array(N); let backslashCode = new Array(N); for (let i=0;i<N;i++) { board[i]= new Array(N); slashCode[i]= new Array(N); backslashCode[i]= new Array(N); for (let j=0;j<N;j++) { board[i][j]=0; slashCode[i][j]=0; backslashCode[i][j]=0; } } // Arrays to tell us which rows are occupied let rowLookup = new Array(N); for (let i=0;i<N;i++) rowLookup[i]= false ; // Keep two arrays to tell us // which diagonals are occupied let slashCodeLookup = new Array(2 * N - 1); let backslashCodeLookup = new Array(2 * N - 1); for (let i=0;i<2*N-1;i++) { slashCodeLookup[i]= false ; backslashCodeLookup[i]= false ; } // Initialize helper matrices for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) { slashCode[r] = r + c; backslashCode[r] = r - c + 7; } if (solveNQueensUtil(board, 0, slashCode, backslashCode, rowLookup, slashCodeLookup, backslashCodeLookup) == false ) { document.write( "Solution does not exist" ); return false ; } // Solution found printSolution(board); return true ; } // Driver code solveNQueens(); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0
性能： 当在本地机器上运行N=32时，回溯解决方案需要659.68秒，而上面的分支和绑定解决方案只需要119.63秒。对于更大的N值，差异甚至会更大。
参考资料： https://en.wikipedia.org/wiki/Eight_queens_puzzle www.cs。康奈尔。edu/~wdtseng/icpc/notes/bt2。pdf 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.cppku.com/wp-content/themes/zibll/img/thumbnail.svg)
