====== Chess - Programming - de Bruijn Sequence - De Bruijn Sequence on a Chess Board ======
===== De Bruijn Graph on a Chess Board =====
A directed De Bruijn Graph of B(2, 6) sequences with Little-Endian Rank-File Mapping board coordinates (a1 = 0, b1 = 1, h8 = 63).
* For topology reasons, almost each node (except a1 and h8) of the graph is de-concentrated and appears twice in the form of two reversed binary trees.
* The leaf outputs join the respective reversed tree.
* Between c6 and f3 is a direct cycle, since 42 is 2*21 and 21 is (2*42 + 1) % 64, with both six-bit pattern reversed - 010101 (21) versus 101010 (42).
* The challenge is to traverse the graph in any way to visit each of the 64 nodes aka squares __exactly once__.
+----------------->---------------a1--------------<-----------------+
| | |
| b1 |
| +--------------/ \-------------+ |
| c1 d1 |
^ +-----/ \-----+ +-----/ \-----+ |
| e1 f1 g1 h1 |
| +-/ \-+ +-/ \-+ +-/ \-+ +-/ \-+ |
| a2 b2 c2 d2 e2 f2 g2 h2 |
| a3 b3 c3 d3 e3 |f3| g3 h3 a4 b4 c4 d4 e4 f4 g4 h4 |
+-a5b5c5d5e5f5g5h5a6b6c6d6e6f6g6h6 a7b7c7d7e7f7g7h7a8b8c8d8e8f8 | |
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ | |
| |
+----------------->---------------h8--------------<--------------+ ^
| | |
| g8 |
| +--------------/ \-------------+ |
| f8 e8 |
^ +-----/ \-----+ +-----/ \-----+ |
| d8 c8 b8 a8 |
| +-/ \-+ +-/ \-+ +-/ \-+ +-/ \-+ |
| h7 g7 f7 e7 d7 c7 b7 a7 |
| h6 g6 f6 e6 d6 |c6| b6 a6 h5 g5 f5 e5 d5 c5 b5 a5--+
+-h4g4f4e4d4c4b4a4h3g3f3e3d3c3b3a3 h2g2f2e2d2c2b2a2h1g1f1e1d1c1
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
----
===== B(2, 6) =====
De Bruijn sequences can be described by two parameters:
* **k**: The number of entities in the alphabet e.g. {0,1,2,3,4,5,6,7,8,9} for k=10
* **n**: the order (length of sub-sequence required) e.g. n=4 for a four digit long PIN.
**B(2, 6)** implies 2^6 or 64 bit sequences.
* There are 2^26 or 67,108,864 odd 64-bit sequences with 64 overlapping unique six-bit sub-sequences, for instance 0x022fdd63cc95386d.
i 0000001000101111110111010110001111001100100101010011100001101101|00000 s[i]
0 000000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 0
1 000001 1
2 . 000010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
3 000100 4
4 . . 001000 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5 010001 17
6 . . . 100010 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
7 000101 5
8 . . . . 001011 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
9 010111 23
10 . . . . . 101111 . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
11 011111 31
12 . . . . . . 111111 . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13 111110 62
14 . . . . . . . 111101 . . . . . . . . . . . . . . . . . . . . . . . . . 61
15 111011 59
16 . . . . . . . . 110111 . . . . . . . . . . . . . . . . . . . . . . . . 55
17 101110 46
18 . . . . . . . . . 011101 . . . . . . . . . . . . . . . . . . . . . . . 29
19 111010 58
20 . . . . . . . . . . 110101 . . . . . . . . . . . . . . . . . . . . . . 53
21 101011 43
22 . . . . . . . . . . . 010110 . . . . . . . . . . . . . . . . . . . . . 22
23 101100 44
24 . . . . . . . . . . . . 011000 . . . . . . . . . . . . . . . . . . . . 24
25 110001 49
26 . . . . . . . . . . . . . 100011 . . . . . . . . . . . . . . . . . . . 35
27 000111 7
28 . . . . . . . . . . . . . . 001111 . . . . . . . . . . . . . . . . . . 15
29 011110 30
30 . . . . . . . . . . . . . . . 111100 . . . . . . . . . . . . . . . . . 60
31 111001 57
32 . . . . . . . . . . . . . . . . 110011 . . . . . . . . . . . . . . . . 51
33 100110 38
34 . . . . . . . . . . . . . . . . . 001100 . . . . . . . . . . . . . . . 12
35 011001 25
36 . . . . . . . . . . . . . . . . . . 110010 . . . . . . . . . . . . . . 50
37 100100 36
38 . . . . . . . . . . . . . . . . . . . 001001 . . . . . . . . . . . . . 9
39 010010 18
40 . . . . . . . . . . . . . . . . . . . . 100101 . . . . . . . . . . . . 37
41 001010 10
42 . . . . . . . . . . . . . . . . . . . . . 010101 . . . . . . . . . . . 21
43 101010 42
44 . . . . . . . . . . . . . . . . . . . . . . 010100 . . . . . . . . . . 20
45 101001 41
46 . . . . . . . . . . . . . . . . . . . . . . . 010011 . . . . . . . . . 19
47 100111 39
48 . . . . . . . . . . . . . . . . . . . . . . . . 001110 . . . . . . . . 14
49 011100 28
50 . . . . . . . . . . . . . . . . . . . . . . . . . 111000 . . . . . . . 56
51 110000 48
52 . . . . . . . . . . . . . . . . . . . . . . . . . . 100001 . . . . . . 33
53 000011 3
54 . . . . . . . . . . . . . . . . . . . . . . . . . . . 000110 . . . . . 6
55 001101 13
56 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 011011 . . . . 27
57 110110 54
58 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101101 . . . 45
59 01101|0 26
60 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1101|00 . 52
61 101|000 40
62 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 01|0000 16
63 1|00000 32
----