chess:programming:de_bruijn_sequence:de_bruijn_sequence_on_a_chess_board
Table of Contents
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
chess/programming/de_bruijn_sequence/de_bruijn_sequence_on_a_chess_board.txt · Last modified: 2021/10/28 15:54 by peter