Robson » Little Red Book » Eight Queens

Chapter 9 - Question 5

The chess board and pieces are a source of many intriguing problems. One such is:

Eight queens are to be placed on a chess board in such a way that no queen could capture any of the others.

Solution 1

I'm going to work this out by feeding some simple rules into a script and then making the script do the hard work.

Horizontal matching is sorted by only placing one queen on each row.

Vertical matching is sorted by taking any array of the values 0 to 7 and shuffling it, then placing the queen for each row on the corresponding square across.

So all solutions generated will be fine horizontal and vertical. This means the actual work is taken up by generating solutions until one works for diagonals as well.

PHP:

<?
   // all queens must be on a different vertical line
   $pos = array(0, 1, 2, 3, 4, 5, 6, 7);
   
   // loop at least once
   do
   {
       // use a random order each time
       shuffle($pos);
   
       // loop through each row
       for ($n = 0; $n < 8; $n++)
       {
           // write empty squares across
           $board[$n] = array_fill(0, 8, 0);
           // place a queen in one square
           // this takes care of horizontal matching
           $board[$n][$pos[$n]] = 1;
       }
       
       // reset the invalid variable
       $invalid = false;
       // loop through each row
       for ($a = 0; $a < 8 && !$invalid; $a++)
       {
           // loop through each potential column
           for ($b = 0; $b < 12 && !$invalid; $b++)
           {
               // determine the difference between each row
               // this is then used to calculate the position of all the potential hits
               $diff = ($b - $a) + 1;
               // check the diagonal rule
               $invalid =
                   // check it's inside the board and not the same square
                   $a-$diff >= 0 && $a-$diff <= 7 && $diff &&
                   (
                       // check if the square is inside the board
                       // and check if it's occupied
                       ($pos[$a]-$diff >= 0 && $pos[$a]-$diff < 8 && $board[$a-$diff][$pos[$a]-$diff] == 1)
                       ||
                       ($pos[$a]+$diff >= 0 && $pos[$a]+$diff < 8 && $board[$a-$diff][$pos[$a]+$diff] == 1)
                   );
           }
       }
       // increment the attempts
       $counter++;
   }
   // loop until a valid solution is found
   // or until too many attempts have been made
   while ($invalid && $counter < 1000);
 
   // check if the loop terminated because it took too long
   if ($invalid)
       // just fail with a message
       echo 'The script has stopped early because a solution was not found in time. '
          . 'Try refreshing this page to find a solution.';
   else
   {    
       // output the board
       for ($n = 0; $n < 8; $n++)
           // show the empty and filled squares
           echo implode('', $board[$n]) . '<br/>';
           
       // show how many tries it took to find a solution
       echo 'Attempts: ' . $counter . '.';
   }
?>

Which produces:

00000001
00100000
10000000
00000100
01000000
00001000
00000010
00010000
Attempts: 320.

Log

© 2004-17 robson | cc unless stated