A319235 The profile of the backtrack tree for the eight queens problem.

1, 8, 42, 140, 344, 568, 550, 312, 92

Offset: 0

Author

Peter Luschny, Sep 15 2018

Keywords

• nonn
• fini
• full

Comments

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

The backtrack tree as defined by Knuth has for the eight queens problem 2057 nodes.

References

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

Links

• Wikipedia, Backtracking
• Wikipedia, Eight queens puzzle

Crossrefs

Cf. A000170, A319236.

Formula

a(8) = A000170(8), the number of solutions.