• entries
149
510
• views
94474

# 8 queens beats a full house

87 views

One way to use globals...

I inserted syntax to add and initialize global variables. These globals are only initialized the first time the script is executed or when the reset_globals; keyword is called. In this way data can be shared over a series of script executions. I decided to test out some of the language features by solving that pesky 8 queens problem. I used a single array of integers to store queen positions and three other arrays to assess the threat level of a particular square.

Here is the A2 source:
// Global variables can be used to share data with all functions// The globals can are only initialized the first time a script// is called. The reset_global; keyword can be used at any time// to re-initialize global variables.global{	int Queens[8;]		= {0;0;0;0;0;0;0;0;};	int RowAttack[8;]	= {0;0;0;0;0;0;0;0;};	int NegDiagAttack[15;]	= {0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;};	int PosDiagAttack[15;]	= {0;0;0;0;0;0;0;0;0;0;0;0;0;0;0;};}// This is the entry point of the script// It resets the global variables and then runs the // 8 queens function. After that the values of the// each queen are printed.function void main(void){	// Reset globals	reset_global;		// Solve the 8 queens	Do_8_Queens(0;);		// Print the solution	print "Columns:";	print "0 1 2 3 4 5 6 7";	print "Rows:";	print Queens;	}// This function sets a queen to the global Queens array.// It also sets the attack arrays which are used in the // Is_Under_Attack() function.function void Set_Queen(int Column, int Row){	// Set the queens array	Queens[Column;] = Row;	// Set the RowAttack array	RowAttack[Row;] = 1;	// Set the Negatice Diagnal Attack	NegDiagAttack[(Column - Row)+7;] = 1;	// Set the Positive Diagnal Attack	PosDiagAttack[Column + Row;] = 1;}// This function removes a queen from the global Queens // array. It also removes the attack array values which // are used in the Is_Under_Attack() function.function void Remove_Queen(int Column, int Row){	// Set the queens array	Queens[Column;] = 0;	// Set the RowAttack array	RowAttack[Row;] = 0;	// Set the Negative Diagnal Attack	NegDiagAttack[(Column - Row)+7;] = 0;	// Set the Positive Diagnal Attack	PosDiagAttack[Column + Row;] = 0;}// Determines if a given square is under attack from// another queen. Returns a 1 if the square is under// attack and a 0 if not.function int Is_Under_Attack(int Column, int Row){	// Check row attack	if(RowAttack[Row;] == 1)	{	return 1;	}	// Check negative diagnal attack	if(NegDiagAttack[(Column - Row)+7;] == 1)	{	return 1;	}	// Check positive diagnal attack	if(PosDiagAttack[Column + Row;] == 1)	{	return 1;	}	return 0;}// This function calculates the 8 queen positions// and stores them in the Queens array in the form// Queens[Column_Index] = Row_Index. It uses// recursion and backtracking to solve the problem.// The function must be called with a zero value// and therefore only solves the 8 queens for a single// case when the first queen is in column = 0, row = 0.function int Do_8_Queens(int Column){	// If we surpass 7 columns then we have succeeded	if(Column > 7)	{			return 1;		}	else // We are still looking for a solution	{		int Row = 0;		int Done = 0;		// Loop while not done and still working on rows		while((Done == 0) & (Row <= 7))		{			// Check to see if the current square is under attack			if(Is_Under_Attack(Column; Row;) == 1)			{	// If so then increment the row				Row = Row + 1;			}			else // The square is safe so			{				// Place a queen in that square				Set_Queen(Column; Row;);				// Move on to the next column                                Done = Do_8_Queens(Column+1;);				// If we have not succeeded then							if(Done == 0)				{	// Remove the queen (backtrack)					Remove_Queen(Column; Row;);					// And increment the current row					Row = Row + 1;				}				else // Success				{	return 1;				}			}		}	}	return 0;}

The output looks like this:
Columns:
0 1 2 3 4 5 6 7
Rows:
0 4 7 5 2 6 1 3

Very, very impressive. You have really added a ton of functionality to this language in a short time!

Thanks Corey. I've just had a look at your Voodoo Script language and it's also very nice. [smile]

That's pretty neat. Seems almost as powerful as C now.

## Create an account

Register a new account