Its Xmas and Xmas means  Donald Knuth putting on his flamboyant Xmas top and talking to us about something that most of us know nothing about? Of course not. This year it's all about the Knight's Tour which is more interesting than anything a salesman could get up to.

The knight is perhaps the strangest of all chess peices as it moves in an L shape - two squares vertical or horizontal and then one at 90 degrees. We all know that the L shape in Tetris is particularly fun and there are lots of puzzles based on having to fit L shapes together. The Knights Tour is a classic of this type of puzzle and it is a sort of travelling salesman problem, but where the salesman is a knight. The problem is to find out whether the knight can visit every square on a chessboard exactly once and get back to its starting square, a closed tour, or not, in whcih case it is an open tour. 

Variations of the Knight's Tour are a fairly solved problem and they provide some interesting geometric patterns. So much so that Knuth suggested they be used to decorate his new computer science building. This is covered at the start of the talk and then he goes on to describe the history of the problem and makes a connection with Celtic knots.

The real questions about the Knight'sTour relates to how many of them there are. Some of these questions are long-standing, but with the help of a computer the solutions can be found. For example, every closed Knight's Tour has to have at least four turns at more than 90 degrees, but there is only one tour that achieves this lower bound. 

This talk reveals not only some details of the knights tour, but the fact that Knuth actually uses computers to solve problems! 

If you go to the discussion at the end there is a bonus where Knuth is asked about his Xmas jumper - and its story is almost as interesting. 

I cannot pretend that the content of Knuth's lecture this year is easy to follow, but it is a rare glimpse into how such problems are tackled and how research is done. 

• Mike James is the author of The Programmer’s Guide To Theory which sets out to present the fundamental ideas of computer science in an informal, and yet informative, way and The Trick Of The Mind: Programming and Computational Thought, aimed at programmers and non-programmers alike, which examines the nature of programming and reveals why it is a very special skill.

More Information

Donald E. Knuth Lectures

Related Articles

Knuth's Xmas Lecture 2024 - Strong And Weak

Donald Knuth's Christmas Lecture 2023

Yoda's (Donald Knuth) Xmas Lecture 2018

Knuth's 25th Christmas Lecture - Pi And The Art Of Computer Programming (2019)

No Donald Knuth Christmas Lecture This Year (2020)

Donald Knuth's Xmas Lecture Is Back (2022)

Donald Knuth's Christmas Tree Lecture 2017

Knuth's 22nd 360 Degree Not Christmas Tree Lecture

Knuth's 21st Not Christmas Tree Lecture 

Donald Knuth's Christmas Tree Lecture 

The Art Of Computer Programming - A Great Present.

Donald Knuth's Christmas Tree Lecture 

Donald Knuth and the Art of Programming     

To be informed about new articles on I Programmer, sign up for our weekly newsletter, subscribe to the RSS feed and follow us on Facebook or Linkedin.

Comments

Make a Comment or View Existing Comments Using Disqus

or email your comment to: comments@i-programmer.info

<ASIN: 0321751043>

<ASIN:0134397606>