Chess - Programming - de Bruijn Sequence

A de Bruijn Sequence represents all possible sequences of a given length in a way that is as compressed as possible.

It can be used to build a private bitScanForward routine, and to get the LSB (Least Significant Bit).

A chess board is conveniently 8 x 8 squares, and these can be represented by the numbers 0-63, which is a nice fit for a six-bit long De Bruijn sequence.

• 64-bit De Bruijn Sequences are 64(+5 wrapped)-bit strings, containing 64 overlapping unique sub-strings (ld(64)==6-bits).
• Because multiplying a De Bruijn Sequence with a single bit or power of two value acts like a shift left, this multiply with extracting the upper six bits by shift right 64-6=58 is a well known bitscan-approach to determine the index/position of a single isolated one in a 64-bit word.
• The are 67,108,864 == 0x4000000 == 2^26 Sequences with start index 0 and therefore last index 32 (last index requires wrap of the 5 upper bits, which are all zero).
  • There are 64 times more sequences by rotating the initial one.
  • So in total 2^32 possible 64*6bit De Bruijn Sequences!

The cyclic sequence 0000100110101111 of length 16 is a de Bruijn sequence for n = 4.

The 16 unique sub-strings of length 4 when considered cyclicly are:

0000,0001,0010,0100,1001,0011,0110,1101,1010,0101,1011,0111,1111,1110,1100,1000

Taking each 4-bits

0000100110101111

returns:

0000
 0001
  0010
   0100
    1001
     0011
      0110
       1101
        1010
         0101
          1011
           0111
            1111
             1110

About De Bruijn Sequences

De Bruijn Sequence Generator

De Bruijn Sequence on a Chess Board

Get De Bruijn Sequence

Using a De Bruijn Sequence

8-bit Example

TODO

Why does the standard numbering equation for de Bruijn sequences give differing results for dB(16,4) and dB(2,16), when both are 16 bits?
De Bruijn sequences are numbered by the equation
dB(k,n) = ((k!)^(k^(n-1)))/(k^n).
When we have dB(2,16), the computed value is of the order 2.1598E+9859 .
For dB(16,4), the computed value is of the order 2.7629E+54556.
Yet, both sequences are represented within just 64K bytes of memory.
Only one of these computations can be correct.

https://en.wikipedia.org/wiki/De_Bruijn_sequence

https://www.chessprogramming.org/De_Bruijn_Sequence

http://supertech.csail.mit.edu/papers/debruijn.pdf

https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.1038.9096&rep=rep1&type=pdf

https://stackoverflow.com/questions/37083402/fastest-way-to-get-last-significant-bit-position-in-a-ulong-c

https://cstheory.stackexchange.com/questions/19524/using-the-de-bruijn-sequence-to-find-the-lceil-log-2-v-rceil-of-an-integer

https://docplayer.net/167480236-Using-de-bruijn-sequences-to-index-a-1-in-a-computer-word-charles-e-leiserson-harald-prokop-keith-h-randall-mit-laboratory-for-computer-science-cam.html