The Knight’s Tour is a sequence of chess moves by a knight on a chessboard such that the piece visits every square only once. How hard could it be?
Here’s one possible path that I worked out starting at e1.
e1, g2, h4, f3, e5, g6, h8, f7, d8, b7, a5, c6, d4, b3, a1, c2, b4, a2, c1, d3, c5, a6, b8, d7, f8, h7, g5, e6, f4, h3, g1, e2, g3, h1, f2, e4, c3, d1, b2, a4, b6, a8, c7, b5, a7, c8, d6, e8, f6, g8, e7, d5, e3, c4, a3, b1, d2, f1, h2, g4, h6, f5, g7, h5
The trick is (as far as I can tell) you’ve got to move in a pattern such that at the halfway point your board looks like this:
There might be other ways to complete the tour, but regardless, if you can get sets of two in the block pattern similar to the image above then the rest is just as easy as getting here in the first place. Also, notice that only two corners have been filled at this point, A1 and G8 while at the same time in the centre four squares D4 and E5 are filled while D5 and E4 are not yet taken. The other general idea is to choose the move that has the least options to move to next (beware there are exceptions).
The knight is randomly placed at the outset but this pattern is buildable from any of the start positions I’ve worked on. Give it a try: The Knight’s Tour. The source code is at github if you’d like to build your own — created by Reddit user psrwo.
(via BoingBoing)
