Arrange 5 non-attacking knights on a 5x5 toroidal board

Question

The celebrated British mathematician and lover of public transport, Simon Norton, passed in 2019. He was the subject of a wonderful biography. He was not a particular fan of chess, but here is a tiny gem due to him.

• How many ways are there to arrange 5 knights on a 5x5 toroidal chessboard so that none of them attack one another?

“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 he gets 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)?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

(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).)

Answer 6

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

Answer 7

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.