使用回溯递归的8个皇后问题
|
我一直在研究8个皇后区的问题，但被困住了。我不需要代码。我很乐意提供指导和指导，以了解自己如何使用回溯递归来解决此问题。
该程序应通过绘制ASCII中的皇后区的位置来枚举N皇后问题的所有解决方案，就像这里的两个解决方案一样。
到目前为止，我的伪代码是：
void queen(int n){
for( int i = 0; i < n; i++){
place queen[ i ] on row i;
for(int j = 0 ; j < n ; j++){
if( queen[ i ] is not in the same column as queen[0] through queen[ i - 1 ] &&
queen[ i ] is not on the same major diagonal with queen[0] through queen[ i -1 ] &&
queen[ i ] is not on the same minor diagonal with queen[0] through queen[ i -1 ] ) {
print \'Q \';
}
else{
print \'* \';
}
System.out.println();
}
System.out.println();
}
}
solver(int n, Board b){
for(int i = 0; i < b.length; i++){
place queen in column i;
for(int j = 0; j < b.length; j++){
change b;
solver(n+1,changed b);
}
}
}
solver8(board /* with queens presented in first 7 columns */){
// place a queen in the 8th column;
for(each possible placement of the queen in column 8
or in other words int i = 0; i < board.length; i++ ){
place the queen and print the board
}
}
solver7(board /* with queens presented in first 6 columns */){
// place a queen in the 7th column;
for(each possible placement of the queen in column 7
or in other words int i = 0; i < board.length; i++ ){
solver8(board with queens placed in first 7 columns);
}
}
solver6(board /* with queens presented in first 5 columns */ ){
// place a queen in the 6th column;
for(each possible placement of the queen in column 6
or in other words int i = 0; i < board.length; i++ ){
solver7(board with queens presented in first 6 columns);
}
}
solver1(1, empty board){
for(int i = 0; i < board.length; i++){
place queen in row[i] of column 1;
solver2(board with queen in row[i] of column 1);
}
}
private int numberOfQueens = 8;
solver(int n, Board b){
for(int r = 0; r < b.length; r++){
place queen in row[r] of column[n];
if(n == numberOfQueens){
print the board;
return;
}
else{
solver(n+1, board with queen in row[r] of column[n]);
}
}
}
}
没有找到相关结果
已邀请:
5 个回复
犀寺扦
讹巳漓把备
// On input, s represents a valid State up to depth d-1 sub do_it(int d, State s) if (d == MAX_DEPTH+1) // State s represents an answer! Print it and return. else (augment s to make it valid for depth d) for each augmented_s do_it(d+1, augmented_s) end for end if end sub // top level do_it(0, empty_state)的，可以有多种方法将其扩充到有效深度为的状态。这个想法是让他们每个人都称呼自己。 对于此问题，“状态”是面板。深度“ d-1”可能表示已填充前d-1列。合法的增强州将是那些在d列中有女王/王后以致无法将其捕获的国家。 [更新] 这是另一种查看方式。向后处理问题。 假设我要求您编写一个简单的函数。此功能将前7列中已经存在皇后的木板作为输入。它要做的就是拿起那块木板，找到所有方法在第8列中添加一个皇后，然后打印出这些木板。您认为您可以编写此功能吗？好;写下来。 现在假设我要您编写一个几乎简单的函数called10 function。此功能将前6列中已存在皇后的木板作为输入。它要做的就是拿起那块木板，找到所有方法在第7列添加一个皇后，然后将这些木板中的每一个作为参数传递给。您可以编写此功能吗？ 现在假设我要求您编写另一个函数。作为输入，它需要一个在前5列中都有皇后的木板。它所要做的就是拿起那块木板，找到所有方法在第6列添加一个皇后，然后将这些木板中的每一个传递给。 依此类推，直到我们达到。这个拿一个空的棋盘，找到所有方法在第一栏中放置一个女王，然后将每个棋盘传递到each15 to。 您刚刚编写了8个函数，它们一起解决了8个皇后区问题。如果这没有意义，请将其写为8个函数并盯着它直到您这样做。 现在，如果您查看所有这些功能，就会发现它们非常相似。因此，您无需编写单个函数，而无需编写solver8，solver7，solver6，...，solver1：...使得solver（1，b）与solver1（b）相同，solver（2，b）与solver2（b），...相同，而solver（8，b）与求解器8（b）。例如，您将只使用solver（2，...）来调用solver（3，...），而不是使用solver2（...）来调用solver3（...）。一个函数而不是8，但执行相同的操作。 如果您从开始，您会很快发现最终代码更干净，只是装满一块木板，然后打印出来，然后再调用它。晤默报
上看到这个漂亮的动画 另外，请注意：。 查看此处说明的。疾很毋悲
咳累录酬
2.2十字女王发现对角像要么代码：package queenproblem; public class QueenProblem { int numQueens[];// hold columns postion int numQueen; QueenProblem(int noOfQueens) { this.numQueen = noOfQueens; numQueens = new int[noOfQueens]; } public static void main(String[] args) { new QueenProblem(8).solveProblem(); } public void solveProblem() { arrange(0); } // recursive Function void arrange(int rowIndex) { // 1.to check valid Postion of not. // 2. to check all Queens postion is found or not. for (int i = 0; i < numQueen; i++) { if (isValid(rowIndex, i)) { numQueens[rowIndex] = i;// save col index if (rowIndex == numQueen - 1) { printsBoard(); } else { arrange(rowIndex + 1); } } } } private void printsBoard() { for (int i = 0; i < numQueen; i++) { for (int j = 0; j < numQueen; j++) { if (numQueens[i] == j) { System.out.print(\" * \"); } else System.out.print(\" - \"); } System.out.println(); } System.out.println(); } boolean isValid(int rowIndex, int colIndex) { for (int i = 0; i < rowIndex; i++) { // on the save columns if (numQueens[i] == colIndex) return false; if ((i - rowIndex) == (numQueens[i] - colIndex)) return false; if ((i - rowIndex) == (colIndex - numQueens[i])) return false; } return true; } }