Every so often I click on the **Random Post** link at the top right of the site, and have another look at a previously published problem. And sometimes I’ll think about attacking a problem in a different way than my original solution, and post an additional comment.

I recently revisited **Enigma 69: Maximum Queen moves** to see if I could think of a better algorithm to enable me to expand the analysis beyond a 5×5 board. As it happened I didn’t come up with a better algorithm, but I did refine the one I’d previously published to be more efficient. By eliminating symmetrically equivalent positions, using bit vectors to represent the board, and pre-computing moves I was able to get my program running about 150 times faster than my simple implementation. While this isn’t enough to rescue the pathologically slow nature of the algorithm as the size of the board increases, it does bring the solution for the 6×6 board into a feasible time frame.

After 14 hours of CPU time (less actual time, as we can run multiple copies of the program to consider different numbers of Queens) I was able to confirm that 128 moves was indeed maximal for the 6×6 board, with the Queens arranged in a “border” configuration (and I was able to do some analysis, but not an exhaustive treatment, of the 7×7, 8×8 and 9×9 boards).

As the board was now represented by a bit vector, I was looking for an efficient way to generate all *k*-bit patterns in an *n*-bit vector. And that was when I stumbled on the **Bit Twiddling Hacks** page. Right down at the end of the page is a section called *“Compute the lexicographically next bit permutation”*.

The page is primarily concerned with C (or C++) code, but the implementation in *Python* is as follows.

Suppose we start with the variable `v` holding an integer with *k* bits set when represented in binary. Then the following code fragment computes `w`, which is the next largest integer after `v` that also has *k* bits set in it’s binary representation.

t = (v | (v - 1)) + 1
w = t | ((((t & -t) // (v & -v)) >> 1) - 1)

So, if we want to generate all 8-bit numbers with exactly 2 bits set, we can simply start with the smallest number with 2 bits set (11 in binary, which is 3 in decimal), and keep applying the the code above until we exceed 255 (the largest 8-bit number).

v = 3
while v < 256:
print(f"{v:08b} = {v}")
t = (v | (v - 1)) + 1
v = t | ((((t & -t) // (v & -v)) >> 1) - 1)

When run (under *Python* 3.6*)* we get the following result:

00000011 = 3
00000101 = 5
00000110 = 6
00001001 = 9
00001010 = 10
00001100 = 12
00010001 = 17
00010010 = 18
00010100 = 20
00011000 = 24
00100001 = 33
00100010 = 34
00100100 = 36
00101000 = 40
00110000 = 48
01000001 = 65
01000010 = 66
01000100 = 68
01001000 = 72
01010000 = 80
01100000 = 96
10000001 = 129
10000010 = 130
10000100 = 132
10001000 = 136
10010000 = 144
10100000 = 160
11000000 = 192

Which is a complete list of all 28 8-bit integers with exactly 2 bits set, in numerical order. And if we didn’t limit the numbers to 8-bits the program would continue generating integers with exactly 2 bits set indefinitely.

I might add this function to the **enigma.py** library (if I can think of a good name for it), but if you are trying to speed up a program it will probably be faster to just use the code fragment inline.

## Recent Comments