{"id":1250,"date":"2014-01-18T01:04:09","date_gmt":"2014-01-18T01:04:09","guid":{"rendered":"http:\/\/graham-kendall.com\/blog\/?p=1250"},"modified":"2020-09-22T01:58:22","modified_gmt":"2020-09-22T01:58:22","slug":"knights-tours","status":"publish","type":"post","link":"https:\/\/graham-kendall.com\/blog\/knights-tours\/","title":{"rendered":"Knight’s Tour"},"content":{"rendered":"
\"Knight's<\/a>
Knight’s Tour (screen shot from Numberphile video)<\/figcaption><\/figure>\n

If you are interested in Chess, you may have come across Knight’s Tour problem before.<\/p>\n

Your task is to take a knight and place it anywhere on the chess board. Then, by performing legal Knight’s moves. can you visit each square on the chess board? Moreoever, you are only allowed to visit each square once (so 64 moves)?<\/p>\n

If you end up at the final square, and it would be possible to move to your starting square with a legal Knight’s move, this is know as a close tour<\/em>. Mathematicians would also recognise this as a Hamiltonian Path<\/a>.<\/p>\n

If you end up on a square where it is not possible to get to your starting position (via a legal Knight’s move) this is know as an open tour.<\/p>\n

When you first see this problem, you tend to think that it would be impossible to find any tour, whether open or closed.<\/p>\n

You might be surprised to learn that there are 26,534,728,821,064 closed tours. Yes, that’s right, 26 TRILLION of these tours. So if you tried it and could not find one, then shame on you :-).<\/p>\n

How many open tours do you think there are? At the time of writing, nobody knows!<\/p>\n

The video below does the job of exaplaining Knight’s Tours much better than I can, and it also includes some extra information about semi-magical squares.<\/p>\n

I have a particular interest in this video and I had some discussions with Brady Haran (the producer of this series) as I have published a couple of papers on this topic (see here<\/a> and here<\/a>) , where we used ants<\/em> to find Knight’s tours.<\/p>\n