8 Queens Problem - Segmentation Fault

Please support our C++ advertiser: Programming Forums - DaniWeb Sister Site
Thread Solved

•
•
Join Date: Jun 2008
Posts: 182
Reputation: mrboolf will become famous soon enough mrboolf will become famous soon enough 
Solved Threads: 18
mrboolf mrboolf is offline Offline
Junior Poster

8 Queens Problem - Segmentation Fault

 
0
  #1
Jun 18th, 2008
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

C++ Syntax (Toggle Plain Text) 
  1. Regine.cpp: In member function ‘bool M_Board::Q_check(int**, int, int)’:
  2. Regine.cpp:117: warning: left-hand operand of comma has no effect
  3. Regine.cpp:123: warning: left-hand operand of comma has no effect
  4. Regine.cpp:129: warning: left-hand operand of comma has no effect
  5. 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:

C++ Syntax (Toggle Plain Text) 
  1. #include <iostream>
  2. #include <time.h> // for random purposes //
  3. using namespace std;
  4.  
  5. const int N = 8;
  6.  
  7. class M_Board {
  8. 	public:
  9. 	M_Board();
  10. 	~M_Board();
  11. 	bool check_MBoard(); // checks for invalid queen positioning in the whole board
  12. 	bool Q_check(int **board, int i, int j); // checks invalid queen position for a single queen
  13. 	void print_MBoard(); // prints the board configuration
  14. 	void put_Queen(int i, int j); // places a queen on the board, in position (i,j);
  15. 	int QCount; // number of queen already on the board
  16. 	int **m_board; // NxN matrix which represents the board
  17. };
  18.  
  19. M_Board::M_Board() {
  20. 	int i = 0, j = 0;
  21. 	m_board = new int*[N];
  22. 	for(i=0;i<N;i++) {
  23. 		m_board[i] = new int[N];
  24. 	}
  25. 	i = 0;
  26. 	for(i=0;i<N;i++) {
  27. 		for(j=0;j<N;j++) {
  28. 			m_board[i][j] = 0;
  29. 		}
  30. 	}
  31. 	QCount = 0;
  32. }
  33.  
  34. M_Board::~M_Board() {
  35. 	int i = 0;
  36. 	for(i=0;i<N;i++) {
  37. 		delete [] m_board[i];
  38. 	}
  39. 	delete [] m_board;
  40. }
  41.  
  42. bool M_Board::check_MBoard() {
  43. 	int i = 0, j = 0;
  44. 	M_Board copy;
  45. 	if(QCount!=8) {
  46. 		return false;
  47. 	}
  48. 	for(i=0;i<N;i++) {
  49. 		for(j=0;j<N;j++) {
  50. 			copy.m_board[i][j] = m_board[i][j];
  51. 		}
  52. 	}
  53. 	copy.QCount = QCount;
  54. 	for(i=0;i<N;i++) {
  55. 		for(j=0;j<N;j++) {
  56. 			if(copy.m_board[i][j]==1) {
  57. 				if(copy.Q_check(copy.m_board, i, j)==false) {
  58. 					return false;
  59. 				}
  60. 			}
  61. 		}
  62. 	}
  63. 	return true;
  64. }
  65.  
  66. bool M_Board::Q_check(int **board, int i, int j) {
  67. 	int a = 0, b = 0;
  68. 	// checks horizontal right movement
  69. 	for(a=j+1;a<N;a++) {
  70. 		if(board[i][a]==1) {
  71. 			return false;
  72. 		}
  73. 	}
  74. 	// checks horizontal left movement
  75. 	for(a=j-1;a>=0;a--) {
  76. 		if(board[i][a]==1) {
  77. 			return false;
  78. 		}
  79. 	}
  80. 	// checks vertical up movement
  81. 	for(a=i-1;a>=0;a--) {
  82. 		if(board[a][j]==1) {
  83. 			return false;
  84. 		}
  85. 	}
  86. 	// checks vertical down movement
  87. 	for(a=i+1;a<N;a++) {
  88. 		if(board[a][j]==1) {
  89. 			return false;
  90. 		}
  91. 	}
  92. 	// checks diagonal down-right movement
  93. 	for(a=i+1,b=j+1;a<N,b<N;a++,b++) {
  94. 		if(board[a][b]==1) {
  95. 			return false;
  96. 		}
  97. 	}
  98. 	// checks diagonal up-right movement
  99. 	for(a=i-1,b=j+1;a>=0,b<N;a--,b++) {
  100. 		if(board[a][b]==1) {
  101. 			return false;
  102. 		}
  103. 	}
  104. 	// checks diagonal up-left movement
  105. 	for(a=i-1,b=j-1;a>=0,b>=0;a--,b--) {
  106. 		if(board[a][b]==1) {
  107. 			return false;
  108. 		}
  109. 	}
  110. 	// checks diagonal down-left movement
  111. 	for(a=i+1,b=j-1;a<N,b>=0;a++,b--) {
  112. 		if(board[a][b]==1) {
  113. 			return false;
  114. 		}
  115. 	}
  116. 	return true;
  117. }
  118.  
  119. void M_Board::print_MBoard() {
  120. 	int i = 0, j = 0;
  121. 	cout << endl << endl;
  122. 	for(i=0;i<N;i++) {
  123. 		cout << " _";
  124. 	}
  125. 	cout << endl;
  126. 	i = 0;
  127. 	for(i=0;i<N;i++) {
  128. 		cout << "|";
  129. 		for(j=0;j<N;j++) {
  130. 			if(m_board[i][j]==0) {
  131. 				cout << "_";
  132. 				cout << "|";
  133. 			}
  134. 			if(m_board[i][j]==1) {
  135. 				cout << "Q";
  136. 				cout << "|";
  137. 			}
  138. 		}
  139. 		cout << endl;
  140. 	}	
  141. }
  142.  
  143. void M_Board::put_Queen(int i, int j) {
  144. 	m_board[i][j] = 1;
  145. 	QCount++;
  146. 	return;
  147. }
  148.  
  149. int main(void) {
  150. 	M_Board board1;
  151. 	board1.put_Queen(0,3);
  152. 	board1.put_Queen(1,6);
  153. 	board1.put_Queen(2,2);
  154. 	board1.put_Queen(3,7);
  155. 	board1.put_Queen(4,1);
  156. 	board1.put_Queen(5,4);
  157. 	board1.put_Queen(6,0);
  158. 	board1.put_Queen(7,5); // the "guilty" line!
  159. 	if(board1.check_MBoard()==false) {
  160. 		cout << "La posizione non e' valida!\n";
  161. 	}
  162. 	else {
  163. 		cout << "La posizione e' valida\n";
  164. 	}
  165. 	board1.print_MBoard();
  166. 	return 0;
  167. }

Edit: it's not the line
C++ Syntax (Toggle Plain Text) 
  1. 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...
Last edited by mrboolf; Jun 18th, 2008 at 1:58 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 296
Reputation: tesuji is on a distinguished road 
Solved Threads: 42
tesuji tesuji is offline Offline
Posting Whiz in Training

Re: 8 Queens Problem - Segmentation Fault

 
0
  #2
Jun 18th, 2008
Hi mrboolf,

•
•
•
•
Originally Posted by mrboolf View Post
. . .
c++ Syntax (Toggle Plain Text) 
  1.  
  2. M_Board::M_Board() {
  3. 	int i = 0, j = 0;
  4. 	m_board = new int*[N];
  5. 	for(i=0;i<N;i++) {
  6. 		m_board[i] = new int[N];
  7. 	}
  8. 	i = 0;
  9. 	for(i=0;i<N;i++) {
  10. 		for(j=0;j<N;j++) {
  11. 			m_board[i][j] = 0;
  12. 		}
  13. 	}
  14. 	QCount = 0;
  15. }
  16.  
  17. M_Board::~M_Board() {
  18. 	int i = 0;
  19. 	for(i=0;i<N;i++) {
  20. 		delete [] m_board[i];
  21. 	}
  22. 	delete [] m_board;
  23. }
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
Last edited by tesuji; Jun 18th, 2008 at 3:03 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Nov 2007
Posts: 981
Reputation: mitrmkar is just really nice mitrmkar is just really nice mitrmkar is just really nice mitrmkar is just really nice mitrmkar is just really nice 
Solved Threads: 210
mitrmkar mitrmkar is offline Offline
Posting Shark

Re: 8 Queens Problem - Segmentation Fault

 
0
  #3
Jun 18th, 2008
a gets a negative value (-1) in the following loop.
C++ Syntax (Toggle Plain Text) 
  1. 	// checks diagonal up-right movement
  2. 	for(a=i-1,b=j+1;a>=0, b<N;a--,b++) {
  3. 		if(board[a][b]==1) {

The comma operator a>=0, b<N is not doing what you probably expect.
Last edited by mitrmkar; Jun 18th, 2008 at 3:32 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 296
Reputation: tesuji is on a distinguished road 
Solved Threads: 42
tesuji tesuji is offline Offline
Posting Whiz in Training

Re: 8 Queens Problem - Segmentation Fault

 
0
  #4
Jun 18th, 2008
sorry, completely nonsense what I wrote ! so forget it.
true, new <--> delete and malloc <--> free
sorry for telling that nonsens

krs,
tesu
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2008
Posts: 182
Reputation: mrboolf will become famous soon enough mrboolf will become famous soon enough 
Solved Threads: 18
mrboolf mrboolf is offline Offline
Junior Poster

Re: 8 Queens Problem - Segmentation Fault

 
0
  #5
Jun 18th, 2008
Thank you all for fast reply!

•
•
•
•
a gets a negative value (-1) in the following loop.
C++ Syntax (Toggle Plain Text) 
  1. 	// checks diagonal up-right movement
  2. 	for(a=i-1,b=j+1;a>=0, b<N;a--,b++) {
  3. 		if(board[a][b]==1) {
  4.  
  5. // 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

C++ Syntax (Toggle Plain Text) 
  1. // checks diagonal down-right movement
  2. 	for(a=i+1,b=j+1;(a<N)&&(b<N);a++,b++) {
  3. 		if(board[a][b]==1) {
  4. 			return false;
  5. 		}
  6. 	}
  7. 	// checks diagonal up-right movement
  8. 	for(a=i-1,b=j+1;(a>=0)&&(b<N);a--,b++) {
  9. 		if(board[a][b]==1) {
  10. 			return false;
  11. 		}
  12. 	}
  13. 	// checks diagonal up-left movement
  14. 	for(a=i-1,b=j-1;(a>=0)&&(b>=0);a--,b--) {
  15. 		if(board[a][b]==1) {
  16. 			return false;
  17. 		}
  18. 	}
  19. 	// checks diagonal down-left movement
  20. 	for(a=i+1,b=j-1;(a<N)&&(b>=0);a++,b--) {
  21. 		if(board[a][b]==1) {
  22. 			return false;
  23. 		}
  24. 	}

it works fine. Thank you mitrmkar!

For tesuji: don't worry and thanks for the advice
Reply With Quote Quick reply to this message  
•
•
Join Date: Apr 2008
Posts: 296
Reputation: tesuji is on a distinguished road 
Solved Threads: 42
tesuji tesuji is offline Offline
Posting Whiz in Training

Re: 8 Queens Problem - Segmentation Fault

 
0
  #6
Jun 18th, 2008
thx

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.
c++ Syntax (Toggle Plain Text) 
  1.     int nbs=0;
  2.     void Queens(int nn, int row[], int k=0)
  3.     { if(k==nn)
  4.       { cout<<endl<<"Solution "<<(++nbs)<<":"<<endl;
  5.         for(int i=0; i<nn; i++)
  6.         { for(int j=0; j<nn;j++)
  7.           { if(row[i]==j) cout<<("Q "); else cout<<(". ");
  8.           } cout<<endl;} cout<<endl;}
  9.       else
  10.       { for(int i=0; i<nn; i++)
  11.         { row[k]=i;
  12.           for(int j=0; j<k;j++)
  13.           { if((row[j]==row[k])||((row[j]-row[k])==(k-j))
  14.             ||((row[k]-row[j])==(k-j))) goto fails;
  15.           } Queens(nn, row, k+1); fails:;}}
  16.     }
  17.     int qu_main(int argc, char *argv[])
  18.     { const int nn = 8;
  19.       int *row = new int[nn];
  20.       Queens(nn, row);
  21. 	  return 0;
  22.     }

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
Last edited by tesuji; Jun 18th, 2008 at 6:48 pm.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jun 2008
Posts: 182
Reputation: mrboolf will become famous soon enough mrboolf will become famous soon enough 
Solved Threads: 18
mrboolf mrboolf is offline Offline
Junior Poster

Re: 8 Queens Problem - Segmentation Fault

 
0
  #7
Jun 20th, 2008
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.
Last edited by mrboolf; Jun 20th, 2008 at 9:02 am.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
This thread has been marked solved.
Perhaps start a new thread instead?
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Other Threads in the C++ Forum


Views: 1980 | Replies: 6
Thread Tools Search this Thread



Tag cloud for C++
6 api application array arrays assignment beginner binary bitmap c++ c/c++ calculator char class classes code coding compile compiler console conversion convert count data database delete developer display dll email encryption error file forms fstream function functions game generator getline givemetehcodez graph homeworkhelper iamthwee ifstream image input int java lazy lib loop looping loops map math matrix memory multidimensional multiple newbie news node number output parameter pointer problem program programming project proxy python random read recursion recursive reference return sort sorting string strings struct template templates text tree url variable vector video visual visualstudio win32 windows winsock word wordfrequency wxwidgets
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC