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

Hi mrboolf,

. . .

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

Consider your constructor and destructor:

In C++ memory is allocated by applying "new". Its partner is "free" ! You should never apply "delete", which is plain C, on memory once allocated with "new".

Maybe that will help you.

Btw, you should mark the statements by the line number where the warning appears. So simple add //123: warning: left-hand operand of comma has no effect
at the code line in question.

brs,
tesu

a gets a negative value (-1) in the following loop.

// checks diagonal up-right movement
	for(a=i-1,b=j+1;a>=0, b<N;a--,b++) {
		if(board[a][b]==1) {

The comma operator a>=0, b<N is not doing what you probably expect.

sorry, completely nonsense what I wrote ! so forget it.
true, new <--> delete and malloc <--> free
sorry for telling that nonsens

krs,
tesu

Thank you all for fast reply!

a gets a negative value (-1) in the following loop.

// checks diagonal up-right movement
	for(a=i-1,b=j+1;a>=0, b<N;a--,b++) {
		if(board[a][b]==1) {

// checks diagonal up-right movement for(a=i-1,b=j+1;a>=0, b<N;a--,b++) { if(board[a][b]==1) {

The comma operator a>=0, b<N is not doing what you probably expect.

You are absolutely right, of course. Stupid error... but just rewriting the loop test expressions in this way

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

it works fine. Thank you mitrmkar!

For tesuji: don't worry and thanks for the advice :)

thx :zzz:

Here is a great solution of the n queens problem. It originates from Niklaus Wirth, inventor of Pascal, Modula, and Oberon, over 30 years ago. His solution is unique, and I need some hours to understand it completely. Because this code is famous one cannot hand it in as his own solution of an assignment, probably every other teacher knows it.

int nbs=0;
    void Queens(int nn, int row[], int k=0)
    { if(k==nn)
      { cout<<endl<<"Solution "<<(++nbs)<<":"<<endl;
        for(int i=0; i<nn; i++)
        { for(int j=0; j<nn;j++)
          { if(row[i]==j) cout<<("Q "); else cout<<(". ");
          } cout<<endl;} cout<<endl;}
      else
      { for(int i=0; i<nn; i++)
        { row[k]=i;
          for(int j=0; j<k;j++)
          { if((row[j]==row[k])||((row[j]-row[k])==(k-j))
            ||((row[k]-row[j])==(k-j))) goto fails;
          } Queens(nn, row, k+1); fails:;}}
    }
    int qu_main(int argc, char *argv[])
    { const int nn = 8;
      int *row = new int[nn];
      Queens(nn, row);
	  return 0;
    }

Maybe you can learn something from Wirth's code (except from the goto which is considered to be harmful). Interesting is his "chess board" what consists of one row only.

krs,
tesu

Very interesting indeed...
I need more research to understand it sufficiently, thank you for giving me the input to do so :)

I was thinking of permutations... in order to find ALL the possible solutions I think it's possible, as long as I consider only the EIGHT queen problem, to generate all the permutations of the { 0, 1, 2 ,3 ,4 ,5 ,6 ,7 } array, interpreting the components as "rows" and their index as "columns" of the chessboard. After each permutation is created a simple check on the diagonals tells if that particular combination is a solution or not (since horizontal and vertical interferences are excluded by the absence of repetitions).

In the 8x8 chessboard case it works well and it's satisfying to get all the solutions at once, but what if I would like to consider much greater boards? Already in a 100x100 one is WAY much too slow :(

I guess the N! is not a guy to make laughs about... pity, 'cause I liked that.

I'm going to study Wirth's solution now :)

Thanks to all.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.