Chess

Trinomial Coefficients and Kings

Posted on by John

The term trinomial coefficient is used a couple different ways. The most natural use of the term is a generalization of bionomial coefficients to three variables, i.e. numbers of the form

\frac{n!}{i! \, j! \, k!}

where i + j + k = n. These numbers are the coefficients of yj zk in the expansion of (x + y + z)n.

But there’s another use of the term trinomial coefficient, the one that we are interest in for this post, and that is the coefficients of xk in the expansion of (1 + x + 1/x)n. These numbers can be visualized in a triangle analogous to Pascal’s triangle.

In Pascal’s triangle, each entry is the sum of the two entries above it. In the trinomial triangle, each entry is the sum of the three entries above it.

If you’ve been reading this blog regularly you know I’ve been interested in chess puzzles lately. The thing that make me interested in trinomial coefficients is that they relate to moves of a king on a chessboard.

If you note the number paths a king can take to a square using the minimal number of moves, you get the trinomial triangle. The reason is simple: the number of ways to get to a square equals the number of ways to get there via the square up and to the left, plus the number of ways to get their via the square above, plus the number of ways to get their via the square up and to the right.

Related posts

A crowded little chess puzzle

Posted on by John

Here’s a puzzle by Martin Garnder [1].

Can a queen, king, rook, bishop, and knight be placed on a 4² board so no piece attacks another?

There are two solutions, plus symmetries.

Note that in all non-attacking chess puzzles, the colors of the pieces are irrelevant. In the solutions I chose the piece colors to be the opposite of the square colors strictly for aesthetic reasons.

More chess posts

More Martin Gardner posts

[1] Martin Gardner. Some New Results on Nonattacking Chess Tasks. Math Horizons. February 2001, pp 10–12.

Special solutions to the eight queens problem

Posted on by John

There are 92 ways to place eight queens on a chessboard so that no queen is attacking any other. These fall into 12 equivalence classes. The 92 solutions are all rotations and reflections of these 12 basic solutions.

If you think about the previous numbers a minute, you might wonder why the total number of solutions is not a multiple of 12. There is one particular solution that is more symmetric than the others. So the total number of solutions 92 breaks down into

8 × 11 + 4 × 1.

To illustrate this, let’s look at two fundamental solutions: one that is particularly ordered and one that is particularly disordered in a sense that we’ll get to later on.

Most basic solutions, like the one below, are part of an equivalence class of eight solutions.

You can rotate the board 90° or reflect it about the middle[1], or some combination of both [2]. This amounts to eight possibilities.

This solution, however, is more symmetric.

You can rotate the basic solution, but flipping it over does not create a new solution: a flip produces the same result as two 90° rotations.

It’s curious that there is only one highly symmetric solution to the eight queens problem. When I first saw the problem as a child I expected all the solutions to be highly symmetric. That may be why I wasn’t able to find a solution.

Among the 11 basic solutions that are less ordered, the one shown above is uniquely disordered in the following sense: no three queens lie on a straight line.

The eight queens problem is a problem about restricted straight lines. It says no two queens lie on the same rank, file, or diagonal. But if we look at all straight lines, then of course there is a line through any two queens. In the most orderly solution, every queen is on a straight line with two others. In the least orderly solution, no queen is on a straight line with two others.

In 1900 Henry Dudenay introduced the no-three-in-line problem, looking at ways to place points on a lattice such that no line goes through three points, with no restriction on the slope of the lines. So one family of solutions to the eight queens problem is also a solution to the no-three-in-line problem.

Related posts

[1] It doesn’t matter whether you flip about the horizontal or vertical axis.

[2] In fancy terminology, the action of the dihedral group D8 applied to a solution yields another solution.

The non-attacking bishops problem

Posted on by John

How many bishops can you place on a chessboard so that no bishop is attacking any other bishop?

For a standard 8 × 8 chessboard the answer is 14. In general, for an n × n chessboard the answer is 2n − 2.

Here’s one way to place the maximum number of non-attacking bishops.

To see that the bishops cannot attack each other, I think it’s helpful to imagine extending the chessboard so that each bishop attacks the same number of squares. Then we can see that they miss each other.

Related posts

n-queens in 3D

Posted on by John

It’s possible to place n queens on an n × n chess board so that no queen is attacking any other queen, provided n > 3. A queen is able to move any number of squares in any horizontal, vertical, or diagonal direction. Another way to put it is that the queen can move in any of 8 = 3² − 1 directions, in the direction of any cell in a 3 × 3 grid centered on the queen.

What if we extend chess to three dimensions? Now we have an n × n × n cube. Now a queen is able to move in 26 = 3³ − 1 directions, in the direction of any cell in a 3 × 3 × 3 cube centered on the queen.

Klarner [1] proved that it is possible to place n² queens in an n × n × n cube so that no queen is attacking any other, provided gcd(n, 210) = 1, i.e. provided the smallest prime factor of n is larger than 7. The condition gcd(n, 210) = 1 is sufficient, and it is conjectured to be necessary as well [2].

Klarner constructed a solution as follows: Place the queens on

(i, j, (3i + 5j) mod n)

for i and j running from 1 to n.

One way to visualize the queens in 3D is to draw a 2D grid where each cell contains the vertical coordinate of the corresponding queen. This grid will be a Latin square, and so the 3D queen placement problem is also known as the Latin queen problem.

Here’s a visualization of Klarner’s example.

Note that if you only pay attention to a particular number, you have a solution to the 11 queens problem in a square. That’s because every slice of a 3D solution is a solution to the 2D problem.

I played around with plotting the points in three dimensions. Here’s one view.

A slight rotation of the cube gives a substantially different perspective. This would be better as an animation, available here.

Mathematica code

Here’s the code that made the images above.

Flat grid:

    Grid[
        Table[
            Mod[3 i + 5 j, 11], 
            {i, 0, 10}, 
            {j, 0, 10}
        ], 
        Frame -> All
    ]

Static 3D view:

     ListPointPlot3D[
         Table[
             {i, j, Mod[3 i + 5 j, 11]}, 
             {i, 0, 10}, 
             {j, 0, 10}
          ], 
          BoxRatios -> {1, 1, 1}, 
          PlotStyle -> {PointSize[0.02]}
      ]

Animation:

    Animate[
        ListPointPlot3D[
            Table[
                {i, j, Mod[3 i + 5 j, 11]}, 
                {i, 0, 10}, 
                {j, 0, 10}
            ], 
        BoxRatios -> {1, 1, 1}, 
        PlotStyle -> {PointSize[0.02]}, 
        ViewPoint -> {2 Cos[t], 2 Sin[t], 1}
        ], 
        {t, 0, Pi, 0.05}, 
        AnimationRunning -> True, 
        AnimationRate -> 4
    ]

    Export["klerner_animation.gif", %]

Related posts

[1] D.A. Klarner, Queen squares, J. Recreational Math. 12 (3) (1979/1980) 177–178.

[2] Jordan Bell and Brett Stevens. A survey of known results and research areas for n-queens. Discrete Mathematics 309 (2009) 1–31

A knight’s tour of an infinite chessboard

Posted on by John

Let ℤ² be the lattice of points in the plane with integer coordinates. You could think of these points as being the centers of the squares in a chessboard extending to infinity in every direction.

Cantor tells us that the points in ℤ² are countable. What’s more surprising is that you could count the points using a knight’s move. If you place a knight at the origin, there is a way for him to visit every point exactly once.

It’s possible to tour every point in a 5 × 5 lattice as shown below.

The knight’s next move would take it out of the 5 × 5 block and position it to begin touring a new 5 × 5 block bordering the first block.

You can repeat this pattern, covering ℤ² in a spiral of 5 × 5 squares.

I produced the first two images using Quiver, an application intended for drawing commutative diagrams, though I’ve found it useful for other drawing tasks as well.

The third image was taken from a note by Robert E. Gilman on an article by Norman Anning: A Recreation. The American Mathematical Monthly, Vol. 37, No. 10 (Dec., 1930), pp. 535–538.

Related posts

Queens on a donut

Posted on by John

The eight queens problem is to place eight queens on a chessboard so that no queen attacks another. Because queens are allowed to move any number of spaces horizontally, vertically, or diagonally, this means no queen can be on the same row, column, or diagonal as any other queen.

For example, the following image gives one solution to the eight queens problem. (See the previous post for how I made the chessboard images in this post.)

The eight queens problem has been generalizes many ways, first by considering square chessboards of different sizes. The n-queens problem works on an n by n board. The n-queens problem can be solved for all n greater than 3.

The problem I want to consider here is the toroidal n queens problem. We first curl up our chessboard into a cylinder, then curl join the ends of the cylinder together to make a torus (donut).

checkerboard torus

(I found the image above on TeX StackExchange.)

When we do turn our chessboard into a torus, the rows and columns don’t change. If no two queens were on the same row (column) on the flat chessboard, there still won’t be any two queens on the same row (column) in the toroidal chessboard.

But the diagonals do change, as the following image illustrates.

If we curl our chessboard vertically by joining the left and right edges—no need to imagine the torus for this example, a cylinder will do—then some of the diagonals merge. The queen on the bottom row would be on the same diagonal as the queen in the third row from the top.

George Pólya proved that the toroidal n queens problem has a solution if and only if n is not a multiple of 2 or 3. Not only does the particular solution to the eight queens problem above not extent to a torus, no solution to the eight queens problem extends to a torus because 8 is divisible by 2.

The smallest non-trivial chessboard of size n with n not divisible by 2 or 3 is n = 5. The following solution to the five queens problem remains a solution if you identify the edges, making the board into a torus.

Related posts

How to make a chessboard in Excel

Posted on by John

I needed to make an image of a chessboard for the next blog post, and I’m not very good at image editing, so I make one using Excel.

There are Unicode characters for chess pieces— white king is U+2654, etc.—and so you can make a chessboard out of (Unicode) text.

    ♔♕♖♗♘♙♚♛♜♝♞♟

I placed the character for each piece in an cell and changed the formatting for all the cells to be centered horizontally and vertically. The following is a screenshot of the Excel file.

Chessboard: screenshot from Excel file

The trickiest part is getting the cells to be square. By default Excel uses different units for height and width, with no apparent way to change the units. But if you switch the View to Page Layout, you can set row height and column width in inches or centimeters.

Another quirk is that you may have to experiment with the font to get all the pieces the same size. In some fonts, the black pawns were larger than everything else [1].

You can download my Excel file here. You could make any chessboard configuration with this file by copying and pasting characters where you want them.

When I tested the file in Libre Office, it worked, but I had to reset the row height to match the column width.

Related posts

[1] Thanks to a reply on twitter I now understand why black’s pawn is sometimes outsized. The black pawn is used as an emoji, a sort of synecdoche representing chess. That’s why some fonts treat U+265E, black knight, entirely differently than U+265F, black pawn. The latter is interpreted not as a peer of the other pieces, but as the chess emoji. See the chess pawn entry in Emojipedia.

King of high dimensional space

Posted on by John

rook, king, knight

Which has more mobility on an empty chessboard: a rook, a king or a knight?

On an ordinary 8 by 8 chessboard, a rook can move to any one of 14 squares, no matter where it starts. A knight and a king both have 8 possible moves from the middle of the board, fewer moves from an edge.

If we make the board bigger or higher dimensional, what happens to the relative mobility of each piece? Assume we’re playing chess on a hypercube lattice, n points along each edge, in d dimensions. So standard chess corresponds to n = 8 and d = 2.

A rook can move to any square in a coordinate direction, so it can choose one of n − 1 squares in each of d dimensions, for a total of (n − 1)d possibilities.

A king can move a distance of 0, 1, or −1 in each coordinate. In d dimensions, this gives him 3d − 1 options. (Minus one for the position he’s initially on: moving 0 in every coordinate isn’t a move!)

What about a knight? There are C(d, 2) ways to choose two coordinate directions. For each pair of directions, there are 8 possibilities: two ways to choose which direction to move two steps in, and then whether to move + or − in each direction. So there are 4d(d − 1) possibilities.

In short:

  • A king’s mobility increases exponentially with dimension and is independent of the size of the board.
  • A rook’s mobility increases linearly with dimension and linearly with the size of the board.
  • A knight’s mobility increases quadratically with dimension and independent of the size of the board.

The rules above are not the only way to generalize chess rules to higher dimensions. Here’s an interesting alternative way to define a knight’s moves: a knight can move to any lattice point a distance √5 away. In dimensions up to 4, this corresponds to the definition above. But in dimension 5 and higher, there’s a new possibility: moving one step in each of five dimensions. In that case, the number of possible knight moves increases with dimension like d5.

Related post: A knight’s random walk in 3 or 4 dimensions