| The Games and Puzzles Journal — Issue 42, November-December 2005 |
Introduction
The ever fascinating world of the knight's tour has been attracting and entertaining innumerable people for centuries and will continue to do so forever. The reason is simple. The more we delve into it, the more we discover, and amazingly, still more remains to be explored and discovered. The author has constructed numerous reentrant cyclic single-diagonal magic tours. Few such tours have even broken diagonals adding to the magic constant. But how many such tours exist? Is there any reentrant, 'perfect magic tour' (rows, columns and both diagonals adding to the magic constant)? What about magic tours having bimagic properties? A plethora of such questions have remained unanswered. This paper is a sequel to a previous one in The Games and Puzzles Journal: Issue #32 March-April 2004.
The New Magic Tours
Note: Since Mr Kumar has provided the Diagrams of the New Magic Tours discussed here in excellently reproducible form the Editor has preferred to show them on a separate page that opens in a new window. This is to avoid the danger of introducing errors by interfering with the coding. By resizing one or both windows the text can be read alongside the appropriate diagram.
Figure 1 is an 'almost perfect magic tour' with its even magic diagonal different from the previous ones. Figures 2 to 6 can be obtained by modifying its non-magic diagonal quads. Figures 7 to 9 have rearrangement of the numbers along its magic diagonal. Similarly, Figure 10 has a different arrangement along its magic diagonal. Figures 11 to 13 can be obtained by modifying its non-magic diagonal quads.
Figure 14 is a different one again and Figures 15 to 18 can be derived from it. Figure 19 is an improvement over the previous tours. Its non-magic diagonal is 16 more than the magic constant. Figure 20 is the nearest to perfection so far achieved. Its non-magic diagonal is 12 short of the magic constant. Figures 21 and 22 also have similar properties. These two tours also have a broken diagonal adding to the magic constant. It is shown in pink colour. Figures 23 to 25 have two adjacent magic diagonals.
Tours having bimagic properties is another field that has not been looked into. The author has observed that tours having pandiagonal magic properties are rare and the tours having bimagic properties are still rarer. Figure 26 is a tour having bimagic property, shown in blue colour. That is, sum of numbers in this row is 870 and the sum of its squares is bimagic constant, namely, 83810. Its reverse tour also has this bimagic property. A magic tour having diabolic bimagic properties has also remained elusive. Figure 27 is the nearest one so far achieved which has a broken diagonal, whose square adds up to 83812, just 2 more than the bimagic constant 83810. It is shown in green colour. All these reentrant tours have cyclic magic properties too. Readers are requested to look for magic tours having diabolic bimagic properties.
Magic Tours of Knight are a subset of more general, magic squares. Few methods of constructing magic squares are known but a general theory of magic squares has remained elusive. It is perhaps the oldest unsolved mathematical problem.
Conclusion
T. H. Willcocks published the first open, single-diagonal magic knight tour in the year 1955. This article is to commemorate its golden jubilee. The work by Willcocks, Murray, Jelliss and the present writer has led to enumeration of over a hundred, open, single-diagonal and a few both-diagonal magic tours. The reentrant, both-diagonal magic tour has remained elusive. However its search has led to the discovery of over one thousand five hundred single-diagonal magic tours, many having cyclic, pandiagonal and bimagic properties. Earlier, the author had estimated the number of simple magic tours (only rows and columns magic, not diagonals) to be around 100,000 [in The Games and Puzzles Journal Issue #24, September-December 2002]. Further studies have revealed that so many tours are only of Wadiar's type. So their total number may be, around one million.
G. P. Jelliss has derived four single diagonal 12 by 12 magic tours from a previously known 8 by 8 magic tour. [See the Knight's Tour Notes section on 12 by 12 Magic Tours for these and other results referred to above.] Since all the 280 magic tours on the 8 by 8 board have been enumerated, thanks to the Stertenbrink-Meyrignac-Mackay multinational team [see http://magictour.free.fr/], readers are requested to look into their extension to the 12 by 12 board. Magic tours on still larger boards have got scanty attention. Readers are requested to look into these also. [The author is obliged to Mr Jelliss for providing photocopies of Murray's manuscript; a priceless gem in India].
Awani Kumar queried why the application of standard mathematical methods, like "Solving the system of linear equations with the successive numbers a knight's move apart" has not led professional mathematicians to crack the problem. Well of course they have tried this approach, and their results have appeared in many papers. There are many pages on magic squares in the MathWorld pages for example (under 'Recreational Mathematics') and there are some good books on the subject, such as: W. S. Andrews, Magic Squares and Cubes (1917, reprint by Dover Publications 1960). W. H. Benson and O. Jacoby, New Recreations with Magic Squares, (Dover Publications 1976). The more recent compilation: C. A. Pickover, The Zen of Magic Squares, Circles and Stars (Princeton University Press 2002) shows very little advance on the Andrews work apart from quoting examples by John Hendricks that extend the subject to higher dimensional figures. There are also good short accounts in the well known books on Mathematical Recreations by W. W. Rouse Ball and by M. Kraitchik.
By direct application of the method of simultaneous linear equations little can be deduced except in the case of the smallest square arrays. For generality consider a rectangle of r rows and s columns, with the entries A(i, j) where the rank number i takes the values 1 to r and the file number j takes the values 1 to s. If the average of all the entries is X, then the rank sum must be sX and the file sum rX. We can enter s – 1 numbers at random in the first rank and the final entry in the rank is then determinate, being sX – [A(1, 1) + A(1, 2) + ... + A(1, s – 1)]. Similarly for the first r – 1 ranks. The entries in the last rank are now fully determined. The last entry in file j, from 1 to s – 1, being rX – [A(1, j) + A(2, j) + ... + A(r – 1, j)]. The final entry, in the bottom right corner, must be A(r, s) = [Sum of all A(i, j) for i ranging from 1 to r – 1 and j ranging from 1 to s – 1] + sX + rX – rsX.
The term following the square bracket takes the form rX – (r – 1)sX when calculated down the file and sX – (s – 1)rX when calculated along the rank, both of which are equivalent to sX + rX – rsX. In this last expression rsX is the total T of all the entries in the array, and we could alternatively write rank-sum = T/r, file-sum = T/s, average = T/rs, using T instead of X. In the case of a square array we have r = s, and so the rank-sum equals the file-sum and we can write sX = rX = Z for the magic constant.
In the above array there are (r – 1)(s – 1) + 1 independent variables, namely the entries in all the rows and columns except the last, plus either X or T (or in the square case Z). For these variables to be determinate requires extra conditions. For instance if the numbers in the array are to be all the numbers from 1 to rs then T = (rs + 1)rs/2. The requirement for diagonals to have a constant sum can also be expressed as a simple linear equation. However, other conditions, such as the successive numbers being a knight's move apart, are not so easily expressed. This is indeed why the magic knight's tour problem is difficult and interesting.
Now let's consider the simplest square cases. The first is very elementary but the problem gets rapidly more complicated.
The 2 by 2 Square.
In the case of a 2 by 2 array we get the general form:
| A | Z – A |
| Z – A | A |
where Z = 2X and there are just two variables A and Z. We can alternatively define B = Z – A putting the array in the form of a literal latin square as here:
| A | B |
| B | A |
If we also require the diagonals to add to the same sum then we must have A = B, and all four entries must be the same.
The 3 by 3 Square.
In the case of a 3 by 3 array we get the general form:
| A | B | Z – A – B |
| D | E | Z – D – E |
| Z – A – D | Z – B – E | A + B + D + E – Z |
where now Z = 3X and there are five variables (A, B, D, E and Z).
If we define I = A + B + D + E – Z, x = A – I and y = E – I we get the form
| = |
| + |
|
presenting the square as a sum of two latin squares.
The 4 by 4 Square.
In the case of a 4 by 4 array there are ten variables. The general form is:
| A | B | C | Z – A – B – C |
| E | F | G | Z – E – F – G |
| I | J | K | Z – I – J – K |
| Z – A – E – I | Z – B – F – J | Z – C – G – K | A + B + C + E + F + G + I + J + K – 2Z |
In the process of seeking a way to express this array, if possible, as a sum of latin squares, or at least groups of satins, using a similar strategy as for the 3 by 3, I first defined a = Z – A, f = Z – F, k = Z – K, which puts it in the form:
| Z – a | B | C | a – B – C |
| E | Z – f | G | f – E –G |
| I | J | Z – k | k – I – J |
| a – E – I | f – B – J | k – C – G | Z – a – f – k + B + C + E + G + I + J |
Apart from the Zs which form a satin (one in each rank and file) this doesn't on the face of it look very promising for forming latin squares, since the letters form square patterns, with entries in two ranks and two files. However I hit upon a general method for converting such arrangements to satin type. The trick is to put null formulas of the type G – G, I – I, and so on in the cells in the other ranks and files and then to combine half of them with the symbols already in the cells. For instance putting G – G and I – I in the cell containing B we can then define X = B + G + I making the entry X – G – I. Similarly putting E – E and J – J in the cell containing C and defining Y = C + E + J we get Y – E – J. A similar process can be used to redistribute the a, f, k, and defining U = Z – a – f – k we get the much tidier form:
| = |
| + |
| + |
| + |
| + |
| + |
|
The Us form a satin, occupying the principal diagonal. The Xs and Ys form satins of Beverley type (with one element in each rank file and diagonal). But these all have a cell in common so do not form components of a latin square. The other elements can be displayed in the form of three partial latin squares, having one satin component zero. Possibly further manipulation may reduce the number of latin squares.
A general form for any diagonally magic square was published by our old friend Ernest Bergholt in Nature 1910 (vol 83 page 368, according to Rouse Ball) in the form:
|
| = |
| + |
| + |
|
where the second and third components are not quite latin squares.
Rouse Ball writes: The square is pandiagonal if a = b = d – c = (A – B – C + D)/2, symmetrical if a + c = d = b – c and A + C = B + D; therefore never both pandiagonal and symmetrical, since then we should have A – a = B.
by Tom Marlow (November 2003)
The regular octahedron has eight equilateral triangular faces and can be thought of as two square pyramids joined base to base. So it has six vertices with four triangles meeting at each. Now add the numbers 1 to 8, one to each face, so that the total around each vertex is the same, this total to be known as the magic constant. Can this be done, and if so in how many ways?
The total of 1 to 8 is 36 and each triangle contributes to three vertices so that the total of all vertices is 108 and the magic constant is 18. There are eight ways, listed below, to choose from the numbers 1 to 8 to make a set of four which total to 18. So each vertex must have one of these sets on its surrounding faces.
A: 8, 5, 3, 2 and a: 7, 6, 4, 1
B: 8, 7, 2, 1 and b: 6, 5, 4, 3
C: 8, 6, 3, 1 and c: 7, 5, 4, 2
D: 8, 5, 4, 1 and d: 7, 6, 3, 2
The sets form pairs which use all eight digits within the pair. Opposite vertices are made from all eight faces, so must each use one set of such a pair. It turns out that the Aa pair must be used in any solution. This is because if, for example, A and B are being used then faces 8 and 2 which are in both sets must share an edge. And if C is also used then 8 and 3 can share an edge and so also can 8 and 1 between B and C. No such pairings are possible if B, C and D are tried together.
This leads to three solutions, using ABC, ABD and ACD, as shown in Figure 1 (a), (b) and (c). The numbers on the hidden faces are shown off the edges of the diagrams. [The view shown is from above the A vertex.]
In each case a mirror image is possible, as shown in Figures 1 (a'), (b') and (c'). In this Figure (b') is oriented showing a diagonal reflection of (b), but if it is rotated 90 degrees clockwise it will be seen as a left-right reflection of (b), similar to the relationship between (a) and (a').
A magic octahedron with numbered faces adding to a constant round each vertex is of course equivalent to a magic cube with numbered vertices adding to a constant around each face.
by Tom Marlow (January 2004)
The cuboctahedron is one of the Archimedean or semiregular solids. It is made by cutting the corners from a cube by lines joining the midpoints of each edge. The squares are thus made into smaller squares rotated 45 degrees and the corners become triangles. There are 14 faces (six squares and eight triangles) meeting at 12 vertices.
The problem posed here is to add the numbers 1 to 14, one on each face, so that the total of the four faces meeting at each vertex is the same.
Figure 1(a) is a view of the solid. Figure 1(b) is a diagram of all the faces, which is more convenient for working on the problem, but note that the 14th and square face is under the diagram, or can be considered as surrounding it. Corresponding faces in the two diagrams have been given corresponding letters of identification.
To solve the problem it is first necessary to establish the vertex total, which may have any value from 28 to 32. The higher figures arise when higher numbers are allocated to the square faces, since they contribute to four vertices each. It is also easy to show that in any solution opposite pairs of squares must add to the same total. The same applies to opposite pairs of triangles (e.g. H and F or E and J) but the total may or may not be the same as for the squares.
For a vertex total of 28 the squares must be given the numbers 1 to 6 and this so restricts the possibilities that it turns out that there is only one solution, as shown in Figure 2(a). The number on the hidden base is shown above the diagram. This solution can be reflected as shown in Figure 2(b). The reflected version cannot be rotated to coincide with the original, so it is a matter of taste as to whether it is considered a different solution. The reflection shown turns about the south-west to north-east diagonal but if either diagram is rotated by 90 degrees anti-clockwise the reflection can be seen to be a left-right reflection, showing that only one distinguishable reflection is possible.
For a total of 32 the squares must be numbered 9 to 14 and a solution can be derived from Figure 2(a) by changing each number to its complement to 15, as shown in Figure 3.
For a vertex total of 29 there is a wider range of choice for the square numbers, but the possibilities are limited as the range overlaps the triangle range, and exhaustive search shows that there is no solution. For total 31 similar but complementary considerations apply and there is no solution.
For a total of 30 the total of both square and triangle pairs must be 15 which gives a wider choice of possible pairings and results in six solutions, which are shown in Figures 4 (a) to 4(f). In all cases a reflection as for Figure 2(a) in Figure 2(b) is possible.
by George Jelliss and Tom Marlow
The space compass, which I introduced in The Games and Puzzles Journal Issue #23 May-August 2002, is a map of 7 great circles on a sphere dividing it into 48 spherical triangles with angles of 45, 60 and 90 degrees (the angles of a spherical triangle add to more than 180 degrees). The 26 points of intersection of the great circles can be taken as the vertices of a polyhedron formed of 48 plane triangles, but I'm not sure what the angles of these triangles work out to be (reducing the spherical angles proportionately gives angles of 41.5, 55.5 and 83.0 degrees approximately).
Tom Marlow's results above suggested to me that something similar might be done with the space compass. The result I found was this arrangement in which the numbers round all the nodes add to multiples of 49 (that is 98, 147 and 196 at the points where 4, 6 and 8 triangles meet respectively). The triangles round the 8-fold and 6-fold nodes are easily made to add to these totals since they consist of pairs adding to 49. Getting the 4-fold nodes to add to 98 was the tricky part.
In the diagram the sphere is represented by two hemispheres which must be imagined folded together (along a hinge at the point where they meet) to form the complete sphere.
I suggested the idea to Tom Marlow and he came up with this different result, in which the numbers 1 to 26 are placed at the nodes and each of the 7 great circles adds up to the same total of 108. This is 4 times 27, the diametrally opposite numbers adding to 27.
In this diagram the numbers 19, 1, 9, 25, 8, 26, 18 on the great circle where the two hemispheres fit together are duplicated, since these nodes are represented twice.
Two numerical puzzles have become popular in the newspapers recently under the Japanese names Sudoku and Kakuro. The wikipedia has a good article on Sudoku and its history, though the page on Kakuro (or Cross Sums) is not yet as informative.
Although both involve entering digits 1 to 9 in the squares of a grid, Sudoku is purely a logic puzzle (any 9 distinct symbols could be used instead of the digits) while Kakuro combines logic and a little arithmetic (the digits entered must add to specified sums).
Having been a supporter of the Dozenal Society of Great Britain since about 1990 it occurred to me to try to compose examples of Sudoku and Kakuro using the dozenal digits, which include two extra symbols for ten and eleven. The following two puzzles are the result. They were first published in the Dozensonline forum (see the General Chit-Chat section), but here I can present them with better diagrams and perhaps to a wider readership.
There is no accepted standard system for the two extra symbols needed for ten and eleven in dozenal numeration. The DSGB favours the rotated 2 and 3, as suggested by Isaac Pitman in the 19th century, while the US organisation favours the star and hash symbols found on digital phone pads. Here I use the Roman X for ten, which naturally suggests Y for eleven.
Here is my effort at composing a Sudoku puzzle using all twelve dozenal digits. The grid is twelve by twelve and is divided into twelve rectangles each 3 by 4. The puzzle is to fill in the gaps so that each rank, each file and each rectangle contains the twelve digits 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, X, Y.
In this composition 54 digits are given which is an average of 4½ per box. This is the best I was able to achieve in the time available; better examples can probably be made. Note that there is only one X given and no Ys. The last move is to fill these in.
It took me about three hours to compose the above problem, from thinking of the idea through to testing that it worked out correctly. Two hours one day and one hour the next. The method used was first to fill in the 0s, one in each rank, file and box, then the 1s, then the 2s and so on, just putting them in at random. When I got to putting the Xs and Ys in I had to do a bit of fiddling around, interchanging pairs here and there, to make sure there weren't two Xs or two Ys in the same box. I didn't aim at any form of symmetry or other kind of pattern in the arrangement, just a random solution. Then it was a matter of striking out digits whose values could be determined by the other existing digits, i.e. working the puzzle backwards. All the Ys and all but one X could be eliminated straight away, since they form a "bisatin of one circuit" which is something I've studied before in the printed issues of The Games and Puzzles Journal (volume 1, issue 10, page 160, 1989 ). What I aimed at was to leave the top left rectangle blank, and to use 6 or less of each digit, and to get the average number per rectangle down as low as I could.
Perhaps the reader might like to try composing one, which is why I've explained my method in some detail. Of course the final and essential step is to solve it yourself to ensure there is only the one solution. Most of the published Sudoku problems I've seen use a symmetrical layout of the given numbers but this is not an essential feature.
Kakuro puzzles have been appearing in The Guardian (in the G2 section) since they changed the paper's format recently, and I've found them fascinating. They are also known as Cross-Sums, being somewhat like Cross-Words. Instead of a word, each light (row or column of spaces) contains a sequence of two or more of the digits 1 to 9, not using any digit twice. The total to which each light must add is specified. The Guardian denary version uses an array 9 by 11 giving 99 cells (100 – 1), not counting the left and top border of index cells. For the dozenal version below I have used a grid 11 by 13 giving 143 cells (or in dozenal numeration Y by 11 giving YY cells, still 100 – 1).
The puzzle is to put one digit 1, 2, 3, 4, 5, 6, 7, 8, 9, X, Y in each space to give the specified totals, shown to the left of each across light and at the top of each down light. The same digit cannot be repeated in a light. Thus for example the total 7 can only be shown in three cells as 1 + 2 + 4 (in some order), not as 1 + 3 + 3, nor 3 + 2 + 2.
Note also that the totals in the diagram are expressed in dozenal notation. For example: 10 represents one dozen, 11 represents a dozen plus one, 1X represents a dozen plus ten.
The above problem was composed from the centre outwards, and is based mainly on using pairs of sums that have only one number in common where they intersect. For example ten in four cells is X = 1 + 2 + 3 + 4 and sixty (five dozen) in 8 cells is 50 = Y + X + 9 + 8 + 7 + 6 + 5 + 4. So they intersect at 4.
Getting a 3 by 3 area correctly filled, as occurs three times in the above puzzle, is tricky as the four numbers at the corners of the 3 by 3 square must not be permutable. For instance here 6 and 7 can be interchanged without affecting the row or column sums:
| 7 | 6 |
| 6 | 7 |
I imagine this will be difficult to solve, especially for someone new to these types of puzzle, but hope it is of interest.
I must admit that composing the Kakuro puzzle took more time than the Sudoku, so I don't fancy composing a whole series of them. Though I suppose that the process would become quicker with experience. I imagine the puzzles published in the papers are churned out by computer methods. Does anyone know for sure?
Does anyone know of any other number puzzles of these types? That is to say, puzzles where many different examples can be composed, all using a similar format, as compared with one-off puzzles like cryptarithms?
Copyright © 2005 — G. P. Jelliss and contributing authors.
Partial results may be quoted provided proper acknowledgement of the source is given.