By a transition, or transiteration, broadly speaking, I mean a step-by-step transformation puzzle. The coined term transiteration being a combination of transition and iteration meaning a continued process.
Defined with more precision and detail: A transiteration is any problem in which the solver is given: (a) an initial configuration, or possibly a set of alternative initial configurations, e.g. arrangements of pieces on a games board. (b) A set of rules whereby the position may be transformed in a step-by-step process. (c) An objective which has to be attained in the fewest possible moves, or a given number of moves. The objective may take the form of a final completely specified configuration, or a criterion determining a set of allowable configurations only one of which, ideally, can be reached in the minimum number of steps (such as checkmate in chess problems). The number of steps needed may or may not be specified. Knowing it of course makes the problem a little (or even a lot) easier.
The transiterations form a very wide and varied class of quasi-mathematical recreations, but because of their diversity in appearance and presentation they have not hitherto been treated as a single family as is attempted here.
A graphical method of visualising transiterations, at least in part, is often helpful, in which we represent configurations by points (nodes) and allowable transitions between them by arrowed lines (moves). The problem thus becomes one of finding a route from a node belonging to the set of initial positions allowed to a node representing a possible final position, along the arrowed lines of the network in fewest moves. Borrowing terms from geography, the path is a geodesic on the map.
A more abstract representation of a transiteration is as a set T of ordered pairs (A,B) of configurations. If (A,B) is in T then the transition from A to B is allowable. We can then denote by T(n)A the set of configurations reachable from A in n transitions allowed by T. However, among these configurations will usually be some that can also be reached in fewer than n transitions. Denote by T'(n)A those that can only be reached in n transitions and no fewer. These can be called the prime nodes.
An important class of transiterations, which includes the vast family of chess problems, is formed by those in which the configurations are arrangements of pieces on a board of cells. We may define a move to be a transition in which a single piece is affected. This may be the placement of a piece P in a cell c (written P-c), the removal of a piece from a cell (written Pc-), or the transfer of a piece from one cell to another (written Pc-d).
Examples to be added here.
Examples to be added here.
Rule: In these transiterations a group of chess pieces, all of the same colour, are held in a confined area and their freedom of movement is restricted further by the condition: No piece guarding another. We list them according to number of pieces and size of board.
3 men, 4x4 board: Kd1, Qa2, Rb4. Play the K to the opposite corner of the board. Solution in 21 moves: Kc1, Rd4, Rd3, Qa4, Kb1, Rd2, Qc4, Ka1, Qb3, Rd4, Qc2 (this is the mid-way point, subsequent moves reflect the previous play in the a1-d4 diagonal), Rb4, Qa3, Ka2, Qd1, Rc4, Ka3, Qb1, Rd4, Rd2, Ka4. [T. R. Dawson, Bolton Football Field 24 December 1910].
4 men, 5x5 board less ab45 corner: Knighted Rooks (Empresses) e5, d4, b1, a1. Interchange the two pairs. Solution in 14 moves: c1, e3, a3, e1, d5, c5, d2, d4, a2, b2, e3, e1, a1, e5, or the reverse. [T. R. Dawson, Problemist Fairy Chess Supplement April 1932, problem 405].
4 men, 5x5 board: (a) Kc1, Qd5, Rb4, Na1. (b) Ke2, Qd5, Rc3, Na1. Play the King to the centre. Solutions in 7 moves [G. P. Jelliss, Chessics #6 p.6].
4 men, 5x5 board: Ka1, Qe3, Na4, Nb4. Play the King to another corner. Solution in 13 moves: Kb1, Qe5, Kc1, Kd2, Na2, Kd3, Qe1, Kd4, Nb2, Kc5, Kb5, Qe3, Ka5. [G. P. Jelliss (composed 11 December 1977), Chessics #6 p.7].
4 men, 5x5 board: Ka1, Qc2, Na5, Nd5. Play Q to c4. No piece making two moves in succession. Solution in 23 moves: Qe2, Kb1, Nb3, Nb4, Nc5, Kc1, Na4, Qe5, Kd2, Na2, Kd3, Qe1, Kd4, Nb2, Kc5, Qe4, Nc1, Kb5, Nb3, Nd1, Na1, Ka5, Qc4. The extra condition merely stops duals, it does not affect the number of moves needed. [G. P. Jelliss (composed 29 December 1977), Chessics #6 p.7].
5 men, 6x6 board: Qb4, Rc5, Rd1, Ba2, Be3. Interchange the Rooks. Solution in 18 moves: Bf2, Rd3, Rc1, Be6, Qa4, Rb1, Bc5, Rf3, Bd6, Rc3, Rb2, Bf5, Re2, Re1, Qa2, Bf4, Rc6, Rd1. [T. R. Dawson, Norwich Mercury, 28 December 1910].
Rule: From a sequence (a, b, c, ...) we are allowed to form other sequences by the operations of adding one element to another or subtracting one from another, but we are not allowed to add an element to, nor to subtract it from, itself. It follows that we can add and subtract integral multiples of an element to or from another element.
It is possible to show that by this process the sequence can be given any "even" permutation (i.e. one equivalent to an even number of interchanges) but not an "odd" permutation. We can also negative any even number of elements, but not an odd number. Combining these two results, we can give the sequence an odd permutation provided we negative an odd number of the elements at the same time.
Example (1): Convert (a, b) into (b, a). Answer: (a, b) - (a+b, b) - (a+b, a) - (b, a) in three steps. An alternative sequence of moves is: (a, b) - (a, ba) - (b, ba) - (b, a). We can similarly transform (a, b) to (b, a) in three moves in two ways.
Example (2): To permute (a, b, c) cyclically, i.e. to (c, a, b) or (b, c, a), the only even permutations of three elements. A solution in six steps is: (a, b, c) - (a+c, b, c) - (a+c, a+b+c, c) - (a+c, a+b, c) - (a+c, a+b, a) - (c, a+b, a) - (c, a+b, b) - (c, a, b).
Examples to be added.
The name solitaire, while originally applicable to any "game for one player", and still sometimes used in that sense, has come in particular to be applied to puzzles in which a number of pieces (usually in the form of pegs fitting into holes in a board, or marbles sitting in circular seats) are arranged on a board to be removed one at a time, the method of move and capture being that of the short jump of capturer over victim to the vacant cell beyond, the aim being to reach a specified configuration, such as leaving only one piece on the board.
The following, constructed by working backwards, are all the possible arrangements of up to 7 men on a board of square cells with just one vacant cell, that will reduce to one man by a suitable sequence of captures. The final man can be any of those on the blue cells and can be left on any of the cells coloured yellow. Where both these conditions apply the cell is coloured green. The cross-shaped formation marked with an asterisk (*) was given by J. Busschop, Recherches sur le Jeu du Solitaire 1891 (as reported in Fairy Chess Review June 1943).
Example 1 Square board at least 5x5. Only the initial piece can create new pieces. Play to stalemate in the fewest moves. How many ways? Answer: 8 moves in the form of a "figure eight" (two squares joined at a corner), 16 ways. The piece ends where it started with all four directions now blocked.
Example 2 Square board at least 4x4. Each piece can create only one new piece. Play to stalemate in the fewest moves. How many ways? Answer: 4 moves, 8 ways, e.g. N, S, E, W. The fourth created piece is now on the original cell and has no move.
Pentalpha Cretan puzzle described by Miss L.S.Sutherland in 1938, also known "in northern India; in Sikkim and Assam where it is known as Lam Turki and in the Karwi division, United provinces, as Kawwadand" (Source?). Pentagram board with nine pebbles. A move consists in placing a piece on any vacant cell and jumping it in a straight line over one cell (vacant or occupied) to another vacant cell. You have to do this nine times. Solution: Starting at an inner node, number the nodes 0 to 9 in the sequence of a "dabbaba tour" round the star (after the first move all subsequent moves are uniquely determined); the inner cells are all even and the outer cells odd. Then a solution to the puzzle (the end of each move being the start of the previous move) is: 89, 78, 67, 56, 45, 34, 23, 12, 01. Leaving node 0 vacant. The tenth move 90 would complete the cycle, and since the cycle can be started anywhere any cell can be the one left vacant; the first move should be made to a cell one leap from the required final hole.