[seqfan] Is there a constant hidden in the backtrack trees of the n queens problem?
Peter Luschny
peter.luschny at gmail.com
Sat Sep 29 15:36:34 CEST 2018
Consider the profile P(n) of the backtrack tree of the
n queens problem. Let I(n) denote the index of the maximum
of P(n) and consider I(n)/n. Does I(n)/n converge?
In terms of A319288 the question is
A319288(n) / n -> C for n -> oo ?
[..., 0.600, 0.667, 0.714, 0.625, 0.667, 0.700, 0.727, 0.750,
0.769, 0.786, 0.733, 0.750, 0.765, 0.778, 0.789, ...]
I believe that such a constant exists (and has a value
between 0.7 and 0.8), but have no idea how to prove this.
I even believe that there is a whole class of combinatorial
search problems that are characterized by the fact that their
backtrack trees have such a constant.
Every comment, also if it is as speculative as the question,
is welcome.
Cheers, Peter
More information about the SeqFan
mailing list