Author: Gerd Isenberg
Date: 00:28:50 06/18/04
Go up one level in this thread
Hope my De Bruijn excurse becomes not too boring...
There are for sure other, smarter algorithms, traversing de Bruijn graphs, using
or recombine and concat so called Lyndon words.
Anyway, with the help of the unique sub-sequence 31->63->62 only the half nodes
are needed now. Incremental updating the unique index of the last six-bit
sequence also helped to reduce the time to count all 2**26 64-bit De Bruijn
sequences under 90 seconds on my Athlon Xp2.8 now:
// time 82.618 sec
// Nodes 4344789619
// Locked Nodes 2023130156
// Open Nodes 2321659463
// De Bruins 67108864
// nps 52588262
// De Bruin ps 812269
Since de Bruijn sequences are cyclic (with wrap around), i consider shifted 5
leading zero sequences not as "different" to the generated 6 leading zero
sequences, even if they are fine as disjoint bitScan-multiplier too.
Gerd
void findDeBruijn(BitBoard seq, int depth, int unique)
{
++m_Nodes;
if ( (m_Lock & pow2[unique]) == 0 && unique != 32)
{
++m_NlNodes;
if ( depth == 0 )
{
if ( ++m_dBCount == m_Match4nth )
bitScanRoutineFound(seq);
}
else
{
m_Lock ^= pow2[unique];
if ( depth > 2 && unique == 31 )
{
findDeBruijn(seq | pow2[depth-1], depth-2, 62);
}
else
{
if ( depth > 1 )
findDeBruijn(seq, depth-1, (unique*2)&63);
findDeBruijn(seq | pow2[depth-1], depth-1, (unique*2+1)&63);
}
m_Lock ^= pow2[unique];
}
}
}
initial call:
start = clock();
try {findDeBruijn(0, 64-6, 0);} catch(int){}
stop = clock();
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.