The simplest move on a board of squares is the {0,1} step of the wazir or single-step rook. The wazir's move takes it through the sides of the square on which it stands. On a chequered board this is a step to any adjacent square of opposite colour. Since the wazir does not participate in modern chess, other than as a component in the moves of king, queen, rook and pawns, its study has been unjustly neglected.
Wazir tours, besides being of interest in themselves, are also useful in analysing the structure of knight's tours on boards whose sides are double those of the wazir tour (see under Magic Knight's Tours – Braid Method). The general problem of enumerating wazir tours on rectangular boards, one would think should not be intractable to normal mathematical methods, such as the derivation of recurrence relations, but as far as I know it has only so far been tackled successfuly in a few special cases. [I vaguely remember seeing something in the Journal of Recreational Mathematics recently, but have not had time to check it out properly.]
The shortest wazir paths equivalent to an (m, n) move obviously use m + n moves. The number of shortest wazir paths equivalent to an (m, n) move is thus (m + n)!/m!n!.
Spiral labyrinths and dances are also ancient. The term labyrinth is used for designs in which there is a single path to follow; as opposed to puzzle paths, called mazes, with branching paths and dead ends, which were a Renaissance innovation (~ ad 1550). Rock-carved labyrinths are known from as far apart as Arizona, Sumatra and Scandinavia, but their dates are disputed [Pennick 1990]. All however are of similar design to the legendary labyrinth at Knossos, as represented on Minoan coins (~ 1600 bc). The pattern of the classical labyrinth is formed by bending and stretching a double meander round in a circle, as illustrated here.
Greek myth attributes the design of the Minoan labyrinth to the proto-engineer Daidalos, who is also mentioned by Homer as maker of a 'choros' for Ariadne, which was a circling dance, or a place for dancing [Liddell & Scott, Greek-English Lexicon, abridged 1935, pp.148, 786]. The prefix 'Dai-' is said to mean cunning or curious and 'Alos' is a furrow, so perhaps his very name means 'labyrinth'. Pennick (1990) attributes the discovery of the topological equivalence illustrated above to Jeff Saward in lectures given in 1981-2, however Brewer (1974, p.698) states that the Maeander "is said to have given Daedalus his idea for a labyrinth" so knowledge of the property can probably be traced to earlier sources (if indeed it was ever lost).
During the middle ages the classical labyrinth design was elaborated. An early example is the pavement labyrinth in the Church of San Vitale, Ravenna (~ ad 530). The underlying wazir tour is shown alongside the labyrinth diagram.
The famous pavement labyrinth at the Cathedral of Notre Dame, Chartres (~ ad 1250) is even more elaborate. The same design as that of Chartres occurs at St Quentin and Amiens (1288) and is extended further in the plan for the Town Maze on the common at Saffron Walden (~ 1400).
Obviously a wazir can make only one geometrically distinct open tour on a board of 1×n cells; a straight walk from end to end.
Boards 2×n. On a board 2×n (n >1) the wazir has one closed tour; a walk around the edges. The numbers of 2×n wazir open tours are tabulated below. The figures for G(n) were first found by drawing out the tours for the cases 2 to 6, then deducing the general formula and using it to calculate the other cases. The diagrams show the tours of these smaller boards, listed systematically:
In drawing the tours we find there are (when n > 2) n with an end at a corner, then n–3 with an end one in from a corner, then n–5 with an end two in from a corner, and so on, until we reach 1 or 2 as last term. Thus G(n) = 1 + (1 + 3 + 5 + ... + (n–1)) when n is even, and 1 + (2 + 4 + 6 + ... + (n–1)) when n is odd. Denoting by h and k the nearest whole numbers such that h £ (n/2) £ k, and using the properties that the sum of the first s successive odd numbers is s^2 and the sum of the first s even numbers is s(s+1) we have G(n) = 1 + (n/2)^2 or 1 + [(n–1)/2][(n+1)/2], which can be expressed concisely as G(n) = 1 + hk. For n = 1, 2, ... the successive values are: 1, 2, 3, 5, 7, 10, 13, 17, 21, 26, 31, 37, 43 50, 57, 65 ... but for n = 2, when the board is square the 2 reduces to 1 due to rotation being possible.
The S(n) symmetric tours consist of one U-shaped tour with both ends in the first rank (as oriented in the diagrams above) and a lengthwise axis of symmetry and when n is even (and > 2) there are n/2 others that have a breadthwise axis, but when n is odd there are instead (n–1)/2 that have 180° rotational symmetry. Thus S(n) = h + 1. The successive values for n = 1, 2, ... are: 1, 2, 2, 3, 3, 4, 4, ... but again for n = 2 we must reduce this to 1. A curiosity of this symmetric case is that if the two end-points of a wazir tour are symmetrically placed then the tour itself must be symmetric, and when it exists it is uniquely determined.
It happens that the number of reentrant tours equals S(n); this set includes the U-shaped tour and one other symmetric tour when n is even. The total of tour diagrams can now be calculated by the usual formula for rectangles: T(n) = 4G(n) – 2S(n) = 4hk – 2h + 2. The successive values are: 1, 1, 8, 14, 22, 32, 44, 58, 74, 92, 112, 134, 158, 184, 212, 242, ...
Boards 3×n. For a closed tour n must be even. Every 3×2m closed wazir tour forms a circuit round the edge with m–1 'indentations', each of which may be in either of the longer edges (2 choices). The number of tour diagrams is thus T(n) = 2^(m–1). Diagrams of the first few cases follow.
To find the number of symmetric tours we separate the cases of m even and odd. When m is even a tour can always be oriented with the middle indentation in a chosen edge. Then there are 2^(m/2 – 1) ways of indenting on each side of this, giving this number of tours with an axis of symmetry. When m is odd there is no central indentation, but we can always reflect if necessary so that the first indentation is in the chosen edge. The other indentations in that half can be made in 2^((m–1)/2 – 1) ways, giving this number of reflective and the same number of rotative tours. Thus S(n) = 2^(g–1) where g is the nearest whole number g ³n/4. We can now calculate G(n) = T(n)/4 + S(n)/2 = 2^(m–3) + 2^(g–2). Table of results:
n = 4 6 8 10 12 14 16 18 20 22 24 G(n) = 1 2 3 6 10 20 36 72 136 272 528 S(n) = 1 2 2 4 4 8 8 16 16 32 32 T(n) = 2 4 8 16 32 64 128 256 512 1024 2048
The following diagrams show the first few cases of open tours 3×n. They are grouped according to the separation of their end-points. Symmetric tours are printed with a darker line. I have the following limited results: (a) 3×3: G = 3, S = 1 rotative, T = 20. (b) 3×4: G = 19 (7 reentrant), S = 7 (4 reflective, 3 rotative), T = 62. (c) 3×5: G = 36, S = 6 rotative, T = 132. (d) 3×6: G = 91 (19 reentrant), S = 14 (8 reflective, 6 rotative), T = 336.
Boards 4×n. The two wazir closed tours on the 4×4 in the shape of H and C (hot and cold) are well known. Diagrams for 4×5, 4×6 and 4×7 follow.
A recurrence relation for T(n) in this case was given by C. Flye Sainte-Marie [L'Intermédiaire des Mathematiciens, vol.11 (1904) pp. 86–88] namely: T(n) = 2T(n–1) + 2T(n–2) – 2T(n–3) + T(n–4), with initial values T(1) = 0, T(2) = 1, T(3) = 2, T(4) = 6.
Results summary: (a) 4×4: G = 2, S = 2 (1 quaternary reflective, 1 binary reflective), T = 6. (b) 4×5: G = 5, S = 3 (binary reflective), T = 14. (c) 4×6: G = 15, S = 10 (3 quaternary reflective, 3 binary reflective with long axis, 3 binary reflective with short axis, 1 binary rotative), T = 37. (d) 4×7: G = 26, S = 6 (all binary reflective with long axis), T = 92. (e) 4×8: G = 72, S = 24 (4 quaternary, 16 binary reflective, 4 binary rotative), T = 236.
On the 4×4 board there are 38 geometrically distinct open tours, of which 14 are reentrant (9 from the C tour and 5 from the H) and 7 are symmetric.
Boards 5xn. 5×6: 44 closed tours, 11 symmetric (7 reflective, 4 rotative), 33 asymmetric.
5×8: I find 440 closed tours (not checked). These may be classified by corner patterns, and include 34 symmetric tours, as shown below.
Board 6×6. 149 closed tours, 28 symmetric (1 quaternary rotative, 3 quaternary reflective, 5 binary rotative, 19 binary reflective). The symmetric cases are illustrated.
Board 8×8. On the standard chessboard I have studied the wazir tours with quaternary symmetry: there are 19 reflective, none rotative.
Board 10×10. Wazir tours in quaternary symmetry total 224 reflective, 101 rotative (these totals not checked). The reflective cases can be classified according to the distance in from the edges of the moves that cross the two axes, thus: (0, 0) 52, (0, 2) 38, (0, 4) 86, (2, 2) 14, (2, 4) 34. I show one example from each class, and some assorted rotative examples.
A General Method for Larger Boards. The 4×4 H-pattern can be repeated in 2×2 array and the four components joined up by an H-pattern of linkages to generate a quaternary reflective tour 8×8. This in turn can be used to generate a tour a factor of 2 larger, that is 16×16 as shown in (A) below, and the process can be continued to larger boards. More variety in the pattern can be obtained by making the joining H-connections horizontally instead of vertically as in (B).
Similarly, the 6×6 swastika pattern can be repeated in 3×3 array and the nine components joined up by a swastika pattern of linkages to generate a quaternary rotative tour on the 18×18 board, as in (C) below. This in turn can be used to generate a tour a factor of 3 larger, that is 54×54, and so on. Alternatively the anti-clockwise swastikas can be joined clockwise as in (D). Many varied patterns of this type can be constructed by systematic linking of tours. The reader is invited to try out this visually constructive recreation.
Tours of this type are similar to patterns encountered in the study of 'fractals' or 'space-filling curves'.
First we consider wazir tours with the minimum number of right-angled turns, which are equivalent to non-intersecting rook paths with the minimum number of rook moves. On a board n×n, if there are moves in every rank and file then we have at least 2n moves. On the other hand, if there is a rank or file without a move along it, then it must be crossed or met by n mutually parallel moves, and these will require a further n–1 rook moves to join them into a single path, or n to make a closed circuit. The minimum is therefore 2n rook moves for a closed tour and 2n–1 for an open tour. In an open tour the first and last moves must be parallel, since they are among the n parallel lines. We take these horizontal. There are always at least two full-rank moves, top and bottom. To solve the problem on a rectangle n×m (m > n) we just stretch the n parallel moves along the ranks, so we can confine our attention here to square boards.
The numbers of open tours: 2×2: G = S = 1, T = 4; 3×3: G = 2, S = 1, T = 12; 4×4: G = 5, S = 2, T = 32; 5×5: G = 13, S = 3, T = 92. On the 6×6 the total of open tours is not known, but there are 21 with end at corner (2 corner to corner, 1 symmetric).
The numbers of closed tours: 2×2: G = S = T = 1; 4×4: (the C-shaped tour) G = S = 1, T = 4; 6×6: (illustrated) G = 3, S = 2, T = 16; 8×8: (illustrated) G = 12, S = 3, T = 84; 10×10 G = 58?.
The problem of a 16-move non-intersecting rook closed tour of the standard chessboard was proposed and solved with one example (the 'four-pronged' pattern) by Sam Loyd [Chess Strategy 1881]. H. E. Dudeney gave a problem solved by a 15-move open tour c2-b2 [The Canterbury Puzzles 1904], ensuring a unique solution by a barrier between d1 and e1. T. R. Dawson gave complete solutions for two 8×8 cases in 15 moves, giving 7 tours a1 to a6 [Chess Amateur, i 1909, Puzzle 28] and 6 tours a1 to a4 [British Chess Magazine, vi 1943].
The problem of finding a closed tour with just two turning points in each rank and file is impossible; there must be more than two turns in at least one of the edges. There is however a pseudotour with this property: the set of n/2 concentric squares.
To to see the uniqueness of this tour: draw the 8Q position on a blank diagram, then draw in the wazir moves in stages, considering the squares in the following order: (1) a12358, b1, c8, d1, e8, f1, g8, h12468; (2) b7, c2, d7, g27; (3) a6, b3, e2, f7, g5; (4) c6, f6, g3; (5) b5, c5, e6, f3; (6) c34, e5, f5; (7) de34. Throughout the process you must take care not to form a closed path covering only some of the vacant squares and not all. Within each stage the cells listed can be examined in any order.
This discovery naturally led me to enquire if the number of blocks needed to fix the wazir tour could be reduced. The number of blocks must be even, since the wazir moves alternately to black and white squares, so in a closed tour there must be the same number of each. The number was quickly reduced to six (a6, c2, d6, e6, f2, h6). Then further search led to the unexpected discovery (February 1978) that four blocks suitably placed on the chessboard are sufficient to determine a unique closed wazir tour of the remaining squares. These results were published in The Problemist [vol.10, nr.22 (xi 1979) p.376]. Three four-block arrangements were reported there. In 1981 Tom Marlow sent me seven more solutions, which stimulated me to find four more, and these were published in Chessics [vol.1, nr 12 (1981) pp.7-9, 12-13]. The 14 known solutions are as follows. The last one shown is the only one with a block within the central 4×4.
THEOREM: On the 8×8 board the minimum number of blocks to force a unique closed wazir tour of the remaining cells is four, and one block must appear in each quarter of the board. Proof: [Chessics 1981] If there are only two blocks then at least one 4×4 quarter of the board must be free of blocks. We can take it to be the a1 quarter. Now consider the 3×3 cells in the a1 corner, and all possible routes of the wazir through these nine cells. The following diagrams show the possible paths.
Diagrams 1-2, 3-4, 5-6, 7-8, 9-10, 11-12, 13-14, 15-16 are pairs in which the entrances and exits to the 3×3 are the same but the routes followed are different; in other words the tour is not uniquely determined in these cases. Diagram 17 similarly pairs with its own reflection in the a1-d4 diagonal. Finally diagram 18 can be settled by considering how the wazir tour outside the 3×3 must link up the entrances and exits to the 3×3 without crossing over or forming detached circuits. The connections must be either a4-b4, c4-d1, d2-d3 or a4-d3, c4-d4, d1-d2. If we now delete the interior of the 3×3 we can reconnect in accord with pattern 3, or its diagonal reflection. QED.
The general problem is: How few blocks are needed on a board m×n so that there is a uniquely determined closed wazir tour of the remaining cells? On the larger boards it is as if the blocks direct the wazir across the open board in lateral or diagonal zigzagging 'wazir waves'. No blocks are needed on boards 2×n. One block suffices on boards 3×3 and 3×5. Two blocks suffice on all boards 4×n, e.g. on any board 4×2m a solution is (a1, y2), where y represents the penultimate file. Two blocks also solve boards 3×4, 3×6, 3×8. Three blocks are needed on boards 3×7, 3×9, 3×11. Four blocks on 3×10, 5×6, 6×6, 8×8, and generally 8×2m, e.g. (a3, c6, y2, y6). Five on 7×7, six on 12×12, seven on 9×9, eight on 10×10, 14×14, 16×16; nine on 11×11. T. H. Willcocks considered the problem for larger boards and gave some examples in which larger solutions are derived from smaller ones.
The difficult 10×15 case appeared in the Journal of Recreational Mathematics 1999 and I was able to solve it in 8 blocks as shown below.
There are one or two subtle points: (1) Put in all the obviously forced edge moves, shown by heavy lines in the second diagram, then b2-b3 is forced, since b2-b1 results in c2-c1-d1 and no move through d2. (2) When the forced 'staircase' moves are put in, then b6-b7 must be taken, since a6-c6 and a7-c7 close off short circuits. Then a6-a7 is barred since it forces b6-c6 and b7-c7 which creates a longer short circuit. Putting in a6-b6 and a7-b7, there is a 'mini-avalanche' forcing c6-e6 and c7-e7, then f6-g6 and f7-g7. (3) Now there are more forced staircase moves, leading to a similar situation: o8-o9 is barred; instead o8-n8 and o9-n9 must be inserted, leading to a mini-avalanche in the opposite direction.