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:
Code:
#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
Code:
/***************************************************************************
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.