Wikipedia:Reference desk/Archives/Mathematics/2020 March 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

March 2

King's Tours

Hi!!

I wonder if anyone has ever looked into the question of how many unique King's Tours exist for a chess board of a given size.

For example, on a boring 1x1 board there is one tour, on a 2x2 there are (if I'm not mistaken) 3. Is there some mathematical way to calculate this or can it be brute-forced on a computer?

Duomillia (talk) 02:22, 2 March 2020 (UTC)

There are some sequences in the Online Encyclopedia of Integer Sequences that relate to it. Bubba73 ^{You talkin' to me?} 02:56, 2 March 2020 (UTC)

If you say 3 for 2x2 then you must require a cycle and not distinguish between directions. This is OEIS:A140519. PrimeHunter (talk) 03:01, 2 March 2020 (UTC)

Y'all're a bit too quick for me. The paper linked in the above sequence at the OEIS describes an algorithm for enumerating, but a computer is still required. For the king's graph, they seem to have increased the known results from 8x8 up to 16x16. –Deacon Vorbis (carbon • videos) 03:09, 2 March 2020 (UTC)

If a formula or recurrence relation suitable for paper-and-pencil computation was known, it would have been mentioned at the OEIS entry. No formulas are known for the number of knight's tours, rook's tours or queen's tours either. (By the latter I do not mean concert tours of Queen.)  --Lambiam 06:51, 2 March 2020 (UTC)

If it doesn't have to be a cycle, it's a self-avoiding walk, and computing the number of those is (according to the article) believed to be NP-hard (i.e. difficult). 2602:24A:DE47:B270:A096:24F4:F986:C62A (talk) 03:30, 3 March 2020 (UTC)

Computing the number of Hamiltonian paths is NP-hard for general graphs, but may be easy for a restricted class of graphs. For example, it is easy on cycle graphs, dipole graphs and cliques. We do not know whether it is hard on any of these particularly restricted classes of chess-move graphs.  --Lambiam 10:47, 3 March 2020 (UTC)

Yes, the NP-hardness of counting self-avoiding walks (SAW) is stated as a conjecture. There is a big literature about SAW though, and not much about them is easy. Especially in the higher dimensional case it wouldn't surprise me if it's way up there in complexity, maybe even PSPACE-complete. Is anything known about that? 2602:24A:DE47:B270:A096:24F4:F986:C62A (talk) 17:13, 3 March 2020 (UTC)

The number of self-avoiding walks on the clique C_n equals $\sum _{k=0}^{n}{\frac {n!}{k!}}$ (sequence A000522 in the OEIS), which grows like $\Theta ((n/e)^{n+{\frac {1}{2}}})$ but is easy to compute.  --Lambiam 22:52, 3 March 2020 (UTC)