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

[Brad Klee]

Hi Peter,

Repeats occur at index a'(m)=3,8,15..., which is fit by quadratic function
a'(m)=m^2-1.

A hypothesis would be: a(1)=0, a(n) = a(n-1) + 1 unless n = a'(m) for some
m,
in these cases do not increment, a(n)=a(n-1). As increments happen with
only
quadratic frequency, asymptotically it should be that a(n)/n ~ 1.

If increments happen with a linear period, then we can force convergence to
a number
less than one. Example: a(1)=0, a(n) = a(n-1) + 1 unless 5 divides n, then
a(n)=a(n-1).
The sequence of first differences is periodic with T=5, and a(n)/n ~ 4/5.

This is naive analysis, and it would really be better to argue from the
particulars of
the problem. Nevertheless, if every first difference is drawn from {0,1} or
even from
a finite set, and if the sequence of first differences is periodic on
average, then
maybe it will be possible to prove convergence.

How do you rule out the scenario of quadratic lapses? What do your beliefs
say in
general about the first differences? Do you know of any trivial examples
where the first
differences satisfy a linear recurrence? Any answers would help your case.

Cheers,

Brad




On Sat, Sep 29, 2018 at 8:37 AM Peter Luschny <peter.luschny at gmail.com>
wrote:

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