Computer Chess Club Archives


Search

Terms

Messages

Subject: De Bruijn Graph on a Chess Board

Author: Gerd Isenberg

Date: 13:18:51 06/20/04


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  a1
\/\/\/\/\/\/\/\/\/\/||\/\/\/\/\/ \/\/\/\/\/\/\/\/\/\/\/\/\/\/  \/

All nodes except b1,g8 and h8 occur twice due to "topology" reasons ;-)
\/ are vertices to the duplicated tree.

2**26 different ways (Euler Cycles) to traverse all 64 squares!
Takes 57 seconds now!

With my board mapping the direct cycle is between f3 and c6.

Cheers,
Gerd



This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.