back to
Stefan's HomePage
|
The knight moves over the chess board in the way that is displayed on the left. If the knight happens to be on the field marked with an S, he can access any of the X-fields in the next step. |
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.
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...)
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...
The problem of finding a single solution for the
Knight's Tour was
solved
in the early 1990s by a group of students as a project for the
german scientific contest "Jugend forscht". Their algorithm finds
a single solution on a chess board of any size (>=5x5) within an
almost unmeasurably short period of time.
The basic idea is quite simply generic recursion. They cut the
big boards into very small ones
(5x5, 6x6, 6x7, 6x8, 7x7, 7x8, 8x8), for which a solution can
easily be found, and then reconnected the small boards to fill
the bigger (and really big) boards.
That way they only had to find solutions for small boards that
match certain criteria, like a given starting and ending position
(easy enough) that allowed the knight to move from the end
position on one board to the starting point of the next one.
Using this algorithm, they could prove that any board bigger
than or equal to 5x5 has at least one solution, as all boards
with longer sides can be split into boards with the sizes
mentioned above (length N = a*6+b*7+c*8 for all N>17, N<=17 works
anyway).
Now some of those solutions can be found in no-time.
Normally there are quite a few to be found, so it's not that
hard to find at least one.
Since this algorithm can be used for parallel computation, it is impossible (and unneccessary, BTW) to find a faster one.
A variation of this problem makes the knight return to the
starting point on the board. It's not really more afford to find
a special solution like that since it only constraints the
algorithm to end up on one of a certain number of fields, which
is always possible if the knight actually can end up on
those fields.
The exceptions are given by the following idea:
A 5x5 board has 25 fields. On each move, the color of the field
the knight is standing on changes because of his way of moving.
So if the first field was white, the second one will be black
and so will be every field the knight accesses with an even number.
Therefore the 25th field, the last one he moves on, will be white
again.
On this board, the first position and the last one always have
the same color, so there is no way for the knight to move from
the last one directly back to the starting position.
Therefore re-entrant paths (real cycles) are only possible on
boards with an even number of fields.
All boards (>5x5) with an even number of fields provide at least one solution for a cycle. Boards of sizes 3xN or 4xN may vary.
Well, I didn't like all those at leasts when I wrote this
text, since it means that we do not actually know the exact
number of solutions that can be found for a given board.
Now we are coming to the biggest problem of this little family:
We are trying to count the number of paths the knight can move
along in order to access every field of the board exactly one
time. This really involves finding all solutions and stupidly
counting them. To get an idea of the size of the problem, you
may take a look at the following table, that gives the number
of directed paths on different squared chess boards.
| Boardsize | Solutions | Number of valid board configurations | Max. number of board configurations |
|---|---|---|---|
| 4x4 | 0 | 29976 | 2.69*10^7 |
| 5x5 | 1728 | 38010697 | 7.13*10^13 |
| 6x6 | 6637920 | ? | 1.3*10^17 |
| 7x7 | ? | ? | 1.1*10^26 |
| 8x8 | 8,121,130,233,753,702,400 by (Löbbing,Wegener 1996) | ? | 4.5*10^36 |
The maximal number of field configurations given above allows
to estimate the size of the problem since those have to be
tested in order to find all solutions.
This number is nevertheless much bigger than the number of
allowed paths since the knight normally runs into dead ends
long before he can actually finish his journey across the board.
The number is easily calculated since we can count the number
of accessible fields for each position on the board and
multiply them.
This results in the maximal number of paths that may allow the
knight to access all fields, but still includes everything that
whould lead to a dead end situation.
An example: The knight starts in the top-left corner of the
chess board. From that position he can access two other fields,
making it two possible paths. Selecting one of them the knight
now can access five new fields and so on. To find the maximal
number of paths we can now multply the number of accessible
fields on all his ways: 2 * 5 * ...
Since the knight always has to access each field once, this is
just the same as if we multiplied the number of successors for
each field on the board. We may argue that we have to decrease
all factors (but the first one) by 1 since the knight always
comes from one of those fields, so there's always at least one
less accessible, but since we search the solutions beginning
on any of the fields on the board, any of them can be the first
one. So we really end up multiplying all counters.
Examples for 5x5 and 6x6 are given below.
|
|
Some test calculations show an average depth for backtracking
at about two third of the way (60-70%) if no optimizations are
used. This leads to the following calculation:
The maximal branching factor of the problem (i.e. the maximal
number of successors that have to be tested in the next
iteration) is seven, since one field has at most eight successors
one of which the Knight previously came from.
As it can be seen from the boards above, if the board grows, the
middle part will fill with a successor count of eight while the
two rows and columns on both sides stay basically the same.
Since the middle part is a square, it will grow much faster than
the borders that grow linearly, so for big boards, a branching
factor of 7 will be a good assumption.
That's why counting the Knight's Tours becomes such a big
problem even if the board is only slightly growing.
Now we see that there are (NxN) valid configurations in the
first iteration, not more than (NxN)*7 in the second, then
(NxN)*7*7 and so on.
That makes it (NxN)*7^(N*N-1) in the last iteration.
The resulting exponential function is
c(i) = (N*N) * 7^(i-1).
We see that most of the possible configurations reside at the
end of the paths, because of the high branching factor, and so
we can integrate the function to see how many of them do.
The integral of the function c is given by
I(i) = (N*N)/ln(7) * 7^(i-1).
We already said that after about two third of the path the
knight has to turn back and do backtracking.
For generalisation purposes I will name this ratio
r in the following text.
So now we take the integral of that part to have an
approximation for the valid board configurations:
Ptried
= I(r*N*N) - I(1)
= (N*N)/ln(7) * (7^(r*N*N-1) - 1)
and the integral of the part that represents the invalid
configurations since the knight had to return earlier on:
Pbacktracked
= I(N*N) - I(r*N*N)
= (N*N)/ln(7) * (7^(N*N-1) - 7^(r*N*N-1))
We now can calculate the relation between the two:
Ptried / Pbacktracked
= (7^(r*N*N-1) - 1) / (7^(N*N-1) - 7^(r*N*N-1))
~ 7^(r*N*N-1) / (7^(N*N-1) - 7^(r*N*N-1))
This is a constant for a given board. It gives us an
approximate relation between the maximum number of board
configurations and the number of valid ones and allows
us to estimate the size of the problem more exactly.
So now here is a new table which gives the new approximation
of the above mentioned boards.
| Boardsize | Solutions | Number of valid board configurations | New estimate between | Max. number of board configurations |
|---|---|---|---|---|
| 4x4 | 0 | 29976 (=3.00*10^4) | 2.34*10^3 | 2.69*10^7 |
| 5x5 | 1728 | 38010697 (=3.80*10^7) | 1.49*10^7 | 7.13*10^13 |
| 6x6 | 6637920 | ? | 1.3*10^17 | |
| 7x7 | ? | ? | 1.1*10^26 | |
| 8x8 | 8,121,130,233,753,702,400 by (Löbbing,Wegener 1996) | ? | 4.5*10^36 |
I also wrote an essai about this estimate. The PDF file can be found here.
Since symmetry tends to decrease the number of field configurations that have to be tested by factors, it is usually one of the first ideas to implement. The following symmetries exist on any board:
| 1 | 1 | 3 | 1 | 1 |
| 1 | 1 | 3 | 1 | 1 |
| 2 | 2 | 4 | 2 | 2 |
| 1 | 1 | 3 | 1 | 1 |
| 1 | 1 | 3 | 1 | 1 |
Different areas with the same numbers are symmetric and therefore
provide the same number of solutions.
The areas marked with 2 only exist on boards with an odd
height, the areas 3 only on boards with odd width.
If both width and height are odd, area 4 has to be taken
into account, too.
On evenly sided boards there are only the areas marked with
1 one of which has to be tested.
On square boards, the areas 2 and 3 provide the
same number of solutions.
|
back to
Stefan's HomePage
|
|