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

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, 30, 76, 140, 164, 94, 40, 1, 8, 42, 140, 344, 568, 550, 312, 92, 1, 9, 56, 234, 732, 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

Offset: 0

Author

Peter Luschny, Sep 16 2018

Keywords

• nonn
• tabl

Comments

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

Examples

			[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,  30,  76,  140,   164,    94,     40]
[1,  8,  42, 140,  344,   568,   550,    312,     92]
[1,  9,  56, 234,  732,  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]
[1, 12, 110, 756, 4080, 16852, 52856, 120104, 195270, 222720, 160964, 68264, 14200]
		

References

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

Links

• Peter Luschny, Rows n = 0..19, flattened
• Candida Bowtell and Peter Keevash, The n-queens problem, arXiv:2109.08083 [math.CO] 2021.
• V. Kotesovec, Ways of placing non-attacking queens and kings..., part of "Between chessboard and computer", 1996, pp. 204 - 206.
• Peter Luschny, Julia implementation of the n queens problem with profiles
• Michael Simkin, The number of n-queens configurations, arXiv:2107.13460 [math.CO] 2021.
• Wikipedia, Backtracking
• Wikipedia, Eight queens puzzle

Crossrefs

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

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).

Programs

Julia

# See the link section.