Problems for the chess knight ...

Problems for the chess knight ...

Trouble for the knight

The idea of looking at a single the chess knight on the board goes all the way back to the 18th century, when Leonhard Euler, a swiss matematician, introduced a problem in Berlin, 1758. The problem, that is usually referred to as Springerproblem or The Knight's Tour, is given by

Starting with an empty chess board, is there a path that has a knight visit all the fields (black and white) of the board exactly one time?

The knight is paticularly interesting because of his strange way of moving. It would be much less interesting to try that with the queen, for example, since most attempts should lead to a solution. The knight in turn has a very limited way of moving that keeps the number of accessible fields per move below eight.

When Euler first thought of that problem, he imagined an 8x8 board, the regular chess board, while today's mathematical and computerized methods make us want to take a look at bigger boards, too.
But in order to find out about the chances of solving the problem, we have to take a closer look at it first.

Different flavours...

During the last almost 250 years, different ways of looking at the problem have evolved. It is remarkable, that even the smallest one among them took about 230 years to be sufficiently solved in a way that is scalable even for huge boards.
The problem of the Knight's Tours is often used as an example in graph theory, since it is easy to imagine and to try out but nevertheless a very big problem with many different flavours to emphasize on. It can be used to show the idea of symmetry, of directed and indirected tours/graphs and of paths and closed tours. Though it is a Hamiltonian problem, solutions can easily be found.
Since it was proven to have solutions for all boards >= 5x5 in the early 1990s, it has now become even more popular and commenly known and there were several attempts and applications in this field that reach from simple Java-Applets for demonstration and visualisation purposes up to parallel computation and neural networks (why ever...)

All under a general headline

The Knight's Tour represents a special case of one of the biggest problems in computer science: The Hamilton Cycle.
R.W. Hamilton was an irish (cheerz!) mathematician of the 19th century. The problem of the Hamilton Cycle describes the search for a path in a graph to connect all knodes so that they build a cycle, similar to "connect the dots" (Malen-nach-Zahlen) adding the slight difficulty that the numbers are missing and you have to find the right order yourself - and usually there are quite a few dots to connect... The Hamilton Cycles belong to the class of NP-complete problems and are therefore believed to be only solvable with an afford that grows exponentially with the size of the problem.

To find a Knight's Tour is by far more simple since the limitation to a chess board provides some benefits like indirectness, symmetry and (here we go:) recursion. In fact, finding a Knight's Tour is so "easy" that todays home computers do this for giant boards with some billions of fields in an almost unmeasurably short period of time. You can just wait for it...

Read full article from Problems for the chess knight ...