Eight Queens part zero

How many queens can be put on a chess board where none of them are attacking any others?

A chess board has eight by eight squares. A queen attacks all squares in the same row or the same column, or on either of the two diagonals.

If one considers putting queens on a chess board at random, the maximum number of board positions to consider is 64! That is, one puts a queen on the board, and there are 64 choices for where to put her. For the second position, there are only 63 open squares left. So for two queens, 64 * 63 positions need to be considered. There are 64 squares, so the maximum number of queens is 64. The number of positions to check is 64 * 63 * 62... or a total of 64!. That's about 10^89 positions. All the computers on Earth could not check that many board positions in the current age of the Universe. The overwhelming majority of these board positions can be shown to have at least two queens attacking each other. And there are some simple ideas to eliminate whole chunks of these at a time. For example, here's one idea.

Since a queen attacks all the squares in the same column, one can't have two queens in the same column. Since there are only eight columns on a chess board, it's not possible to have more than eight queens on a chess board without any attacking any others. It can be ruled out. That doesn't mean that there are any board positions with eight queens. It only means there aren't any with nine or more. This is apparently obvious enough that the problem is called the Eight Queens problem.

This not-in-the-same-column rule means that the queen in the first column can be in any of eight positions. For each of those, the queen in the second column can be in any of eight positions, for eight squared combinations. It follows that the total number of board positions to check is eight to the eigth power (8^8), or a bit over 16 million board positions. This is a speed increase over our original idea of a factor of about 10^81.

The Eight Queens problem, is an example of a combinatorial problem. It is said to be NP-complete. The solutions for these problems suggest that the entire solution space must be searched to find solutions. NP-complete problems strike fear in the hearts of computer science students. Having never been a computer science student, it's not much of a worry. However, my understanding of gravity is excellent, so acrophobia is available. It's always something.

While at school in 1979, i had a job sitting behind the I/O desk, answering student's computer questions. One day, an advanced computer science student asked me about the problem. The professor had likely read Dijkstra's 1972 article, and assigned it to a class. He prepared the class for the worst by implementing an 8^8 solution that attempted to get all solutions by brute force. After three days, it had covered a third of the solution space, and he killed it. The estimate was nine days for the full solution. This is on a PDP-10 designed in 1966 that performed at about a fifth of a MIPS.

Anyway, on a modern machine, 10^7 is not such a big number of things to do, so let's just plow into it. How should a computer program represent the board? It could have an eight by eight grid, with a one representing a queen, and a zero representing an open space. Since the numbers are either zero or one, the numbers don't have to be larger than one bit. 64 bits could be used.

A program with this representation needs code to generate a first board position, code to generate the next board position in any way that covers all possible board positions, code to check to see if a board position is a solution, and code to print or otherwise note a solution. One can imagine each of these routines. The first board position could be all eight queens at the bottoms of their columns. The next board position could move the rightmost queen up a row. But if that move the queen off the top of the board, it should move it down to the bottom of that column, and move the queen to the left up a row. When all the queens are at the top, it should report that all positions have been searched. The check for win must check each queen's row for other queens, and each queen's diagonals for other queens. A board position print might print a space where there are zeros and a queen where there are ones in an eight by eight square.

Here's another way to represent a board position. In each column, only one queen may be present. So each column can be represented by a single number. This number says what row that queen is in. There are only eight columns, so there are only eight numbers. Each column has eight rows. So each number can have one of eight values, so only three bits are needed. That's a total of 24 bits. In any case, you can think of each column as a digit in a number. As long as the digits are constrained to one of eight unique digits, you can count through all possible board positions. One of the nice features of this representation (compared with a bit per square) is that as you "count" through possible board positions, you don't have to check that two queens are in the same column. That is, the board representation can't violate this constraint, so there's no need to check.

The same routines are needed for the eight numbers as above. If each digit is one through eight, then the intial board could be all ones. The next board looks like counting by one. Checking for a queen in the same row is the same as checking the other queens for the same digit number. Checking diagonals is a bit more complicated. Two columns that are next to each other have a diagonal that are off by one row. If they're one row farther apart, then diagonals are two rows different. Finally, though a full board can be printed, it's easy enough to simply print the row numbers for each column.

This 8^8 Perl program takes 50 seconds to find all solutions. That's because a modern desktop machine is at least 15,000 times faster.

#!/usr/bin/perl
# Chess boards where 8 queens are not attacking each other.
# Can't have two queens in the same column.
# Represent row numbers in columns.
# There are 8^8 (1e7) positions to check.
# 50 seconds - 335544 board checks per second.

# main and global variables
my $col = 0; # current column under consideration
my $x;
my @b; # board, 0 - 7 are columns, values 0 - 7 are positions
my $cnt = 0;

# Set board to queens at bottom.
for ($x = 0; $x < 8; $x++) {
 $b[$x] = 0;
}
while (1) {
 if (&chkwin()) { # check for a win
  $cnt++;
  &prbrd();
 }
 if (&incbrd() == -1) { # increment the board
  print "Done $cnt winning boards.\n";
  exit(0);
 }
}

sub incbrd { # Increment board.
 my $col = 7;

 $b[$col]++;
 while ($b[$col] > 7) {
  if ($col != 0) {
   $b[$col] = 0;
   $col--;
   $b[$col]++;
  } else {
   return -1; # Puzzle is done
  }
 }
 return $col;
}

sub chkwin { # Check a board for a win.
 my ($x, $y, $a);

 for ($x = 0; $x < 8; $x++) { # Check row
  for ($y = $x + 1; $y < 8; $y++) {
   if ($b[$x] == $b[$y]) {
    return 0; # not win
   }
  }
 }
 for ($x = 0; $x < 8; $x++) { # Check diagonals
  $a = 1;
  for ($y = $x + 1; $y < 8; $y++) {
   if (($b[$y] - $a == $b[$x]) ||
       ($b[$y] + $a == $b[$x])) {
    return 0; # not win
   }
   $a++;
  }
 }
 return 1; # win
}

sub prbrd { # Show the board.
 my $x;

 for ($x = 0; $x < 8; $x++) {
  print "$b[$x]";
 }
 print "\n";
}
0;

The Eight Queens wiki page tells us that the first solutions were found in 1850, about 96 years before the first fully functional computer, depending on who you talk to, and what your definition of fully functional computer is. If any solutions can be found by hand, there must be better ways to approach this problem.

My help to the student was likely limited to some hand waving about reducing the problem space, without any real direction. A couple days later, he showed me that he'd reduced the time required to less than a second. He even removed the print statements showing that most of that time was spent printing the answers. There are only 92 of them.

In the next part, the problem is approached using a better technique. It may seem pointless, since the most time that can be saved is about fifty seconds. But the general technique can be used on many such problems. And many of these problems are considerably more complicated. It's best to practice on easier problems first.