[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