login
The profiles of the backtrack tree for the n queens problem, triangle read by rows.
6

%I #27 Mar 31 2024 12:04:57

%S 1,1,1,1,2,0,1,3,2,0,1,4,6,4,2,1,5,12,14,12,10,1,6,20,36,46,40,4,1,7,

%T 30,76,140,164,94,40,1,8,42,140,344,568,550,312,92,1,9,56,234,732,

%U 1614,2292,2038,1066,352,1,10,72,364,1400,3916,7552,9632,7828,4040,724,1,11,90,536,2468,8492,21362,37248,44148,34774,15116,2680

%N The profiles of the backtrack tree for the n queens problem, triangle read by rows.

%C The profile (p_0, p_1, ..., p_n) is the number of nodes at each level of the tree.

%D D. E. Knuth, The Art of Computer Programming, Volume 4, Pre-fascicle 5B, Introduction to Backtracking, 7.2.2. Backtrack programming. 2018.

%H Peter Luschny, <a href="/A319284/b319284.txt">Rows n = 0..19, flattened</a>

%H Candida Bowtell and Peter Keevash, <a href="https://arxiv.org/abs/2109.08083">The n-queens problem</a>, arXiv:2109.08083 [math.CO] 2021.

%H V. Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Ways of placing non-attacking queens and kings...</a>, part of "Between chessboard and computer", 1996, pp. 204 - 206.

%H Peter Luschny, <a href="/A319284/a319284.jl.txt">Julia implementation of the n queens problem with profiles</a>

%H Michael Simkin, <a href="https://arxiv.org/abs/2107.13460">The number of n-queens configurations</a>, arXiv:2107.13460 [math.CO] 2021.

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Backtracking">Backtracking</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Eight_queens_puzzle">Eight queens puzzle</a>

%e [1]

%e [1, 1]

%e [1, 2, 0]

%e [1, 3, 2, 0]

%e [1, 4, 6, 4, 2]

%e [1, 5, 12, 14, 12, 10]

%e [1, 6, 20, 36, 46, 40, 4]

%e [1, 7, 30, 76, 140, 164, 94, 40]

%e [1, 8, 42, 140, 344, 568, 550, 312, 92]

%e [1, 9, 56, 234, 732, 1614, 2292, 2038, 1066, 352]

%e [1, 10, 72, 364, 1400, 3916, 7552, 9632, 7828, 4040, 724]

%e [1, 11, 90, 536, 2468, 8492, 21362, 37248, 44148, 34774, 15116, 2680]

%e [1, 12, 110, 756, 4080, 16852, 52856, 120104, 195270, 222720, 160964, 68264, 14200]

%o (Julia) # See the link section.

%Y Cf. A000170 (T(n,n)), A319283 (row sums), A319288 (indices of the row maxima).

%Y Cf. A000012 (col. 0), A000027 (col. 1), A002378 (col. 2), A061989 and A079908 (col. 3), A061990 (col. 4), A061991 (col. 5), A061992 (col. 6), A061993 (col. 7), A172449 (col. 8).

%K nonn,tabl

%O 0,5

%A _Peter Luschny_, Sep 16 2018