Comment by randomwalker | Hacker News Reader

Comment by randomwalker | Hacker News Reader

Parent Full thread

I've always found Knuth's views curious. Is it just that he's from a different generation, or am I too much of an amateur to understand his wisdom? I don't know.

A couple of days ago he gave me a copy of his paper on Leaper graphs (On dead trees.. quaint :-) His office is a few doors from mine.) Along with a charming note about rewards for finding bugs. Anyway, Leaper graphs are the graphs that describe the moves of a generalized Knight on generalized chessboard. So I researched this some more, and found that Knuth was the first to enumerate all the Knight's tours that are invariant under 180° rotation.

At this point I'm thinking, this sounds like it could be an ICFP problem, and a language like Haskell would be ideally suited for it. Nope, turns out he wrote the program in his C variant. http://sunburn.stanford.edu/~knuth/programs/sham.w I'm amazed you can write that in C and have it turn out as short as it was. It also looks like it has goto's.

I really don't know what to take away from it.

The chessboard has rotational symmetry: if you turn it 180 degrees it is the same. Would not all tours be invariant under 180 degree rotation?

EDIT: Sorry, I understand now. If the knight's tour ends directly opposite it's starting position, it is invariant under 180 degree rotation.

This might help: http://www.mathpuzzle.com/leapers.htm

As you can see from those examples, a symmetric tour is a rather regular-looking object; a random tour has an extremely low probability of being symmetric.

Ah, thank you!

"I am more comfortable doing it with labels and goto statements than with while loops, but some day I may learn my lesson." (http://sunburn.stanford.edu/~knuth/programs/sham.w)

I take away from it that real programmers do not have an emotional attachment to one or other tool/ language. They are interested to solve a problem with maths and logic and the computer and his language are just the butler; a layer that has to be abstracted away.

Obviously Knuth thinks that books as a medium are still valid. (I am with him on this one.)

I have not read the book nor do I have any clue about Leaper graphs, but for some reason he thought it could help to research this. How can this research / knowledge help? Maybe it's just fun, I don't know.

Reply on news.ycombinator.com