A140521 Number of directed "king tours" on an n X n board.

1, 6, 32, 5660, 4924128, 45707720232, 3244086234829248, 1923484178952564643368

Offset: 1

Author

Don Knuth, Jul 26 2008

Keywords

• nonn
• walk

Comments

Or, number of directed Hamiltonian cycles in the graph P_n X P_n.

If the direction of the tour is not taken into account, the numbers for n > 1 must be halved (see A140519).

Computed using ZDDs (ZDD = "reduced, order, zero-suppressed binary decision diagram").

References

• Donald E. Knuth, The Art of Computer Programming, Vol. 4, fascicle 1, section 7.1.4, p. 117, Addison-Wesley, 2009.

Links

• Eric Weisstein's World of Mathematics, Hamiltonian Cycle
• Eric Weisstein's World of Mathematics, King Graph
• Index entries for sequences related to graphs, Hamiltonian

Crossrefs

Cf. A001230, A140519.