{"id":1376,"date":"2016-10-08T13:39:58","date_gmt":"2016-10-08T18:39:58","guid":{"rendered":"http:\/\/www.laurentlessard.com\/bookproofs\/?p=1376"},"modified":"2018-10-29T01:35:40","modified_gmt":"2018-10-29T06:35:40","slug":"non-intersecting-chessboard-paths","status":"publish","type":"post","link":"https:\/\/laurentlessard.com\/bookproofs\/non-intersecting-chessboard-paths\/","title":{"rendered":"Non-intersecting chessboard paths"},"content":{"rendered":"

This Riddler classic puzzle<\/a> is about finding non-intersecting paths on a chessboard:<\/p>\n

\nFirst, how long is the longest path a knight can travel on a standard 8-by-8 board without letting the path intersect itself?<\/p>\n

Second, there are unorthodox chess pieces that don\u2019t exist in the standard game, which are known as fairy chess pieces. What are the longest nonintersecting paths that can be taken by the camel (which moves like a knight, except 3 squares by 1 square), the zebra (3 by 2), and the giraffe (4 by 1)?\n<\/p><\/blockquote>\n

This is a very challenging problem, and there doesn’t appear to be any way to solve it via some clever observation or simplification. Of course, we can try to come up with ever longer tours by hand, but we’ll never know for sure that we have found the longest one.<\/p>\n

Much like the recent Pokemon Go problem<\/a>, we must resort to computational means to obtain a solution. In this case, however, the problem is “small enough” that we can find exact solutions!<\/p>\n

Here are some optimal tours:
\n[Show Solution]<\/a><\/p>\n

\n

Here are optimal-length knight paths computed for various board sizes:
\n\"nonintersecting_knight_paths\"<\/a>
\nOf course, we aren’t restricted to square boards. It’s just as easy to compute for example a max-length knight path on a 12×4 board:
\n\"nonintersecting_rect_path\"<\/a>
\nFor the alternate chess pieces mentioned in the problem statement, the code only requires slight modifications; i.e. there are more ways for paths to cross when a giraffe moves vs when a knight moves. But otherwise, the structure of the optimization problem is identical. Here are some optimal-length paths for the four different pieces:
\n\"nonintersecting_fairy_paths\"<\/a>
\nFor the camel path, we can take advantage of the fact that the camel always remains on squares of the same color, so we are effectively solving the problem on a board with half as many squares! As we can see, there are no patterns in the solutions; this is truly a difficult problem and without powerful computational tools, we would be hard pressed to find these solutions by hand. In the next section, I go into detail about how I solved the problem and I also include my code if you’re interested in solving it yourself!\n<\/div>\n

If you’re interested in the details of how I found my solutions, read on:
\n[Show Solution]<\/a><\/p>\n

\n

Even though we’re resorting to a numerical solution, we must still be careful about how we proceed. There is an astronomical number of possible paths on a chessboard, so simply enumerating and checking each path is out of the question! Instead, we’ll think about the problem as a visiting nodes on a graph. Here, each node is a cell and edges connect pairs of cells between which a knight can move.<\/p>\n

Let’s define the following matrices:<\/p>\n