Long before the advent of software, computers, or even electricity, Wolfgang von Kempelen debuted one of the world’s most spectacular technological marvels ever invented, even by today’s standards. Inspired by the then-famous illusionist François Pelletier, Kempelen wanted to build something so incredible that it would top Pelletier’s – and all others’ – illusions, and that he did. The year was 1770 and the machine was a chess-playing automaton known as The Turk.

The brains behind The Turk were springs, spindles, cogs, and gears, and they were all powered by a few turns of a large key. Some of the clockwork computed the moves while others controlled the automaton’s arm. Yes, there was actually a human-like (Turkish, in fact) torso attached to the cabinet that would physically move the chess pieces.

For nearly 90 years, The Turk garnered fame from across the world and fascinated historical icons such as Napoleon Bonaparte and Edgar Allan Poe. Even Benjamin Franklin became enamored with the contraption, especially after losing a game of chess to it in 1783.

Of course, today we all know the truth behind The Turk: there was an experienced chess player inside the machine, moving levers by candlelight. But what you may not know is that, among other things, The Turk was “programmed” to solve a classic (even in those days) chess puzzle known as the Knight’s Tour.

The Knight’s Tour is fairly simple.

  1. Start with an empty chessboard square (6x6 or larger)
  2. Place a knight piece at some random location on the board
  3. Following the rules of chess, move the knight such that:
    • Each square is visited exactly once
    • The starting square is the last square visited

To illustrate, a Knight's Tour involves the following:

However note that, in the above animation, the board is only 5x5 and the knight does not return to where he started.

Your praxis: develop a function that solves the Knight's Tour. There should be two inputs (board size, starting position) and one output (a series moves to take).

Got a tip for a future Programming Praxis? Please send it on in!