如何使用回溯解决8个皇后 [英] how to solve 8 queens using backtracking

问题描述

#include<iostream>
#include<string>
#include<fstream>
using namespace std;

// check column if Q is present
	bool checkCol(char aBoard[8][8],int aColumn){
	
	for(int j=0; j!=8; j++){
		if(aBoard[j][aColumn]=='Q')
		return false;
		}
	return true;
}

// check diagonals if Q is present
	bool checkDiagonals(char aBoard[8][8], int aRow, int aColumn){
	// down and right movement
			int i=aRow;
			int j=aColumn;
	while(i !=8 && j!=8){
		if(aBoard[i][j] == 'Q')
		return false;
		i++;
		j++;
	}
	
	// down and left movement
	  		i=aRow;
	 		j=aColumn;
	while(i !=8 && j!=-1){
		if(aBoard[i][j] == 'Q')
		return false;
		i++;
		j--;
	}
	
		// up and left movement
				i=aRow;
	 			j=aColumn;
	while(i !=-1 && j!=-1){
		if(aBoard[i][j] == 'Q')
		return false;
		i--;
		j--;
	}
		// up and right movement
			i=aRow;
		    j=aColumn;
	while(i !=-1 && j!=8){
		if(aBoard[i][j] == 'Q')
		return false;
		i--;
		j++;
	}
	
	return true;
	
} 

// checks if both  col and diaganols 
bool canputQueenin(char aBoard[8][8], int aRow, int aColumn){
		if(!(checkCol(aBoard,aColumn) && checkDiagonals(aBoard, aRow,aColumn))){
			return false;
		}
		return true;
	
}	
	
// Print the Board
	void printBoard(char aBoard[8][8]){
	
		int i, j;
	
			for(i=0;i<8;i++){
				for( j=0;j<8;j++){
			
					aBoard[i][j]='-';
		
					cout<<aBoard[i][j]<< "  ";
			 }                      
			 cout <<endl;
		 }
	}
		
	
	
	

	
int main(){
	int i, j;
 	char Chessboard[8][8];
 	printBoard(Chessboard);
       

}

所以这是到目前为止的代码，我遇到麻烦到哪里放置递归回溯函数。有人可以帮助我放置递归吗？

so this is the code so far, im having troubles where to place the recursive backtracking functions. can someone help me where i should place the recursion?

推荐答案

那个地方还不存在！基本上，递归地求解8个皇后的想法包括一个函数，它将一个女王放在给定列（或行）中的位置，然后检查它是否是有效位置。如果它有效，则移动到下一列8或行，然后执行相同的操作。如果没有，请检查下一个位置。如果在当前列中找不到皇后的有效位置，则返回false以指示到目前为止定位的皇后不是有效模式的一部分。否则返回true。



你还没有这样的功能。但是这里有一些伪代码：

That place doesn't exist yet! Basically, the idea of solving the 8 queens recursively consists of a function that puts a queen on position in a given column (or row), then check whether it is a valid position. If it is valid, you move to the next column 8or row, and there you do the same. If not, check the next position. If you can't find a valid position for a queen in the current column, you return false to indicate that the queens positioned so far are not part of a valid pattern. Otherwise return true.

You don't have any such function yet. But here's some pseudocode:

void Position::try_place_queen_at(int column)
{
   int row = 0;
   do {
      if (can_place_queen_at(row, column))
      {
         // put queen at this location
         Position new_board = add_queen(row, column);
         // try putting a queen at the next column
         if (column == Max_column) { // <-- recursion ends here
            // this was the last column, we're done!
            new_board.display(); // show the results
         }
         else {
            // find a spot in the next column
            new_board.try_place_queen_at(column+1); // <-- recursion is here
         }
      }
      else
      {
         ++row;
      }
   } while (row <= Max_row && !valid);
}

我在N皇后位置而不是一般国际象棋位置使用在这里定位一词，i。即整个电路板及其上的所有女王，具有将女王置于问题的特定规则下所需的功能。正如你所看到的，我使用了一个名为Position的类，它支持皇后的放置，检查有效性（对于皇后问题），并显示当前位置，以及通过添加皇后来创建旧位置。



我也通过使用常量Max_column和Max_row而不是8来概括问题。虽然你可能不想改变这个数字，但它有助于代码的可读性，恕我直言。



PS：伪代码将打印所有有效位置。如果你只想要1，那么try ...函数应该返回一个标志来指示你是否已经找到了解决方案。 （或表示到目前为止找到的解决方案数量的数字）。这将允许您在实际显示之前进行检查。

I'm using the term Position here in the sense of an N queens position rather than a general chess position, i. e. the entire board and all the queens on it, with the functionality needed to place queens under the specific rules of the problem. As you can see I've used a class called Position that supports placement of queens, checking validity (for the queens problem), and displaying the current position, as well as creating new positions from the old by adding a queen.

I've also generalized the problem by using the constants Max_column and Max_row instead of just 8. While you may not be interested in varying that number, it helps readability of the code, IMHO.

P.S.: the pseudo code will print all valid positions. If you want only 1, the "try..." function should return a flag to indicate whether or not you've already found a solution. (or a number to indicate the number of solutions found so far). that will allow you a check before actually doing the the display.

这篇关于如何使用回溯解决8个皇后的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！