how to solve 8 queens using backtracking

Question

0.00/5 (No votes)

See more:

#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?

Posted 25-Mar-15 2:38am

Reuben Cabrera

Add a Solution

1 solution

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Stefan_Lang · Answer 1 · 2015-03-26T02:59:00

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:

C++

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);
}

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.