Silent Matt

8 Queens Solver in 31 Bits

The Story

A few years ago, my brother and I were eating lunch at college. As usual, we started talking about computer stuff—solving the 8-queens problem specifically (see below, for an explanation). Eventually, one of us (I don’t remember who it was now) realized that, in the specific case of the 8-queens problem, the whole board could be represented with just 24 bits—not even a whole 32-bit integer. Since there can only be one queen in each row, the state of the board could be represented by storing the column of the queen in each row. So, 3 bits for the column (0-7) times 8 rows makes 24 bits.

As we talked about it, we realized that the extra 8 bits in a 32-bit integer was enough (with 2 bits to spare) to store two loop counters that go from 0 to 7. Using one more bit as a flag to indicate an invalid board, we could store the entire state of an 8-queens solver in 31 bits. Once we realized that it could be done, we had to do it. It took us an hour or two to write the program (which should take, maybe 15-20 minutes doing it the normal way), but it actually works. You can see the code below (If any of my former teachers or my boss sees this, this is not how I normally write code).

What is the 8-queens problem?

The “8-queens problem,” or more generally, the n-queens problem is a math/computer science problem where you try to put 8 chess queens (or n) on a standard 8×8 chess board (or nxn chess board) so that none of them can attack any other queen. Basically, none of them can be in the same row or column as any other queen, or along a common diagonal. If none of that made sense, you could try reading about it on the Wikipedia article.

The Code

Here’s the code, written in C. You can also download the C file and compile it yourself.

The single variable is called S for state. Just to be clear, the single-variable rule only applies to the algorithm, not output functions (putchar could have its own variables).

The code is hard to read (even if you know C and wrote it), so I won’t even try to explain it. Just trust me; it works. /* You are not expected to understand this */

#include <stdio.h>

#define X ((S&255)>>5)
#define Y ((S&31)>>2)
#define I ((S&255)>>4)
#define J ((S&15))
#define P(R) ((S>>(8+((R)*3)))&7)

int main()
{
   int S = 0;
   while (S != -256) {
      S |= 2;
      do {
         S = (S & ~28) | ((X + 1) << 2);
         while (Y) {
            if (!(P(Y)-P(X)) || !(P(Y)-P(X)-Y+X) || !(P(Y)-P(X)+Y-X))
               S &= ~2;
            S += 4;
         }
      } while (X < 7);
      if (S & 2) {
         S = (S & 0xffffff00) | 136;
         while (I) {
            while (J) {
               putchar((!(P(I-1)-J+1)) ? 'Q' : '-');
               putchar(' ');
               S = (S & ~15) | (J - 1);
            }
            putchar('\n');
            S = (S & ~255) | ((I - 1) << 4) | 8;
         }
         putchar('\n');
         S = (S & 0xffffffe0) | 0xe0;
      }
      S += 32;
   }
   return 0;
}

In case you are interested, here’s the output. The program does not check for solutions that are mirror images or rotations, so it prints lots of “duplicate” answers.

- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -

- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -

- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -

- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -

- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -

- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -

- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -

- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - Q - -
- - - Q - - - -

- - - - - - Q -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -

- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -

- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
- - - - - Q - -

- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -

- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q

- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -

- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -

- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -

- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -

- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -

- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -

- - - - - Q - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q

- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -

- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -

- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -

- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -

- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -

- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -

- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -

- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -

- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- Q - - - - - -

- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -

- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q

- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -

- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -

- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -

- - - - Q - - -
- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -

- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -

- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -

- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -

- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - Q - - - - -

- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -

- - - - Q - - -
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -

- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -

- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -

- - - Q - - - -
- - - - - - - Q
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -

- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -

- - - Q - - - -
- - - - - - - Q
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -

- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- - Q - - - - -
Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -

- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q

- - - Q - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
Q - - - - - - -
- - - - - Q - -

- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
- - Q - - - - -

- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -

- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -

- - - Q - - - -
- - - - - Q - -
Q - - - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -

- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -

- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - Q - -

- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -

- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -

- - - Q - - - -
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -

- - - Q - - - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - Q -

- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -

- - - Q - - - -
Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -

- - Q - - - - -
- - - - - - - Q
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -

- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - Q - - -

- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -

- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -

- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -

- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -

- - Q - - - - -
- - - - - Q - -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - Q - - -
- - - - - - Q -
- Q - - - - - -

- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
Q - - - - - - -
- - - - - - - Q
- - - Q - - - -

- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- - - - - - - Q
- - - - Q - - -

- - Q - - - - -
- - - - - Q - -
- Q - - - - - -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -

- - Q - - - - -
- - - - Q - - -
- - - - - - - Q
- - - Q - - - -
Q - - - - - - -
- - - - - - Q -
- Q - - - - - -
- - - - - Q - -

- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - - Q - - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -

- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -
- - - - - - Q -
Q - - - - - - -

- - Q - - - - -
- - - - Q - - -
- Q - - - - - -
- - - - - - - Q
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -

- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -

- Q - - - - - -
- - - - - - - Q
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -

- Q - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
Q - - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - - - - Q -
- - Q - - - - -
- - - - - Q - -
- - - - - - - Q
- - - - Q - - -
Q - - - - - - -
- - - Q - - - -

- Q - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -

- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - - - Q
- - Q - - - - -
- - - - Q - - -

- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
- - - Q - - - -
Q - - - - - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -

- Q - - - - - -
- - - - Q - - -
- - - - - - Q -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
- - - - - Q - -
- - - Q - - - -

- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
Q - - - - - - -
- - - - - - Q -
- - - - Q - - -

Q - - - - - - -
- - - - - - Q -
- - - - Q - - -
- - - - - - - Q
- Q - - - - - -
- - - Q - - - -
- - - - - Q - -
- - Q - - - - -

Q - - - - - - -
- - - - - - Q -
- - - Q - - - -
- - - - - Q - -
- - - - - - - Q
- Q - - - - - -
- - - - Q - - -
- - Q - - - - -

Q - - - - - - -
- - - - - Q - -
- - - - - - - Q
- - Q - - - - -
- - - - - - Q -
- - - Q - - - -
- Q - - - - - -
- - - - Q - - -

Q - - - - - - -
- - - - Q - - -
- - - - - - - Q
- - - - - Q - -
- - Q - - - - -
- - - - - - Q -
- Q - - - - - -
- - - Q - - - -