Public Group

Eight Queens : arrays and recursion

This topic is 4895 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

So I was doing this eight queens problem as an exercise in arrays and recursion. I made a recursive function to try all possible combinations of queen locations on the board. All seems to work well enough but there are only 92 solutions (when not counting mirroring and rotation) but I get 96. So I went back and tried to debug by adding in some more functionality. I narrowed the problem down to whenever there is a solution with a queen in the 7,7 spot I get a duplicate of that solution. Now I just can't seem to figure out why it is doing this. I've looked over the code trying to figure it out but am at a loss. Any help would be appreciated.
// Eight Queens : Recursively find all solutions
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

const int nSize = 8;		// board size, default of 8
int nSolutions = 0;			// number of solutions found
int solution[100] = { 0 };	// added for debugging; array to hold number codes for each solution

void eightQueens( int queen );
void check( int [][nSize] );
void print( int [][nSize] );
void encode( int [][nSize], int solutionNumber );	// added for debugging purposes
int duplicates( int [] );							// added for debugging purposes

int main()
{

cout << "Solutions found: " << nSolutions << endl;
cout << "Duplicates found: " << duplicates( solution ) << endl;

return 0;

}	// end main

void eightQueens( int Q )
{
static int board[nSize][nSize] = { 0 };

if ( Q < nSize )
{
for ( int i = 0; i < nSize; i++ )	// loop thru each row
{

if ( i == 0 )
{
board[ nSize - 1 ][Q] = 0;	// set last row back to empty
board[ i ][Q] = 1;			// fill new position
}
else
{
board[ i - 1 ][Q] = 0;	// set old position back to empty
board[ i ][Q] = 1;		// fill new position
}

eightQueens( Q + 1);		// start moving next queen
check( board );				// check for solution

}	// end for

}

}	// end function eightQueens

// check if current placement on board is a solution
void check( int board[][nSize] )
{
bool solution = true;
int conflicts = 0;

// check rows
for ( int x = 0; x < nSize; x++ )
{
conflicts = 0;
for ( int y = 0; y < nSize; y++ )	// searches 1 row
conflicts += board[x][y];
if ( conflicts > 1 )
solution = false;
}
// check columns
for ( int x = 0; x < nSize; x++ )
{
if ( !solution )
break;

conflicts = 0;
for ( int y = 0; y < nSize; y++ )	// searches 1 column
conflicts += board[y][x];
if ( conflicts > 1 )
solution = false;
}
// check diagonals
// check right-down
for ( int x = 0; x < nSize; x++ )
{
if ( !solution )
break;

for ( int y = 0; y < nSize; y++ )
{
if ( !solution )
break;

conflicts = 0;
for ( int n = 0; x + n < nSize && y + n < nSize; n++ )	// searches along diagonal from x,y
conflicts += board[x+n][y+n];

if ( conflicts > 1 )
solution = false;
}
}

// check right-up
for ( int x = 0; x < nSize; x++ )
{
if ( !solution )
break;

for ( int y = 0; y < nSize; y++ )
{
if ( !solution )
break;

conflicts = 0;
for ( int n = 0; x + n < nSize && y - n > -1; n++ )
conflicts += board[x+n][y-n];

if ( conflicts > 1 )
solution = false;
}
}

if ( solution )	// if board is a solution then display it
{
++nSolutions;

cout << "Solution # " << nSolutions << endl;
// assign solution code
encode( board, nSolutions );
// print the board
print( board );
cout << endl;

if ( nSolutions % 8 == 0 )	// pause after 8 solutions have printed
{
cout << "PAUSED: Press a key to continue" << endl;
cin.get();
}
}

}	// end function check

void print( int board[][nSize] )
{
for ( int i = 0; i < nSize; i++ )
{

for ( int j = 0; j < nSize; j++ )
{
if ( board[j] == 0 )
cout << "  " << "x";
else
cout << "  " << "Q";
}

cout << endl << endl;

}

}	// end function print

// ***********************************
// Following 2 functions for debugging
// ***********************************

// assigns a number code to solution n
// ex. 15863724 : 1 = first column queen in row 1, 5 = second column queen in row 5, etc.
void encode( int board[][nSize], int n )
{
int code[nSize];

// find position of each queen
for ( int x = 0; x < nSize; x++ )
{
for ( int y = 0; y < nSize; y++ )
{
if ( board[y][x] == 1 )
code[x] = y + 1;
}
}

solution[n] = (code[0] * 10000000) + (code[1] * 1000000) + (code[2] * 100000) + (code[3] * 10000) + (code[4] * 1000) + (code[5] * 100) + (code[6] * 10) + code[7];
cout << solution[n] << endl;
}	// end function encode

// searches for solutions with duplicate number codes
int duplicates( int a[] )
{
int n = 0;

for ( int i = 0; i < 100; i++ )
{
for ( int j = 0; j < 100; j++ )
{
if ( i != j )
{
if ( a == a[j] && a != 0 && a[j] != 0 )
{
++n;
a[j] = 0;
cout << "Duplicate in " << i << "<->" << j << endl;
}
}
}
}

return n;

}



Share on other sites
I found the problem :)

When the last queen moved to the last row (7,7) the stack would drop back to the previous eightQueens call. The point where it returns is right before the call to check for a solution so it was checking that same solution twice. I added in a static bool to check if a solution was found when the stack collapses( i think this is what you call it? ) Anyway, that seems to have fixed it.

edit: I also made the check function return a bool for my if statement to work.

updated function:
void eightQueens( int Q )	{	static int board[nSize][nSize] = { 0 };	static bool solutionOnBreak = false;		if ( Q < nSize )	{		for ( int i = 0; i < nSize; i++ )	// loop thru each row		{							solutionOnBreak = false;						if ( i == 0 )			{				board[ nSize - 1 ][Q] = 0;	// set last row back to empty				board[ i ][Q] = 1;			// fill new position			}			else			{				board[ i - 1 ][Q] = 0;	// set old position back to empty				board[ i ][Q] = 1;		// fill new position			}						eightQueens( Q + 1);		// start moving next queen						if ( !solutionOnBreak )	// check for solution				if( check( board ) )					solutionOnBreak = true;				}	// end for		}}	// end function eightQueens

• What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 15
• 14
• 46
• 22
• 27
• Forum Statistics

• Total Topics
634046
• Total Posts
3015225
×