Member Avatar for aclark17
aclark17 0 Newbie Poster

Ive been having some trouble getting my Nqueens program to run for n>=9.

I use a function bool PlaceQueens(c) to recursivley find all solutions using a backtracking algorithim , it seems to return neither true or false.

For n=9, the function PlaceQueens exits without returning a value during call 4296.

Here is my code:

static int count=0;
bool ChessBoard::PlaceQueens(int c){

	int r=0;
	
	 if(processcol(r,c)){
		if(c==n-1){
			c--;
			solutions++;}
		c++;}
	else
	c--;
	 if(c<0){
		
		if(solutions==0)
			return false;
		else{
			cout<<"solutions: "<<solutions<<endl;
			return true;}
	}
	 else{

	count++;
	
	if(count>4293){
		cout<<"call: "<<count<<endl;
	
		cout<<*this<<endl;}
	return PlaceQueens(c);}
}

Here is whats happening on the board between calls 4293 and 4296:

//program output

Queen Placement

Enter size of board (positive integer): 9

Placing queens on a 9 x 9 chess board...
call: 4294

-----------------
| | | | | | | | | Q |
-----------------
| | | | Q | | | | | |
-----------------
| Q | | | | | | | | |
-----------------
| | | | | Q | | | | |
-----------------
| | | | | | | | Q | |
-----------------
| | Q | | | | | | | |
-----------------
| | | | | | | Q | | |
-----------------
| | | Q | | | | | | |
-----------------
| | | | | | Q | | | |
-----------------

call: 4295

-----------------
| | | | | | | | | |
-----------------
| | | | Q | | | | | |
-----------------
| Q | | | | | | | | |
-----------------
| | | | | Q | | | | |
-----------------
| | | | | | | | Q | |
-----------------
| | Q | | | | | | | |
-----------------
| | | | | | | Q | | |
-----------------
| | | Q | | | | | | |
-----------------
| | | | | | Q | | | |
-----------------

call: Press any key to continue . . .

//end output

It looks like its exiting just before outputing the value of count. At this point it has found 76 solutions. Total number of solutions for n=9 is 92. It processes n<9 without a problem.I have included the header main and function definitions a attachments to this post.

#ifndef BOARD_H
#define BOARD_H
#include <iostream>
#include <fstream>
using namespace std;

class ChessBoard  {
public:
	// The parameter in this constructor gives the size of the board
	ChessBoard(int size);
	~ChessBoard();

	// Removes all queens from the board
	void ClearBoard();

	//Pre: There is one queen in column 0 through column c-1, and none
	//     of these queens can attack each other.
	//     It attempts to place queens in the remaining columns, and returns
	//     true if all the other queens were placed and false otherwise.
	bool PlaceQueens(int c);

	//  Prints the current state of the board
	friend ostream& operator<<(ostream&, const ChessBoard&);

private:
	//Pre: There is a queen at row r and column c
	//Post: There is no queen in row r and column c
	void RemoveQueen(int r, int c);

	//Pre: The square at row r and column c is safe
	//Post: A queen is placed at row r and column c
	void SetQueen(int r, int c);

	//Pre: 0 <= r < n  and 0 <= c < n
	//     Returns true if the square at row r and column c is safe (i.e., 
	//     can't be attacked by any queen currently placed on the board), 
	//     and false otherwise.
	bool Safe(int r, int c) const;

	// Contains the number of squares on one side of the chess board.
    int n;
	
	int solutions;// number of solutions for the chessboard
	bool checksolution();//checks new solution
	bool processcol(int row, int col);//checks if a queen can be placed in column c starting at row
	
	
	

	

	// queen[c] is the row where the queen in column c is currently placed.
	int* queen;

	// row[r] is true if there is currently a queen in row r.
	bool* row;

	// negdiag[i] is true if there is a queen in the ith negative diagonal.
	bool* negdiag;

	// posdiag[i] is true if there is a queen in the ith positive diagonal.
	bool* posdiag;
	
	
};
#endif
#include <iostream>
#include <fstream>
#include "board.h"
using namespace std;

int main()  {
	char op='y';
	while(op=='y'){
	cout << "Queen Placement\n\n";
	cout << "Enter size of board (positive integer): ";
	int boardsize;
	cin >> boardsize;
	cout << "\nPlacing queens on a " << boardsize << " x " << boardsize
		 << " chess board...\n";
    ChessBoard  myboard(boardsize);
	
	if(!myboard.PlaceQueens(0))
	cout<<"no solutions"<<endl;
		cout<<"continue? ";
		cin>>op;
	}
		return 0;
}
#include <iostream>
#include <fstream>
#include <math.h>

#include "board.h"
#include <cstdlib>  
using namespace std;

ChessBoard::~ChessBoard()
{
	ClearBoard();
}
ChessBoard::ChessBoard(int size)
{
	
	n=size;
	queen=new int[n];
	row= new bool[n];
	negdiag=new bool[2*n-1];
	posdiag=new bool[2*n-1];
	solutions=0;
	int i;
	
	

	for(i=0;i<n;i++)
			queen[i]=-1;

	for(int i=0;i<n;i++)
			row[i]=false;

	for(i=0;i<2*n-1;i++)
			posdiag[i]=false;

	for(i=0;i<2*n-1;i++)
			negdiag[i]=false;

	


	
	
}

void ChessBoard::SetQueen(int r, int c)
{
	queen[c]=r;
	posdiag[r+c]=true;
	negdiag[abs(2*(r-c)+((n-1)-(r-c)))]=true;
	row[r]=true;
}
void ChessBoard::RemoveQueen(int r, int c)
{
	queen[c]=-1;
	posdiag[r+c]=false;
	negdiag[abs(2*(r-c)+((n-1)-(r-c)))]=false;
	row[r]=false;
}
bool ChessBoard::Safe(int r, int c)const
{
	if(queen[c]==-1&&posdiag[r+c]==false&&negdiag[abs(2*(r-c)+((n-1)-(r-c)))]==false&&row[r]==false)
		return true;
	else 
		return false;
}
ostream& operator<<(ostream& out, const ChessBoard& b)
{
	cout<<endl;
	cout<<"-----------------"<<endl;
	int c;
	int r;
	for(r=0;r<b.n;r++){
		cout<<'|';
		for(c=0;c<b.n;c++){
			if(b.queen[c]==r)
				cout<<" Q ";
			else
				cout<<"   ";
			cout<<'|';
		}
		cout<<endl;
		cout<<"-----------------"<<endl;
		}
	return out;
}
	
void ChessBoard::ClearBoard()
{
	int i;
	for(i=0;i<n;i++)
			queen[i]=-1;

	for(int i=0;i<n;i++)
			row[i]=false;

	for(i=0;i<2*n;i++)
			posdiag[i]=false;

	for(i=0;i<2*n;i++)
			negdiag[i]=false;
}
bool ChessBoard::processcol(int row, int col)
{

		if(queen[col]!=-1)
		{
			row=queen[col]+1;
			RemoveQueen(queen[col],col);}
			while(!Safe(row,col)&&row<n)
			row++;
			if(row>=n)
				return false;
			else {
				SetQueen(row,col);
					return true;}
}


static int count=0;
bool ChessBoard::PlaceQueens(int c){

	int r=0;
	
	 if(processcol(r,c)){
		if(c==n-1){
			c--;
			solutions++;}
		c++;}
	else
	c--;
	 if(c<0){
		
		if(solutions==0)
			return false;
		else{
			cout<<"solutions: "<<solutions<<endl;
			return true;}
	}
	 else{

	count++;
	
	if(count>4293){
		cout<<"call: "<<count<<endl;
		cout<<solutions<<endl;
	
		cout<<*this<<endl;}
	return PlaceQueens(c);}
}
  • 1 Contributor
  • 0 Replies
  • 64 Views
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.