Jump to content
  • Advertisement
Sign in to follow this  
  • entries
    149
  • comments
    510
  • views
    95210

8 queens beats a full house

Sign in to follow this  
noaktree

113 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
Sign in to follow this  


3 Comments


Recommended Comments

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

Share this comment


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

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!