In my bit manipulation post awhile back I posed a problem involving "closed form" calculation of chess endgame table indices. Back when I originally solved the problem, it was a big help to create some visualizations of some of the patterns embedded in the square numbering scheme. I had mentioned that I thought the patterns were interesting, so I thought I'd come back and elaborate on that statement.
One way of visualizing some of the patterns involved is to partition the squares according to the equivalence classes defined by the binary bits of the index. Bits 0-2 are the three low-order bits and bits 3-5 are the three high-order bits. Here are the equivalence classes defined by each of the bits of the natural square numbering.
Bit 0
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Bit 3
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Bit 1
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Bit 4
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Bit 2
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Bit 5
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Here we can clearly see the natural row and column oriented behavior of the index. Nothing earth shattering. If we take octal digits instead of binary digits to define our equivalence class, we get the following more colorful partition.
Low Digit
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
High Digit
70 | 71 | 72 | 73 | 74 | 75 | 76 | 77 |
60 | 61 | 62 | 63 | 64 | 65 | 66 | 67 |
50 | 51 | 52 | 53 | 54 | 55 | 56 | 57 |
40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 |
30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 |
20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 |
10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
00 | 01 | 02 | 03 | 04 | 05 | 06 | 07 |
Now on to the interesting stuff. Here are the same six equivalence classes of the less obvious square numbering for which I posed my puzzle.
Bit 0
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
Bit 3
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
Bit 1
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
Bit 4
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
Bit 2
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
Bit 5
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
And for the octal digits...
Low Digit
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
High Digit
64 | 04 | 14 | 24 | 26 | 16 | 06 | 66 |
05 | 65 | 34 | 44 | 46 | 36 | 67 | 07 |
15 | 35 | 74 | 54 | 56 | 76 | 37 | 17 |
25 | 45 | 55 | 75 | 77 | 57 | 47 | 27 |
21 | 41 | 51 | 71 | 73 | 53 | 43 | 23 |
11 | 31 | 70 | 50 | 52 | 72 | 33 | 13 |
01 | 61 | 30 | 40 | 42 | 32 | 63 | 03 |
60 | 00 | 10 | 20 | 22 | 12 | 02 | 62 |
Ahhhhhh....I don't know about you, but I think that's a beautiful square numbering. There's also plenty of group theory going on. What do you see here?
The Haskell code used to generate these tables is here.
Comments