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:

and here is the code of my programCode:#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; }

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.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; }