12

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
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.
  • 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
11

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.

8

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.

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.

  • 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.

What a strange place the 5x5 torus is.

  • 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
0

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.

  • 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

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.