The whole job is done by the 3 methods. These methods use the global variables presented above. IsFree() detects the dead-end during the search,.testing that no vertices except the end-vertex are left, which have less than 2 free neighbors. FirstStep() go forth and NextStep() could go into another direction or go back.
At init
time, I build an array of 64 classes vertex[64]. At the beginning of the algorithm, each vertex knows all its neighbors.
The array of vertices can contain holes i.e indexes of table used in algorithm
could be not consecutive.
-
current
- the current number of the vertex on the
graph. This value is constant. The vertices are numbered from 0 to 63.
- origine
- the attribute "cuurent" of the previous vertex in the path.
Significant only if the vertex is busy (visited)
- index
- the move-number from the start. Start vertex has index = 1 and last vertex
in the path has index = 64. Significant only if the vertex is busy
- possibilitesTab[9]- contains every possible destinations of the vertex (free vertices
and busy vertices). This array contains const values because the graph doesn't
change during the time. This array is built at init time. The last value
is -1.
- FreePossibilitesTab[9]- contains only free destinations, currently not yet visited by the
knight. The last value is -1. FreePossibilitesTab[] is filled in IsFree()
- tentative - index in the table FreePossibilitesTab[9] for the current path. Significant only if the square is busy.
- bool
free - the vertex is not yet visited.
We can define
a solution as a list of 64 integers {x1,x2,
… x64}
1 ≤ i ≤ 64 and 0 ≤
xi ≤ 63 .
We have
the relationships with the attributes of object vertex[]
vertex[xi].current = xi
vertex[xi].index = i
vertex[xi].FreePossibilitesTab[tentative-1] = xi+1
vertex[xi].origine =
xi-1
These attributes
enable the navigation between vertices and are used by the algorithm to progress
in the search or to go back when there is no possibility.
For finding magic knight tour, some changes have been
inserted in these functions. IsFree()was modified. It uses the values of every
lines and columns on the chessboard. Depending on these values, it's possible
to cut the search tree (line or column are too large or too small). In addition,
some other variables have been created in order to improve the performance
of the algorithm. Also, the name of object has been changed from vertex to
caseNB_Optim.The following description concerns the modification in the algorithm
in order to find magic knight's tours
The methods used in the
loop
In the new
algorithm , only 4 methods are relevant (Isfree2() is added)
while (!Save2Do) {
y = caseNB_Optim[x].FirstStep();
IndexP1 = Index + 1;
if (caseNB_Optim[y].IsFree()) {
Src = x;
x = y;
Index += 1;
} else {
while (y = caseNB_Optim[x].NextStep())
{
if (caseNB_Optim[y].IsFree2())
{
Src = x;
x = y;
Index += 1;
break;
}
}
}
}
Before going on a square with FirstStep() method, I check that it is possible. IsFree() and IsFree2() are quite similar and do this work. At the beginning of the loop I suppose the start square is free. Having 2 distinct methods allows to avoid some test in IsFree and IsFree2. So the algorithm is faster.
IsFree is not the right term because the square is free (unvisited) when this method is called. The test made in this method is not “is this square free” ! Instead, 3 tests are made on the square under test.
1/ Is the current line and current column of this square not too small ?
2/ Are all lines and all columns not too large ?
3/ Is there a dead end ?
The order of these tests in the method could be changed for improving the algorithm. So far, no test has been made.
IsFree() and IsFree2() build the table FreePossibilitesTab[] from the table possibilitesTab[]. IsFree() can determine if the end of the path must be fixed or not. There is a global variable endIsDefined which stores this information. This information is computed from another information NBorigine[]. For a performance reason, NBorigine is not an attribute of a vertex but is stored in a separate table.
This table stores as long as the program run the number of possible origin for each square. In FirstStep(), I decrement NBorigine[x] by 1, for each x in possibilitesTab[]. NBorigine[] are incremented in NextStep, when the knight go back.
We can step on the square if IsFree() or IsFree2() return true. FirstStep() step on the square and return the first entry of FreePossibilitesTab[]. So tentative = 1 for the square.
If IsFree() or IsFree2() return false (the square is free, i.e. not yet visited because all squares tested by IsFree() or isFree2() come from FreePossibilitesTab[] so there are free! but one of the 3 conditions is false – too small/too large / dead end). I test the next square in the list FreePossibilitesTab[]. This square is given by NextStep(). NextStep() is recursive but recursive on different objects. It always return a valid square. At the end of the tab FreePossibilitesTab (test on -1) NextStep() uses the attribute origine and calls itself with the origin square.
To be able to check line and column values, the program maintains 2 global tabs not visible in the loop but only in methods. The first tab stores indication about lines and columns occupation (MagicLR[]) and the second one indication about lines and columns value (MagicLRVal[]). Before the step on the square, I do the following
//Row
MagicLR[row] |= Mask_line;
MagicLRVal[row] += IndexP1;
//Line
MagicLR[line]
|= Mask_row;
MagicLRVal[line] += IndexP1;
A improvement in the algorithm concern the way lines and column are managed. I take into account the disposition of the visited squares inside a line or a column using not the number of visited square but a mask that indicates the occupation's topology.
Every square in the chessboard has 2 constant attributes Mask_line and Mask_row. These attributes are just a bit, indicating the square’s position in the line or column. When the square is visited, the bit is “ored” in the right place in the tab.
With this trick, it’s possible to take into account the position of the visited squares in the line and column. Due to the knight movement, 2 Indexes in the same line (or column) cannot be consecutive. Depending on the line occupation, this constraint can be more important. For example, to consecutive squares in a line could not have an index difference less to 3. The following tab taxe[256] stores for all possible combinations of occupation, the value which must be add in comparison of a “standard +2” incrementation.
This tab was manually build.
nb8 taxe [256] = {
4,3,3,3,3,2,3,2,3,3,2,2,3,2,2,2,3,2,3,2,4,1,4,2,3,2,2,2,4,1,4,1, // 32
3,3,2,2,3,2,2,2,4,4,1,1,4,4,1,1,3,2,2,2,4,1,4,1,4,4,1,1,6,3,4,1, // 64
3,2,3,2,2,1,2,1,3,2,2,2,2,1,2,1,2,1,2,1,1,0,1,0,2,1,2,1,1,0,1,0, // 96
3,2,2,2,2,1,2,1,4,4,1,1,4,3,1,1,2,1,2,1,1,0,1,0,4,3,1,1,4,2,3,0, // 128
3,3,2,2,3,2,2,2,2,2,1,1,2,2,1,1,3,2,2,2,4,1,4,1,2,2,1,1,4,1,3,1, // 160
2,2,1,1,2,2,1,1,1,1,0,0,1,1,0,0,2,2,1,1,4,1,3,1,1,1,0,0,3,1,2,0, // 192
3,2,2,2,2,1,2,1,2,2,1,1,2,1,1,1,2,1,2,1,1,0,1,0,2,1,1,1,1,0,1,0, // 224
2,2,1,1,2,1,1,1,1,1,0,0,1,1,0,0,2,1,1,1,1,0,1,0,1,1,0,0,1,0,0,0}
; // 256
This tab is used for the checking of the minimum value and also for the checking of maximum value.
For the minimum value, the test is quite simple. One can easily predict than the line value will be too small. So I don't use the classical values
#define MAGIC 260
#define MAGIC_1 196 // 260 - 64
#define MAGIC_2 134 // 260 - 64 - 62
#define MAGIC_3 74 // 260 - 64 - 62 - 60
but some others depending on occupation's topology
For the maximum value, the test is more complicated. When the knight steps on a square, each line and each column could be checked in order to see whether the value 260 is achievable. The current value of each line and each column must not be too large.
Let line the mask of occupation of the line (or column) and occ[line] the number of busy squares of the line (or column).
Let I[line] (I[column]) the number of knight steps from current square
to the line (or column) to check
Let Index the envisaged index
of the current square, i.e. the square where the knight is going to step.
Val[line] is the current value of the
line to check
The minimum value which could be set on line or column is :
A Magic Knight Tour is possible only if
this value is less or equal to 260.
a magic knight tour cannot be realized
This tab Sigma8 is filled in the init with the following loop
for(i=0;i<5;i++) {
for(j=1;j<65;j++)
{
for(k=0;k<256;k++) {
occ = occupation(k);
Sigma8[i][j][k] = 260 - (8-occ)*(j+i+7-occ) - taxe[k];
}
}
}
Let see an example. In the presented context , the blue line is too large. This is detected in the algorithm. The current Index is 34 and the knight searches a good following square. First, the yellow square (with a question mark) is checked in IsFree()
- The value of line in blue is 12 + 23 + 14 = 49. Val[line] = 49
- This line is at 3 steps from square 4 (yellow square). I[line] = 3.
- The mask of the blue line is 200 (0xC8). For this mask taxe[line]
= 2 and as we can see it, occ[line] = 3
- Index = 35
So, we have at the right of inequality
260 - 2 - (8 - 3)*(3 + 35 + 7 -3) = 48
As Val[line] = 49, it’s not good
to step on the yellow square.
The last test made in IsFree concerns the check on dead-end. This checked is coupled with the filling
of FreePossibilitesTab[9].If
a square has among its neighbors, 2 neighbors which have each one only one
another neighnor, then one neighbor is the next step and the other neighnor
is the end of the way (or vice versa). If the end of the way is already fixed,
one must go back. During the search, one can determine wether the end is free
or fixed. The following figure describes a search for the start square 18
(C3 on a chessboard). 14 solutions are found (last square in a corner is excluded
from this search). The 2 curves indicate, depending on the Index, the number
of
The program also records in a log file the number of calls to IsFree() and IsFree2() and the reason of return. Basically, there are only 4 reasons :
