[seqfan] Re: Is there a constant hidden in the backtrack trees of the n queens problem?

[Simon Plouffe]

Hello, I would guess Pi/4 but that number is not
the one we should see there I think,

Best regards,
 Simon Plouffe


Le sam. 29 sept. 2018 à 15:37, Peter Luschny <peter.luschny at gmail.com> a
écrit :

> 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
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>