Eight Queens Problem

[eternalblizzard]

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

[eternalblizzard]

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?

[Clinton Portis]

I would help you with this, but I don't know how to play the game!

[mzimmers]

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.

[eternalblizzard]

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.