Problems with the eight queens problem

[Wicket]

I heard from a friend of mine of the eight queens problem and I write a program to find all solutions to it. My problem is that it doesn't find any solutions and Wikipedia says there must be 92 solutions to it. After writing the code it does look like I have used the backtracking method (see http://en.wikipedia.org/wiki/Eight_q...rsive_solution)

I haven't only placed the code that deals with empty columns because I first wanted to see if the program worked.

Here is the header:

#include <iostream>

class chessboard
{
public:
	chessboard();
	void set_queen(const int &a, const int &b);
	void remove_queen(const int &a, const int &b);
	bool isqueen(const int &a, const int &b);
	bool iseight();
	bool ispossible(const int &a, const int &b);
	bool isrowempty(const int &i);
	void output();
private:
	/*
	The 8x8 matrix field represents a chessboard
	If there is a queen on the position, the value will be 1
	If the position is under attack by a queen, the value will be -1
	If a position is free then the value will be 0
	*/
	int field[8][8];
};

// Set all positions on the chessboard free
chessboard::chessboard()
{
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			field[i][j] = 0;
}

void chessboard::set_queen(const int &a, const int &b)
{
	field[a][b] = 1;			// Set the position of the new queen
	
	for (int i = 0; i < 8; i++)
	{
		if (i != a)				// Skip the place where the new queen is installed
			field[i][b] = -1;	// Occupy the horizontal row seen from the new queen
		if (i != b)				// Skip the place where the new queen is installed
			field [a][i] = -1;	// Occupy the vertical row seen from the new queen
	}
	// The next four for-statements occupy the diagonal position seen from the new queen
	// There are four for-statements: it goes diagonal forward and diagonal backward
	for (int i = a + 1, j = b + 1; i < 8 && j < 8; i++, j++)
		field[i][j] = -1;
	for (int i = a + 1, j = b - 1; i < 8 && j >= 0; i++, j--)
		field[i][j] = -1;
	for (int i = a - 1, j = b + 1; i >= 0 && j < 8; i--, j++)
		field[i][j] = -1;
	for (int i = a - 1, j = b - 1; i >= 0 && j >= 0; i--, j--)
		field[i][j] = -1;
}

void chessboard::remove_queen(const int &a, const int &b)
{
	field[a][b] = 0;
	
	// First set all positions that are under attack to 0
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			if (field[i][j] == -1)
				field[i][j] = 0;
	
	// Then set the positions that are under attack to 0
	// The positions that were under attack only by the removed queen
	// aren't under attack now any more
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			if (field[i][j] == 1)
				set_queen(i, j);
}

bool chessboard::isqueen(const int &a, const int &b)
{
	if (field[a][b] == 1)
		return true;
	else
		return false;
}

bool chessboard::iseight()
{
	int queens = 0;
	
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			if (field[i][j] == 1)
				queens++;
	if (queens == 8)
		return true;
	else
		return false;
}

bool chessboard::ispossible(const int &a, const int &b)
{
	if (field[a][b])
		return false;
	else
		return true;
}

bool chessboard::isrowempty(const int &i)
{
	for (int j = 0; j < 8; j++)
		if (field[i][j] == 1)
			return false;
	return true;
}

void chessboard::output()
{
	for (int i = 0; i < 8; i++)
		for (int j = 0; j < 8; j++)
			if (field[i][j] == 1)
				std::cout << char(97 + i) << j+1 << " ";
	std::cout << std::endl;
}

and here is the code of my program

/***************************************************************************
	The eight queens problem by Wicket under GPLv2

This program will calculate all the possible solutions to place eight queens
on a chessboard. 

The program will start to place a queen at the first possible place and go
on to place more queens on the next possible place until it reaches the end
of the chessboard. It will produce output to the screen if there are eight
queens placed on the chessboard. Then it removes the last queen and goes to
place queens from the position next to the last removed queen. This goes on
until the queen is removed from a8. After that it isn't possible to place
eight queens on a chessboard
***************************************************************************/

#include "chessboard.h"

int main()
{
	chessboard board;
	int a = 0, b = 0, counter = 0;
	
	// Run this while loop as long as all the posibilities haven't been checked
	while(!board.isrowempty(0) || a == 0)
	{
		for (int i = a; i < 8; i++)
			for (int j = b; j < 8; j++)
				if (board.ispossible(i, j))		// Check if it is possible to place a queen
					board.set_queen(i, j);
		board.output(); 						// TEMPORARY: testing if everything is working
		
		// Produce output to screen if there are eight queens on the chessboard
		if (board.iseight())
		{
			std::cout << ++counter << ": ";
			board.output();
		}
		
		// Remove the last queen
		bool loop_break = false;
		for (int i = 7; i >= 0; i--)
		{
			for (int j = 7; j >= 0; j--)
				if (board.isqueen(i, j))
				{
					board.remove_queen(i, j);
					// Set the start of the for-loops that will place queens on the field
					// at the position next to the removed queen
					if (j == 7)
					{
						a = i + 1;
						b = 0;
					}
					else
					{
						a = i;
						b = j + 1;
					}
					loop_break = true;
					break;
				}
			if (loop_break)
				break;
		}
		//board.output(); 							// TEMPORARY: testing if algorithms working
	}
	
	return 0;
}

Note: just after the first double for in main the program will output how the queens are placed. So your screen will put much output. This line is for testing if it does everything well.

[anon]

I find problems such as these are more easily solved with recursion.

In pseudocode:

solve(depth):
     if depth == 8: print solution
     else:
           for each square in depth-th row:
               if square is free:
                    mark position
                    solve(depth + 1)
                    unmark position

I also tackled this problem and decided that the board only tells whether a square is under fire or not and stored the positions of queens in a different array. This makes marking and unmarking board easier (the same function just adds +1 or -1 to all square affected by this queen - not even caring whether the square occupied by the queen gets marked more than once).