Hi, I'm currently working on an Eight Queens problem solving with recursion and backtracking. I have an output for my code, but it is not the desired output and I am having trouble figuring out what part of the code is wrong. Any advice would be appreciated.

My header file

#ifndef BOARD_H
#define BOARD_H
using namespace std;

static const int BOARD_SIZE = 8;

class Board
{
public:
	Board();
	void display() const;
	void doEightQueens();

private:
	bool isQueen (int inRow, int inCol) const;
	bool isUnderAttack (int cRow, int cCol) const;
	bool placeQueens (int cCol);
	void removeQueen (int cCol);
	void setQueen (int cRow, int cCol);
	int rows [BOARD_SIZE];
};
#endif

My Board.cpp

#include <iostream>
#include "Board.h"

Board::Board() 
{
	for (int i=0; i<BOARD_SIZE; ++i)
	{
		rows[i] = 0;
	}
}

void Board::display() const 
{
	for (int i=0; i<BOARD_SIZE; ++i)
	{
		for (int j=0; j<BOARD_SIZE; ++j)
		{
			if (isQueen(i,j))
			{
				cout << "Q ";
			}
			else 
			{
				cout << "- ";//print out a dash everywhere else
			}
		}
		cout << endl;
	}
}

void Board::doEightQueens() 
{
	placeQueens(0);
}

bool Board::isQueen (int inRow, int inCol) const
{
	return rows[inCol] == inRow;
}

bool Board::isUnderAttack (int cRow, int cCol) const
{
	for (int i=0; i<cCol; ++i)
	{
		if (isQueen(cRow,i) || isQueen(cRow-cCol+i,i) || isQueen(cRow+cCol-i,i))//first condition checks for row, second and third check for left diagonals
		{
			return true;
		}
		else
		{
			return false;
		}
	}
}

bool Board::placeQueens (int cCol)
{
	if (cCol >= BOARD_SIZE)
	{  
		return true; // this is the base case
	}
	bool isQueenPlaced = false;
	int cRow = 0;
	while (!isQueenPlaced && cRow < BOARD_SIZE)
	{  
		if (isUnderAttack(cRow, cCol))
		{
			++cRow;
		}
		else
		{  
			setQueen(cRow, cCol);
			isQueenPlaced = placeQueens(cCol+1);
			if (!isQueenPlaced)
			{  
				removeQueen (cCol);
			} 
		}
		cout << "Current col is: " << cCol;
		cout << " Current row is: " << cRow << endl;
	}
	return isQueenPlaced;
}

void Board::removeQueen (int cCol)
{
	rows[cCol] = 0;
}

void Board::setQueen (int cRow, int cCol)
{
	rows[cCol] = cRow;
}

My Main.cpp

#include <iostream>
#include "Board.h"

int main()
{
	Board board;
	board.doEightQueens();
	board.display();
	system ("pause");
	return 0;
}

The Output I get
Q - - - - - - -
- - Q Q Q Q Q Q
- Q - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -
- - - - - - - -

Comments
sounds like a party at sigfried and roy's house.

Going through my code, I believe the error comes in when the function isUnderAttack is called. For some reason or another the function is not doing what it's suppose to. There's a Q placed in the same row from column 2-7. Any idea why this might have happened?

I'm not at all sure I fully understand your program, but...I wonder if line 43:

for (int i=0; i<cCol; ++i)

should be:

for (int i=0; i< BOARD_SIZE; ++i)

It's not clear to me that you're exhausting all possibilities with your current loop limit.

If my thought process and codes are correct, it doesn't need to go through the whole "BOARD_SIZE." It should fill in the queens by columns and fills in the board from left to right.

This article has been dead for over six months. Start a new discussion instead.