Knight’s Tour

Aim for the loneliest square

Left to instinct, most people fill the middle of the board and then get stranded, with unreachable squares marooned in the corners. The fix is a piece of advice from 1823 known as Warnsdorff's rule: on each move, go to the square that has the fewest onward moves of its own. It sounds backwards (why walk into a dead-end corner?), but that's the point. Corner and edge squares are hard to reach, because a knight only touches them from a couple of angles, so you visit them while you still can and leave the well-connected central squares for later, when you'll have plenty of options.

Reading the board like a knight

A knight moves in an L: two squares one way, one square the other. From the dead center of the board it can reach eight squares; from a corner, only two. That lopsidedness is the whole challenge. One more piece of board sense: every hop lands on the opposite color from the one you stood on, dark to light to dark, for the entire tour. Two squares of the same color can never follow one another, which is why a broken tour so often dies with two stranded squares of matching color: no single hop will ever join them.

• Count the exits from each highlighted option before you hop, and take the most cornered one: the square with the smallest count.
• Treat the four corners as appointments you have to keep early; a corner reached late is often a corner reached never.
• If two moves tie for fewest exits, glance one step further ahead to see which keeps more of the board reachable.

Watch the rule work from move one. Start the knight in a corner and it has exactly two choices. Count each option's own exits, take the smaller number, and hug the rim. For the first dozen hops Warnsdorff's rule will walk you around the edge of the board like a beat cop doing rounds, clearing the awkward squares while the centre stays warm. Only then does the path spiral inward. If you find yourself deep in the middle within your first ten moves, something has gone wrong, and the corners will collect the debt near the end.

Run out of legal hops before all 64 squares are marked and the round ends. Your score is the most squares you've ever covered, so even a broken tour nudges your record toward a full one.

A puzzle with a thousand years of mileage

The Knight's Tour is far older than it looks. Arabic chess writers were building tours in the ninth century, among them al-Adli, a celebrated Baghdad master who wrote one of the first great chess books. Around the year 900 the Kashmiri poet Rudrata worked a knight's path into the syllables of a Sanskrit verse, half a board covered inside a poem. The problem's modern life began when Leonhard Euler gave it the first real mathematical treatment in a 1759 paper, showing how to construct tours and stitch half-tours together. Warnsdorff's fewest-exits rule followed in 1823 and is still the best advice ever handed to a human solver. The tour even had a stage career: the Belgian-American master George Koltanowski performed it blindfolded as a showpiece for decades, hopping a knight around a board whose squares the audience had just called out to him.

Numbers that show the size of it

A closed tour, remember, is one that ends a single knight's move from its starting square, so the route could loop around forever. Counting each direction of travel, there are more than 26 trillion of them on the standard board, and open tours outnumber those massively. The squares were never the problem; picking one path out of that haystack is. There are stranger prizes in the haystack too. In 1848 William Beverley built a tour whose numbers, written into the squares in visiting order, add up to 260 along every row and every column, a semi-magic square drawn by a hopping knight. Whether a tour could manage the full magic square, diagonals included, stayed open until 2003, when a computer search checked every possibility and found none. None of this trivia helps you hop, but it explains the itch. The board is small, the move is simple, and the structure underneath is bottomless. Take Warnsdorff's advice, keep your corner appointments early, and one of those trillions of tours will be yours.