Sign in to follow this  
  • entries
    149
  • comments
    510
  • views
    94317

8 queens beats a full house

Sign in to follow this  
noaktree

82 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

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