13

The celebrated British mathematician and lover of public transport, Simon Norton, was one of those who passed in 2019. He was the subject of a wonderful biography and one of my favourite human beings: an amazing and innocent man.

He was not a particular fan of chess, but here is a tiny gem due to him.

“Toroidal” means the board has no edges. You can leave on the left and just appear in the board on the right. You can leave at the top and just appear at the bottom. And vice versa.


EDIT: Jörg P. has totally nailed it, so I have to give him the green tick. But his solution doesn't give any insight as to why the number is what it is. So I guess that's a bonus question:

  • Bonus question: why do you get this number (120)?
  • 4
    This is what I though of so far. Because the board is toroidal, each knight will be attacking exactly 8 squares. All together then, 5 knights will be attacking 40 squares. Since there's only 25 squares altogether and 5 of those are occupied by the knights, it means that there are only 20 squares that can be attacked on each configuration. Other observation: knights on the edge attack the same colors as the color of their square, other knights attack squares of a different color. I don't know how to proceed from here further. – gst Dec 12 '19 at 15:49
  • 2
    Each empty square is attacked by an average of 2 knights, I agree. I don’t think the colour of squares is so helpful here – Laska Dec 12 '19 at 15:52
  • 1
    Off topic but TIL that the Ultima world was toroidal – JollyJoker Dec 13 '19 at 14:22
  • 1
    @gst, Like you said, each knight attacks eight squares, but you can place the knights such that each unoccupied square is attacked by two of them. So you actually only need twenty unoccupied squares to accommodate the five knights. – Solomon Slow Dec 13 '19 at 22:39
  • 1
    OK, so the point of this puzzle is that the rook's graph, the bishop's graph, and the knight's graph on the 5x5 toroidal board are isomorphic, and there are 5! ways to place 5 nonattacking knights for the same reason that there are 5! ways to place 5 nonattacking rooks. How nice. Is this happenstance, or does it have some deep mathematical significance? – bof Jul 16 at 5:04
9

This is my answer :)

Spoiler alert: Answer is in a comment in the last line of the code block

using System;

namespace Toroidal5Knights
{
    class Program
    {
        static int solution = 0;
        static bool[,] board = new bool[5, 5];

        static int[] dx = { -1, 1, 2, 2, 1, -1, -2, -2 };
        static int[] dy = { -2, -2, -1, 1, 2, 2, 1, -1 };

        static int Wrap(int position)
        {
            if (position >= 5) return position - 5;
            if (position < 0) return position + 5;
            return position;
        }
        static bool PlacePossible(int posX, int posY)
        {
            for (int i = 0; i < dx.Length; ++i)
            {
                if (board[Wrap(posX + dx[i]), Wrap(posY + dy[i])]) return false;
            }
            return true;
        }
        static void SolveFiveKnights(int posX, int posY)
        {
            if (posY >= 5)
            {
                if (IsSolution())
                {
                    PrintSolution();
                    solution++;
                }
                return;
            }
            if (posX >= 5)
            {
                SolveFiveKnights(0, posY + 1);
                return;
            }

            if (PlacePossible(posX, posY))
            {
                board[posX, posY] = true;
                SolveFiveKnights(posX + 1, posY);
                board[posX, posY] = false;
            }
            SolveFiveKnights(posX + 1, posY);
            return;
        }
        static bool IsSolution()
        {
            int count = 0;
            for (int i = 0; i < 5; ++i)
            {
                for (int j = 0; j < 5; ++j)
                {
                    if (board[i, j]) count++;
                }
            }
            return count == 5;
        }
        static void PrintSolution()
        {
            Console.WriteLine("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
            for (int i = 0; i < 5; ++i)
            { 
                for (int j = 0; j < 5; ++j)
                {
                    if (board[i, j])
                    {
                        Console.Write(1);
                    }
                    else
                    {
                        Console.Write(0);
                    }
                }
                Console.WriteLine();
            }
            Console.WriteLine("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~");
        }
        static void Main(string[] args)
        {
            SolveFiveKnights(0, 0);
            Console.WriteLine(solution);
        }
    }
}
// So the number of solutions is 120.
| improve this answer | |
  • Welcome to chess.stackexchange! So what number pops up when you run your program? – Laska Dec 12 '19 at 15:14
  • 1
    Thanks! I edited my code so you can scroll down to see the answer the program computes. I did it in this way so other people can avoid spoilers – Jörg P. Dec 12 '19 at 15:17
  • 1
    It needn't be a multiple of 25, because of solutions which have only 5 distinct cyclic perms (e.g. a1, b2, c3, d4, e5). – Rosie F Dec 12 '19 at 17:51
  • 1
    @RosieF That is a good point. I hadn't realised that was in the solution set. – Chromatix Dec 12 '19 at 18:07
  • 2
    Instead of the dx and dy arrays, couldn't you have done something along the lines of Math.Abs(posX) + Math.Abs(posY) == 3 && Math.Max(posX, posY) == 2 ? The only possible int values here are 2 and 1 with any sign, in any order. Saves you a bit of looping :) Also, if (position >= 5) return position - 5; can be changed to position = position % 5; (it inherently also works for negative numbers, you always end up with a positive int between 0 and 4 (inclusive)). Sorry, the code reviewer in me couldn't help but help :) – Flater Dec 13 '19 at 16:46
12

I noticed a simplification of @RosieF's solution:

Label the squares with two-number labels as follows:

4,2 0,3 1,4 2,0 3,1
1,0 2,1 3,2 4,3 0,4
3,3 4,4 0,0 1,1 2,2
0,1 1,2 2,3 3,4 4,0
2,4 3,0 4,1 0,2 1,3

Then two knights may occupy two squares x,y and X,Y iff those squares' first numbers x and X are different and their second numbers y and Y are different.

Since there are 5 knights and only 5 different numbers in each direction, that means that every x-value must be occupied by a knight, and each of the possible y-values must be assigned to one of those knights. If we sort the knights' coordinates by their x-value, then list only the y-value, then we wind up with some permutation of the numbers from 0 to 4. Every valid placement of the knights produces a permutation of the numbers 0-4, and every permutation of those numbers corresponds to a valid arrangement of the knights.

The total number of valid arrangements of the knights is thus 5!, or 120.

| improve this answer | |
9

Label the squares with two-number labels as follows:

4,2 0,3 1,4 2,0 3,1
1,0 2,1 3,2 4,3 0,4
3,3 4,4 0,0 1,1 2,2
0,1 1,2 2,3 3,4 4,0
2,4 3,0 4,1 0,2 1,3

Then two knights may occupy two squares x,y and X,Y iff those squares' first numbers x and X are different and their second numbers y and Y are different.

Regard these numbers as modulo 5. Then the two-times table is as follows:

 y 0 1 2 3 4
2y 0 2 4 1 3

So if y and Y are different, so also are 2y and 2Y.

If we have a solution, then what happens if we move each knight from x,y to x,2y? The knights' x's were all different from each other, and each x remained the same, so they remain all different from each other. Their y's were all different from each other, and different y's are still different after they get doubled, so they remain all different from each other. So the result is a solution.

What does this doubling of the y's correspond to on the board? Magnifying it by a factor of sqrt(2) linearly, and turning it 135 degrees clockwise. Having magnified a solution once, we may magnify a second time (two magnifications double the solution linearly and turn it through 90 degrees) and a third, but a fourth magnification results in the original again.

We may start with this solution

. . . . .
. . n . .
. n n n .
. . n . .
. . . . .

and magnify it 0, 1, 2 or 3 times, yielding a total of 4 solutions. In each case, the rows can be be cyclically permuted in any of 5 ways, as can the columns, to yield 25 cyclic permutations of each of these 4 solutions, for a total of 100.

In addition we have the following solution

. . . . .     
. . . . .     
n n n n n     
. . . . .     
. . . . .     

This, too, may be magnified 0, 1, 2 or 3 times, yielding a total of 4 solutions. Each of these 4 solutions has only 5 cyclic permutations, for a total of 20 cyclic permutations from these 4 solutions.

This makes a grand total of 100 + 20 = 120.

As Jörg P. has shown, there are no more.

| improve this answer | |
7

There are essentially six solutions that are rotationally and translationally unique. Two of them yield five translations and five more rotated translations each, for a total of twenty:

NNNNN
.....
.....
.....
.....

N....
.N...
..N..
...N.
....N

The remaining four unique solutions can be translated to each of the 25 positions on the board, but are rotationally symmetric, giving a combination of 100 solutions:

..N..
.....
N.N.N
.....
..N..

.....
..N..
.NNN.
..N..
.....

N...N
.....
..N..
.....
N...N

.....
.N.N.
..N..
.N.N.
.....

This yields the total of 120 solutions found by @JörgP.'s program.

| improve this answer | |
  • 2
    Its actually a C# program ;) – Jörg P. Dec 12 '19 at 19:59
  • 1
    @JörgP. Ah, Microsoft WeCantLegallyCallItJavaAnyMore. Even worse then, as I primarily use a Mac and absolutely refuse to install Visual anything on my Windows machine. – Chromatix Dec 12 '19 at 21:22
  • 1
    Your "third unique solution" doesn't exist as such; it's actually four other solutions that can each be translated to each of the 25 positions, but can't be rotated or reflected at all. These four solutions are the four magnifications of the + sign that Rosie F described in her answer. – Brilliand Dec 12 '19 at 23:03
  • 1
    I think I see it now, though her answer is hard to visualise as-is. I'll edit mine. – Chromatix Dec 13 '19 at 0:26
  • 2
    @Chromatix Just to set the record straight, C# is not a variant or descendant of Java, it's a completely separate language, with superficial similarities because it has similar aims and core concepts. Open source and cross-platform compilers for it are also available, as are online tools where you can paste code in and run it, such as tio.run – IMSoP Dec 13 '19 at 14:34
7

(EDIT: substantially revised because I hadn't thought carefully enough about Rosie F's labeling. The result is even cooler!)

Thanks for all the great answers. I would like to add my own solution.

It's key to label squares in the torus, as Rosie F and Brilliand did:

4,2 0,3 1,4 2,0 3,1
1,0 2,1 3,2 4,3 0,4
3,3 4,4 0,0 1,1 2,2
0,1 1,2 2,3 3,4 4,0
2,4 3,0 4,1 0,2 1,3

But we can do more than just label the squares: we can view the labeling as a map (transformation) from the torus to itself!

Suppose we fix the centre cell 0,0 as an origin (and relabel 3 & 4 to -2 & -1 respectively). Let's track what happens to the straight lines under the labeling map. There are 6 straight lines each of 4 cells running through this origin. 6x4+1 = 25: check.

The lines come in 3 pairs:

  • vertical & horizontal for rooks
  • dexter & sinister for bishops (terminology from heraldry: maybe related to the line through which a right-handed swordsman would commonly sweep his sword?)
  • left-turn & right-turn for knights (knight moves forward 2, then turns left or right)

Labelings are completely determined by two values: e.g. where to place 1,0 & 0,1, and we build up everything from there linearly. In particular, Rosie F started with:

1,0 -> -2,1 
0,1 -> -2,-1

This maps both the rook lines to knight lines. Now adding/subtracting these gives:

1,1 -> 1,0
1,-1 -> 0,2

So we are mapping bishop lines to rook lines. And adding another dose of "rook":

2,1 -> -1,1
1,2 -> -1,-1

And hence we are also mapping knight lines to bishop lines.

Since R->N->B->R, we can view knights and bishops as just being rooks in other frames of reference. The number of ways to arrange 5 non-attacking rooks is obviously 5!, so the same must be true for 5 non-attacking knights - and also true for 5 non-attacking bishops!

There are 480 possible labelings (known to their close friends as GL(2,5)). Each gives a frame of reference from which to view the antics of chess pieces. From some, e.g. bishop lines are fixed, while knights and rooks are swapped (e.g. 1,0->-2,-1 & 0,1->1,-2). Others are much more alien, and pieces behave like chimerae (e.g. a combination of vertical rook and dexter bishop). It follows that even for these weird "half-man-half-biscuit" pieces, the number of ways that 5 can appear is exactly 120.

EDIT: generalize to larger boards

What happens if we generalize to different size boards? Let's say we have a pxp toroidal board, where p is an odd prime (in order to avoid division issues). Then through any point Z there are p+1 lines (with gradients 0,1,...,p-1 and infinity. Each line contains p points, including Z. Check: (p-1)(p+1) + 1 = p^2 ok

Any non-singular 2x2 matrix will map the points A (1,0) & B (0,1) to any two points C, D which are not collinear with O (0,0). But this defines a mapping from the lines including OA & OB to the lines including OC & OD, if we ignore the precise points mapped to.

Doing some counting, there are (p^-1)(p^-2p) non-singular matrices and any pair of lines through the origin are mapped to any other pair of lines by (p-1)^2 matrices. There are thus (p-1)p line-to-line mappings, which is what you would expect.

In larger boards, knights will not have a role, as they are "local" in action and can only access 8 squares. But nightriders are relevant to consider. Their lines are not as symmetric as rooks or bishops: a nightrider accesses twice as many lines, or twice as many squares. We would have to compare the left-nightrider and the right-nightrider with rook and bishop to have pieces of equivalent power.

If p=7, then there are 8 lines through any point: rook, bishop and nightrider cover them all. If p=11, then we get 4 more lines due to a unit we can call camelrider. (If a knight's move is (2,1) then a camel's is (3,1).)

Examples for p=5,7,11

| improve this answer | |
  • 1
    The bishops have their own separate mapping, which is also dual to rooks and knights once you apply the appropriate mapping. – Brilliand Dec 13 '19 at 22:11
  • @Brilliand: I'd done my own labeling 1,0->-2,-1 & 0,1->1,-2, which does fix the bishop lines. I only realized later that the choice of labels really does matter, and that Rosie F had done something very different. Hers is a better choice to work with because it shows the equivalence of R,N&B in a single map – Laska Dec 14 '19 at 8:45
1

Here is an answer in simple terms without coding. 120 because assuming there is one way to configure the pieces and the board is torodial and there are 25 squares 5 of which that are occupied by knights leaving 20 left. then the knights can occupy all remaining squares since the board is essentially infinite due to the torodial nature. plus they can occupy the four other squares that knights are currently on by rotating with other knights thus giving each knight 24 other squares to occupy 5*24=120 i believe this works.

| improve this answer | |
  • Hi welcome to chess.stackexchange! I’m not sure I follow your argument. Suppose we have rooks rather than knights. Suppose we have a successful arrangement as you propose as Ra1b2c3d4e5. Then any other square e.g. a2 is attacked by two rooks. Can’t just put Ra1 there, because the other rook attacks it. Certainly can shift Rb2 to b1 simultaneously, but then the arithmetic is different from what you wrote. Sorry if I’ve misunderstood. Thanks so much – Laska Dec 14 '19 at 16:42
  • 1
    Adding together all the different ways each individual piece can be positioned is not the way to go about this. Generally, those values need to be multiplied, not added (to get the number of possible positions). – Brilliand Dec 16 '19 at 20:58
  • If you look at the above solutions every square on the board is covered in one of the solutions so each knight can occupy every square on the board and since there are five knights each knight can a total of four other positions relative to other knights so 25 positions times four additional. The four other knights rotating to other positions thus giving each knight four configurations for each square it can occupy equals 125. Its correct. not eloquent but correct – XCATHADOR Dec 17 '19 at 7:39
  • 1
    @XCATHADOR You just produced the result 125, though. That's not right. (And in general, this question doesn't treat the same position with two knights swapped as a different position.) – Brilliand Dec 18 '19 at 4:38
1

More general answers:

  1. OEIS A172532: Number of ways to place 5 nonattacking knights on an n X n toroidal board.
  2. my book Non-attacking chess pieces (6ed, 2013), page 308, chapter "k Knights on an n x n toroidal chessboard".
| improve this answer | |
  • 1
    Hi Vaclav: welcome and thanks for the link. I gave an overall link to your website here chess.stackexchange.com/questions/27259/…. Simon Norton's interest was in group theory, and 5x5 board is a very interesting special case – Laska Jul 15 at 4:14
  • Btw Vaclav: I sent you an email in May, subject "Chess Math Problem", which I still hope might interest you. I have resent now: pls check your spam folder – Laska Jul 15 at 4:23
  • 1
    I have not received any such e-mail in May or now, not in spam. My e-mail address is kotesovec2(at)gmail.com, please send again. – Vaclav Kotesovec Jul 15 at 6:27
  • OK thanks, I was using an incorrect email address, Vaclav. Have resent. This is a problem in Standard Young Tableaux – Laska Jul 15 at 7:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.