Simple-Linking of Pseudotours

Sections on this page: — The Linkage PolygonSimple-Linking of Two CircuitsSimple-Linking of Three or More Circuits
Linking for Symmetric ToursApplications of Simple-Linking

A pseudotour is a covering of a board by two or more circuits of knight moves. A pseudotour may look like a tour (if the circuits overlap), but does not form a single path. Pseudotour diagrams can often show a greater degree of symmetry than a tour on the same board.

The process of covering a board with circuits, or partial tours, to form a pseudotour, and then deleting as few moves as possible from the circuits to allow the loose ends to be connected up into a tour, open or closed provides a general way of looking at a number of methods of constructing tours that evolved separately. For example the Squares-and-diamonds method and the methods of Vandermonde and Collini can be interpreted in this light.

If it is possible to link the circuits to form a single tour by deleting just one move in each circuit, I call the process simple-linking. Here we describe the general principles of simple-linking circuits.

«The Linkage Polygon

In a tour formed by simple-linking of a pseudotour the deleted and inserted moves must form a knight's path, the linkage polygon. In a closed tour the linkage polygon is a closed path, and in an open tour it is an open path whose end cells are the same as the endpoints of the tour.

THEOREM: If we can link n circuits of knight moves to form a closed or open tour by deleting one move from each circuit and joining up the loose ends, then the deleted and the inserted moves must themselves form a single closed or open path of 2n or 2n − 1 moves respectively.

Proof: Let a1, b1 be the two loose ends of the path formed from the first circuit in an open tour, or from any one of the circuits in the closed tour, after deletion of the move a1–b1. Call the end to which b1 is joined in the final tour a2, and the other end of the link deleted from this second circuit b2, then call the end to which b2 is joined a3, and the other end of the path formed from the third circuit b3, and so on. By this process we number the circuits 1, 2, 3, .... If at any stage we were to join bk to a1 we would form a short circuit. So, avoiding this, we eventually reach bn which must in the closed case join to a1, the only remaining loose end. The moves a1–b1, b1–a2, a2–b2, b2–a3, ... , an–bn, which are alternately the deleted and inserted moves, thus form a path.

The idea of a linkage polygon of alternately deleted and inserted moves also provides a method of converting an open tour (on an even board) into a closed tour. If we can find such a path joining the two ends of the open tour, the deleted moves being moves of the existing open tour, then substituting the inserted moves for the deleted moves results in a pattern with two moves at each cell, i.e. either a closed tour or a pseudotour.

«Simple-Linking of Two Circuits

To link two circuits into one we need to find a pair of parallel moves, one in each circuit, whose end points are a knight's move apart. This was the method used by Vandermonde (1771). In other words the deleted and inserted moves in this simplest case must form a linkage polygon that is in the shape of a rhomb, of one of the three possible shapes:

If we have a centrosymmetric pseudotour of two paths, then to connect them together to form a symmetric tour by a single deletion in each there must be a pair of parallel moves forming two sides of a rhomb whose centre coincides with the centre of the board.

If we start with four circuits we may be able to link them into one by first joining two pairs to give two circuits and then joining these two circuits. This is a two-stage linking process, which involves six deletions and six insertions, and so its overall result is not in general a simple-linking, though it will be a simple-linking (four deletions and four insertions) if we can arrange for two of the links inserted at the first stage to be those deleted at the second stage. In this case the three rhombs join up to form a polygon bounded by eight knight moves.

«Simple-Linking of Three or More Circuits

To find all the simple-linkages of three or more circuits requires a longer step-by-step approach. One method (indicated by Collini 1773) is to give each circuit a label a, b, c, ..., giving the same letter to all cells visited by the same circuit. Now the problem is to find all the sets of n moves aa, bb, cc, ... one in each circuit, that can be joined to form a linkage polygon.

To find all possible linkages we start with one circuit, labelled 'a', and consider in turn all the moves of type aa. If the circuits are of different lengths it is best to take circuit 'a' to be one of the shortest, or else one in a corner where it has less linkages to other circuits. From each end of each chosen move aa we find out to which other circuits, if any, it will link. If we find a partial linkage polygon b–aa–c then we draw in all possible bb and cc links. Then we consider the ways in which this partial linkage polygon bb–aa–cc can be extended or completed.

In the case of three circuits we have only to look for a link b–c that will complete the linkage hexagon. The sequence of letters on the linkage polygon will be abbcca or its reversal accbba.

In the case of four circuits we have to consider all the dd links, seeking for one that will join up with the two ends of one of our bb–aa–cc partial linkages. Six sequences of linkage are possible, occuring in pairs that are reversals of each other: abbccdda/addccbba, abbddcca/accddbba, accbbdda/addbbcca.

In special cases there may perhaps be no linkages between two particular circuits, and this would reduce the number of possible sequences.

«Linking for Symmetric Tours

In the case of a symmetric tour derived by simple-linking from an even number of circuits forming a centrosymmetric pseudotour (the circuits themselves being possibly asymmetric but symmetrically arranged) the linkage polygon is of course itself symmetrical, and centred on the midpoint of the board. The case where the linkage polygon is a rhomb is the simplest example of this.

In the case of four circuits, there are in fact 18 geometrically distinct centrosymmetric octagons that can occur; all will fit on the 8×8 board:

Instead of the above process for finding a linkage polygon, an alternative procedure in the case of symmetric tours may be to try each of the 18 polygons in turn to see which will fit the given circuits. But, since each polygon can occur in four orientations there may be up to 4×18 = 72 cases to consider.

If we begin with circuits that are already symmetric in themselves, as in the method of borders (Collini), deleting one move from a circuit necessarily spoils its symmetry, so none of the tours formed by simple-linking in this case can be symmetric. Symmetric tours can however be formed by double-linking, that is deleting two moves, symmetrically placed, in each circuit and connecting up the loose ends symmetrically to form a tour. Examples of this are shown at the end of the page on Collinian tours.

«Applications of Simple-Linking

Examples of various types of pseudotours and tours constructed from them are given on a series of separate pages. These at present include:
Octonarian tours constructed from the 33 octonary pseudotours – excluding the Collinian and Squares-and-diamonds cases.
Crosspatch tours constructed from the crosspatch pseudotours in which every move is crossed centrally by another – again excluding the Collinian and Squares and diamonds cases.
Collinian tours constructed from the octonary pseudotour consisting of a central 4×4 of squares-and-diamonds surrounded by a border braid, known on other boards as the Border method.
Vandermondian tours constructed from pseudotours consisting of four 16-move circuits arranged in direct or oblique quaternary symmetry.
It is also proposed to include a separate page on Squares-and-diamonds tours meanwhile see the section on history of this subject.

Back to top