# Problems with the eight queens problem

• 06-12-2008
Wicket
Problems with the eight queens problem
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.

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.
• 06-12-2008
anon
I find problems such as these are more easily solved with recursion.

In pseudocode:
Code:

```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).