Jump to content
  • Advertisement
Sign in to follow this  
gnomer

Eight Queens : arrays and recursion

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

If you intended to correct an error in the post then please contact us.

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()
{
	eightQueens( 0 );	// start with queen 0

	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 this post


Link to post
Share on other sites
Advertisement
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


Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!