Hi all.
I'm trying to write a 8 Queen Problem solving program in C++ as an assignement for an exam.
I created a Matrix Board class to represent the chessboard with some functions such as put_Queen or check_Board for invalid positioning. I haven't yet begin to write the solving algorithm, but I usually (since I'm at the very beginning of C++ learning) write small portions of code and then test them before going on. I created the necessary to check if the queens positions on the board are valid or not and after a few test it seemed to work flawlessly.
I decided then to test it with a solution I knew to be exact, I put the 8 queens and got Segmentation Fault while trying to execute the program.
If I comment the last put_Queen call in main it works well (even if obviously tells me that the configuration is invalid). Moreover, if I change "board1.put_Queen(7,5);" with, for example "board1.put_Queen(0,0);" again there's no problem.
Just another thing, wich I don't know if is related or not: when compiling, it tells me
Regine.cpp: In member function ‘bool M_Board::Q_check(int**, int, int)’:
Regine.cpp:117: warning: left-hand operand of comma has no effect
Regine.cpp:123: warning: left-hand operand of comma has no effect
Regine.cpp:129: warning: left-hand operand of comma has no effect
Regine.cpp:135: warning: left-hand operand of comma has no effect
I don't know what else to say, if I forgot something important just tell me and I'll try to be more precise. Thanks to all who will try to help and sorry for my bad programming (I'm learning slowly) as well as for my bad english.
Here's the code:
#include <iostream>
#include <time.h> // for random purposes //
using namespace std;
const int N = 8;
class M_Board {
public:
M_Board();
~M_Board();
bool check_MBoard(); // checks for invalid queen positioning in the whole board
bool Q_check(int **board, int i, int j); // checks invalid queen position for a single queen
void print_MBoard(); // prints the board configuration
void put_Queen(int i, int j); // places a queen on the board, in position (i,j);
int QCount; // number of queen already on the board
int **m_board; // NxN matrix which represents the board
};
M_Board::M_Board() {
int i = 0, j = 0;
m_board = new int*[N];
for(i=0;i<N;i++) {
m_board[i] = new int[N];
}
i = 0;
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
m_board[i][j] = 0;
}
}
QCount = 0;
}
M_Board::~M_Board() {
int i = 0;
for(i=0;i<N;i++) {
delete [] m_board[i];
}
delete [] m_board;
}
bool M_Board::check_MBoard() {
int i = 0, j = 0;
M_Board copy;
if(QCount!=8) {
return false;
}
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
copy.m_board[i][j] = m_board[i][j];
}
}
copy.QCount = QCount;
for(i=0;i<N;i++) {
for(j=0;j<N;j++) {
if(copy.m_board[i][j]==1) {
if(copy.Q_check(copy.m_board, i, j)==false) {
return false;
}
}
}
}
return true;
}
bool M_Board::Q_check(int **board, int i, int j) {
int a = 0, b = 0;
// checks horizontal right movement
for(a=j+1;a<N;a++) {
if(board[i][a]==1) {
return false;
}
}
// checks horizontal left movement
for(a=j-1;a>=0;a--) {
if(board[i][a]==1) {
return false;
}
}
// checks vertical up movement
for(a=i-1;a>=0;a--) {
if(board[a][j]==1) {
return false;
}
}
// checks vertical down movement
for(a=i+1;a<N;a++) {
if(board[a][j]==1) {
return false;
}
}
// checks diagonal down-right movement
for(a=i+1,b=j+1;a<N,b<N;a++,b++) {
if(board[a][b]==1) {
return false;
}
}
// checks diagonal up-right movement
for(a=i-1,b=j+1;a>=0,b<N;a--,b++) {
if(board[a][b]==1) {
return false;
}
}
// checks diagonal up-left movement
for(a=i-1,b=j-1;a>=0,b>=0;a--,b--) {
if(board[a][b]==1) {
return false;
}
}
// checks diagonal down-left movement
for(a=i+1,b=j-1;a<N,b>=0;a++,b--) {
if(board[a][b]==1) {
return false;
}
}
return true;
}
void M_Board::print_MBoard() {
int i = 0, j = 0;
cout << endl << endl;
for(i=0;i<N;i++) {
cout << " _";
}
cout << endl;
i = 0;
for(i=0;i<N;i++) {
cout << "|";
for(j=0;j<N;j++) {
if(m_board[i][j]==0) {
cout << "_";
cout << "|";
}
if(m_board[i][j]==1) {
cout << "Q";
cout << "|";
}
}
cout << endl;
}
}
void M_Board::put_Queen(int i, int j) {
m_board[i][j] = 1;
QCount++;
return;
}
int main(void) {
M_Board board1;
board1.put_Queen(0,3);
board1.put_Queen(1,6);
board1.put_Queen(2,2);
board1.put_Queen(3,7);
board1.put_Queen(4,1);
board1.put_Queen(5,4);
board1.put_Queen(6,0);
board1.put_Queen(7,5); // the "guilty" line!
if(board1.check_MBoard()==false) {
cout << "La posizione non e' valida!\n";
}
else {
cout << "La posizione e' valida\n";
}
board1.print_MBoard();
return 0;
}
Edit: it's not the line
board1.put_Queen(7,5);
in itself that causes the problem... if I comment the previous line, for example, it works just as it should.
It has to be something else involving all the eight pot_Queen calls... maybe there's a problem in the moment it realizes that the configuration is valid, even if I can't find it. I'm neither too sure about what "Segmentation Fault" does mean...