Chess and Math Puzzle (nothing to do with CMA)

[Paul Bonham]

A chess puzzle for the mathematically inclined. My solution will be posted next week, I wonder if anyone will come up with the exact number I did (and it is a very specific number).

On an 8 x 8 chess board, you are to place each of the major pieces, including Kings and Queens, and excluding all Pawns, into the central 4 x 4 section of the chess board. Since the Pawns are excluded, this leaves 16 pieces to fit into the 16 central squares. None of the central squares can be empty, all pieces must be placed.

How many UNIQUE ways can this be done such that the two Kings are not next to each other?

NOTE 1: This will eliminate some, but not all, illegal chess positions. More on that in the notes to my solution!

NOTE 2: the word UNIQUE in this context means that THE POSITION OF ALL PIECES RELATIVE TO EACH OTHER is not duplicated in any other position. Pay very special attention to this!

[Paul Bonham]

Solution Part 1: Total Raw Combinations

I guess no one wants to take a stab at this? Well, I'll be posting the solution in parts.

By the way, I'm adding a new constraint which I haven't even figured out yet: Neither the two White Bishops nor the two Black Bishops can be on same-colored squares. This eliminates more of the illegal chess positions (but still not all of them, as will become clear).

In this, Part One, I submit my calculation of the raw number of combinations of the 16 major pieces (8 White, 8 Black, 1 King and Queen each, 2 Rooks each, 2 Knights each, 2 Bishops each) in the 4 x 4 central squares of the chessboard.

This "raw" number doesn't eliminate duplicates nor illegal positions, nor does it account for uniqueness as described in the original post.

Here it is, and if anyone sees an error anywhere, please post your correction! I'm not a mathematician, and there could be error(s) here. The goal is to find the correct solution, hopefully by using just math (see the note at the end of this part about using a computer algorithm).


1. FIND TOTAL COMBINATIONS

First of all, we know we must populate 16 squares. None can be left empty.

Assume we have 16 unique pieces and each piece can appear up to 16 times.

If we draw the number of combinations for this example as a 4 x 4 grid of squares, with the number of possibilities for each square given to each square, this grid becomes:

16 16 16 16
16 16 16 16
16 16 16 16
16 16 16 16

The total number of combinations then becomes 16 to the power of 16 (i.e. 16 x 16 x 16 ... x16, a total of 16 times).

This number is 18,446,744,073,709,551,616 or about 18.5 pentillion.

As another example, the arrangement of 16 pieces, EACH UNIQUE AND APPEARING ONLY ONCE, in 16 squares would give 16! (16 factorial), combinations.

This would be the grid of the central 4 x 4 squares, with multiplication signs to show the numbers are multiplied together:

16 x15 x14 x13
x12 x11 x10 x9
x8 x7 x6 x5
x4 x3 x2 x1

16! = 20,922,789,888,000 combinations. > 20.9 trillion

However, in our problem, we do not have 16 unique pieces, we have 10 unique pieces (there are no pawns, and each White Rook, Black Rook, White Knight, Black Knight, White Bishop, Black Bishop has a twin). Also, the limit for number of times each piece can appear is different for different pieces:

- only one can be a White King
- only one can be a Black King
- only one can be a White Queen
- only one can be a Black Queen
- only 2 can be a White Rook
- only 2 can be a Black Rook
- only 2 can be a White Bishop
- only 2 can be a Black Bishop
- only 2 can be a White Knight
- only 2 can be a Black Knight

From this we know that initially we can place any of the 10 pieces. The question is, how many times can we place any of the 10 pieces until it's guaranteed that we reach a point where we only have 9 unique pieces left to place? Well, if we take the 6 twin Rooks, Bishops, and Knights and distribute them across 6 squares, we will still have all 10 piece types left to choose from. So lets begin our grid this way:

6 x5 x4 x3
x2 x1

Now we only have 1 of each piece type left and they each MUST be placed. So after we place the 7th piece, there are only 9 possible pieces to place. After we place the 8th piece, there are 8 possible pieces to place. After we place the 9th piece, there are 7 possible pieces to place. This continues until the last square, where there can only be 1 possible piece to place.

Therefore for starting out with one each of the 6 twin pieces on each of the first 6 squares (left to right, from top corner), we have this grid of possible combinations:

6 x5 x4 x3
x2 x1 x10 x9
x8 x7 x6 x5
x4 x3 x2 x1 = 2,612,736,000 combinations

IS THIS THE RIGHT ANSWER FOR THIS PART OF THE SOLUTION (finding total number of combinations before elimination of duplicates and adjacent Kings and same-colored Bishops)?

At first glance, it may not seem so, because we restricted ourselves to picking one of 6 pieces (the ones that have twins) in the first 6 squares (going from left to right starting at the top corner). Obviously there are many other ways we could arrange those 6 pieces that have twins.

So lets approach it from that angle: how many ways can we arrange the 6 squares restricted to one of only 6 pieces on the 16-square grid?

This is like asking: on a 16-square grid, how many ways can you arrange 6 X's?

X X X X
X X O O
O O O O
O O O O

The formula for finding the number of combinations of k objects (all the same) you can arrange in a set of n positions is:

C(n,k) = (n!) / (k! * (n-k)!)

A simple example would be if we had 5 squares in which to place 4 X's, the answer would be
(5!) / (4! x 1!) = 120 / 24 = 5

In our example, n is 16 and k is 6.

So our answer will be (16!)/( 6! x 10!) = 8,008

The total ways we can arrange the 6 twin pieces among the 16 squares is 8,008.

And for each way we can arrange them, there are 2,612,736,000 total combinations as was shown above.

This gives 20,992,789,888,000 total combinations. This is the exact number we calculated above for 16 unique pieces each appearing once on 16 squares, i.e. 16 factorial.

This would seem to verify our answer of 2,612,736,000 combinations.


We can verify this one other way. You'll recall that our grid when placing the 6 twin places first before any other pieces was

6 x5 x4 x3
x2 x1 x10 x9
x8 x7 x6 x5
x4 x3 x2 x1 = 2,612,736,000 combinations

Notice in this grid that there is only 1 time that you can choose from among the 10 piece types. Does that make sense? Let's say in the top left corner, instead of choosing one of the 6 twin pieces, we choose instead one of the 4 non-twin pieces. This immediately drops us to 9 piece types left. We never again have 10 piece types left to choose from. If we again choose one of the now 3 remaining non-twin pieces, this immediately drops us to 8 piece types left. All in all, there is only ONE TIME we can choose from all 10 piece types, and there is only 0NE TIME we can choose from 9 piece types, and there is only ONE TIME we can choose from 8 piece types, and there is only ONE TIME we can choose from 7 piece types. There is exactly TWO TIMES we can choose from the 6 twin piece types before we drop down to choosing only 5 of the remaining twin piece types.


From these 3 proofs, I submit that the total number of "raw" combinations, without considering uniqueness or chess legality, allowed by our constraints is 2,612,736,000.


Now.... Let's say you had a very fast computer and a fast algorithm that could go through all these combinations, and for every one determine very quickly whether the combination is a legal chess position (more on this later). Let's say it could do all this at the rate of 1 thousand combinations per second.

It would take 30.24 days of constant running for your computer to process them all and come up with the magic number of how many of them are legal chess positions.

That's a lot of days of constant processing, and very fast processing besides. Also, it doesn't eliminate duplicate combinations, because if it had to do that, the time taken would go up with each new position, as the computer would have to do the fastest possible search of the already existing combinations to determine if there's a duplicate.

Can we somehow determine mathematically how many of them are legal chess positions, and can we eliminate duplicates, without having to iterate them all and analyze each one?

The key will be to eliminate illegal positions first, then eliminate duplicates. As it turns out, duplicate elimination is the easiest part of this problem.

[Bob Gillanders]

Paul, you are insane!

Awwwww.....my head hurts!

LOL, I actually dug up my old math textbook from grade 13, and reviewed the chapter on combinatorics. :( Of course, none of the examples fit the problem percisely, naturally, so after a little time with pencil and paper, looking at the problem logically with a simplied ie. smaller example, brain went flatline!

But being insane also, I took another stab at it. After reading thru you're logic again, the lights went back on.;)

Paul, you're first step of treating all 16 pieces as discrete is brilliant!
The answer is indeed: 16! = 20,922,789,888,000

Now to adjust for the fact that we have duplicates, you divide by the permutations of the duplicates.
ie. 2 white rooks. you divide by 2 ( if 3 white rooks, divide by 6 ie.3x2)
ie. 2 black rooks, divide by 2, etc etc.

So to eliminate all the permutations of all the duplicated pieces,
that would be 2 x 2 x 2 x 2 x 2 x 2 = 64

So to answer your part 1: possible combinations of chess pieces (no pawns) on the 4x4 board including all illegal positions is:

20,922,789,888,000 / 64 = 326,918,592,000

Okay, that's the easy part!

[David Lyall]

Re: Paul, you are insane!

Putting a Black King in the following positions on the 4x4 board and creating an illegal position by putting a White king in an adjacent square gives

1. Corner: 3 illegal positions x 4 corner squares = 12
2. Edge: 5 illegal positions x 8 edge squares = 40
3. Middle: 8 illegal positons x 4 middle squares = 32

This gives a total of 84 illegal positions. All of these positions would be duplicated in placing the White King first and then placing Black king in adjacent square.

Each of the unique 84 illegal positions would have 16-2 = 14 squares to fill with the remainder of the pieces.

The 14 squares can filled in 14! ways. These positions would have the 64 duplicates as well so there are ( 84 x 14! ) / 64 = 114,421,507,200 positions that are illegal due to the kings being on adjacent squares.

[Bob Gillanders]

The next piece of the puzzle!

David, well done! Those calculations look correct to me. So now we are one step closer to solving Paul's puzzle.

Total positions including illegals = 326,918,592,000
Illegals where Kings are on adjacent squares = 114,421,507,200
New maximum = 212,497,084,800. Wow, that eliminated 35%!

Now the problem gets expontentially more difficult when we try to calculate and eliminate other instances of illegal positions. One example would be where both kings are in check simultaneously.

[Paul Bonham]

Re: Paul, you are insane!

Now to adjust for the fact that we have duplicates, you divide by the permutations of the duplicates.
ie. 2 white rooks. you divide by 2 ( if 3 white rooks, divide by 6 ie.3x2)
ie. 2 black rooks, divide by 2, etc etc.

So to eliminate all the permutations of all the duplicated pieces,
that would be 2 x 2 x 2 x 2 x 2 x 2 = 64

So to answer your part 1: possible combinations of chess pieces (no pawns) on the 4x4 board including all illegal positions is:

20,922,789,888,000 / 64 = 326,918,592,000

Hi, Bob... my head hurts too!

OK, so we already have a discrepancy. In the case of the solution I gave, I also couldn't find this specific example on my internet search, so I tried to think it through logically (don't have a math textbook). Looks like something wasn't right in that whole business about

I NOW THINK WE HAVE BOTH ERRED.


Bob, where you write "Now to adjust for the fact that we have duplicates, you divide by the permutations of the duplicates.
ie. 2 white rooks. you divide by 2", did you get that from your textbook? Where is the proof of this method, can you get it from your textbook and give it here? We want to prove each mathematical method we are using.

Hmmmm.... let's try logic again.

Lets say there are just the 2 White Rooks, and the other 14 pieces are unique. In the 4 x 4 grid, lets put one White Rook in the top left corner. This leaves 15 squares to put the other White Rook. Each of these 15 squares represents a duplicate position, because you can switch the White Rooks and nothing changes.

Now clear the grid and put the first White Rook in the next square to the left. There are now 14 squares left to put the other White Rook, because we already considered the top left corner square. That's 14 more duplicate positions.

Now clear the grid and put the first White Rook in the next square to the left. Now we only have 13 squares left to put the other White Rook. Obviously this is a pattern in which we sum 15 + 14 + 13 ... + 1 to get the total number of duplicate arrangements of White Rooks.

So the total number of duplicate arrangements of the two White Rooks are

15 + 14 + 13 + 12 + 11 + 10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 120

This is verified by the formula C(n, k) = n! / k!(n-k)!

where n = 16 and k = 2.

C(16, 2)
= 16! / (2! x 14!)
= (20,922,789,888,000) / (2 x 87,178,291,200)
= 120


Since we have 6 pieces with twins, there are a total of 6 x 120 = 720 duplicate arrangements of the 6 twins.

So instead of dividing 16! by just 64, shouldn't we be dividing it by 720?

This would give 20,922,789,888,000 / 720
= 29,059,430,400 combinations.

This is the new total of "raw" combinations (not eliminating illegal positions).

Does this seem right to you?

[Bob Gillanders]

Whoa, you head must be really hurting!

Paul, no textbooks or formulas. This part is intuitively obvious.:)

Simple example:

3 pieces, a King and 2 rooks. To make the rooks discrete, we'll name them R1 and R2

How many ways can you arrange them? 6

K, R1, R2
K, R2, R1
R1, K, R2
R2, K, R1
R1, R2, K
R2, R1, K

If you drop the distinction between the rook, then those same 6 arrangements become:

K,R,R
K,R,R
R,K,R
R,K,R
R,R,K
R,R,K

And we see now only 3 discrete arrangements. 6/2=3

or to put it even simplier,

R1,R2 becomes R,R
R2,R1 becomes R,R

2 becomes 1

Got it?:)

[Jordan S. Berson]

Re: Whoa, you head must be really hurting!

2 becomes 1

So, the Rooks get married then? :)

This entire puzzle is very intriguing... I'm still pondering it before I post a reply.

In the meantime, since you mentioned "2 becomes 1", I thought I would ask if you have seen the math problem where 1=2? If you haven't seen it, let me know and I'll post it... see if you can spot the easy error ;-)

[Bob Gillanders]

Re: Whoa, you head must be really hurting!

So, the Rooks get married then? :)

This entire puzzle is very intriguing... I'm still pondering it before I post a reply.

In the meantime, since you mentioned "2 becomes 1", I thought I would ask if you have seen the math problem where 1=2? If you haven't seen it, let me know and I'll post it... see if you can spot the easy error ;-)

I haven't seen 1=2 yet, so please indulge us. However back in high school I did have a proof for 3=7, probably a similiar theme. ;)

[David Lyall]

Re: The next piece of the puzzle!

A couple of thoughts.

1) Another type of illegal position would be when the King is in check by more than one piece simultaneously

2) As all the squares must be filled in the Bishop and Rook cannot check from afar so they must be attacking from a square next to the King.

The following diagrams may assist in calculating the permutations and combinations ( S=Square to be filled in by another piece ).

King in Corner Square:

K R S S
R B N S
S N S S
S S S S

King in Edge Square:

R K R S
B R B N
N S N S
S S S S

King in Middle Square:

B R B N
R K R S
B R B N
N S N S

Note 2 to 12 pieces can be attacking the King simultaneously when the King is in the middle square.

I believe there are no discovered check scenarios as this would mean an empty square to allow a 2nd piece to attack from afar.

[Egidijus Zeromskis]

Re: Chess and Math Puzzle (nothing to do with CMA)

NOTE 2: the word UNIQUE in this context means that THE POSITION OF ALL PIECES RELATIVE TO EACH OTHER is not duplicated in any other position. Pay very special attention to this!

4=1, i.e., the rotation of the all pieces by 90/180/270 degrees does not create an unique position, isn't?

[David Lyall]

Re: Chess and Math Puzzle (nothing to do with CMA)

Rotation is a consideration; however, if the chess board is as in a regular game then each of the squares has a designation, ie c3, c4, etc.

With the chess board fixed, the designated squares are filled in with the 16 pieces without creating duplicate or illegal positions.

The duplication comes from having two identical pieces being interchangable and creating the same position which is not to be counted twice. This would not be a factor if each chess piece was different.

[Paul Bonham]

Re: Whoa, you head must be really hurting!

Paul, no textbooks or formulas. This part is intuitively obvious.:)

Simple example:

3 pieces, a King and 2 rooks. To make the rooks discrete, we'll name them R1 and R2

How many ways can you arrange them? 6

K, R1, R2
K, R2, R1
R1, K, R2
R2, K, R1
R1, R2, K
R2, R1, K

If you drop the distinction between the rook, then those same 6 arrangements become:

K,R,R
K,R,R
R,K,R
R,K,R
R,R,K
R,R,K

And we see now only 3 discrete arrangements. 6/2=3

or to put it even simplier,

R1,R2 becomes R,R
R2,R1 becomes R,R

2 becomes 1

Got it?:)

Bob, I had also done your simple example, and the C(n,k) formula works for it:

C(n,k) where n = 3 and k = 2

= 3! / 2! (3-2)!

= 6 / 2

= 3 (same as your answer)

Since every example that I've seen online of this type of question uses the C(n,k) formula, I got sidetracked thinking this is the formula to use.

But to prove that it's not, I had to go beyond that simple example, because as shown above, one could think from just that example that C(n,k) should be used. It seems once you get hooked on that formula, there's a lot of ways to go wrong, as I did twice! One could even conclude that there's a lot of wrong math being done in the real world based on inappropriate use of this formula (and possibly others).


It does come out that your technique is right, and kudos to you for working it out!

Our superfast computer that can generate, analyze, and determine chess legality of 1,000 of these positions per second would now take 3,784 days to come up with the total legal positions!

That's over 10 years of constant processing! All the more incentive to figure this out mathematically, if possible!

[Paul Bonham]

Re: Chess and Math Puzzle (nothing to do with CMA)

Rotation is a consideration; however, if the chess board is as in a regular game then each of the squares has a designation, ie c3, c4, etc.

With the chess board fixed, the designated squares are filled in with the 16 pieces without creating duplicate or illegal positions.

The duplication comes from having two identical pieces being interchangable and creating the same position which is not to be counted twice. This would not be a factor if each chess piece was different.

David, you make a good point about the board notation, so I guess I should stipulate that board notation doesn't need to be considered.

Thanks to Bob, we've eliminated duplicate positions due to the twin pieces, but Egidijus was on the right track with respect to uniqueness.

Here's my explanation of what makes for uniqueness:

Uniqueness means that any arrangement which is a rotation of by 90, 180 or 270 degrees, or a horizontal flip of, or a vertical flip of, or a diagonal flip of another arrangement is NOT unique, because we are not considering North, South, East, West locations as providing uniqueness. This is valid for chess rules, since there are no Pawns and no possibility for Castling in any of these positions. Only the presence of Pawns or possibility of Castling would make direction part of the quality of uniqueness.

Given the above definition of a UNIQUE combination:

Each combination can be rotated 90 degrees to create 1 duplicate.
Each combination can be rotated 180 degrees to create 1 duplicate.
Each combination can be rotated 270 degrees to create 1 duplicate.
Each combination can be flipped along 2 diagonals to give 2 more duplicates.
Each combination can be flipped horizontally to give 1 more duplicate.
Each combination can be flipped vertically to give 1 more duplicate.
Total duplicates: 7.
Including the original makes 8 duplicates.

Therefore when we calculate a final number of legal chess positions, we will need to divide this number by 8 to achieve unique positions.

But this division should be the FINAL step, after eliminating all duplicates due to twin pieces and all illegal positions.

[Paul Bonham]

List (so far) of Illegal and Illogical Positions

A couple of thoughts.

1) Another type of illegal position would be when the King is in check by more than one piece simultaneously

2) As all the squares must be filled in the Bishop and Rook cannot check from afar so they must be attacking from a square next to the King.

The following diagrams may assist in calculating the permutations and combinations ( S=Square to be filled in by another piece ).

King in Corner Square:

K R S S
R B N S
S N S S
S S S S

King in Edge Square:

R K R S
B R B N
N S N S
S S S S

King in Middle Suare:

B R B N
R K R S
B R B N
N S N S

Note 2 to 12 pieces can be attacking the King simultaneously when the King is in the middle square.

I believe there are no discovered check scenarios as this would mean an empty square to allow a 2nd piece to attack from afar.

Good stuff, David, here's a list I had drawn up of all illegal and illogical positions:


Illegal Positions:

(1) all positions in which both Kings are in check simultaneously.

(2) all further positions in which one of the Kings is in check by 3 or more pieces at once (in next section, all double check positions are eliminated).

(3) all positions in which either side has both Bishops on the same color square. Technically, this isn't an illegal position: either side could have lost one of it's Bishops, then promoted a pawn to a Bishop on the same-color squares as it's remaining Bishop. But we will ignore this far-fetched possibility and call it an illegal position.

Also, some of the positions are illegal in in a totally different sense: they can NEVER BE REACHED by the rules of chess. We will distinguish these positions by calling them ILLOGICAL positions, with a nod to Spock.

Illogical Positions:

(4) all further positions in which one of the Kings is in double check.
Why? A double check requires that at least one of the checking pieces is not in a square
adjacent to the King. In our problem, the only possible such piece is a Knight. That means
the Knight would have to have made the last move, which further means it must have unblocked
a discovered check, which means there must be an empty square somewhere between the King and
the discovered check piece. This is not possible in our problem.

(5) all further positions in which one of the Kings is in check by a battery of Queen & Rook
or of doubled Rooks or of a battery of Queen & Bishop.
Why? this one is obvious, if we take the Black King being the one in check, the last move
must have been made by White, and yet the Black King must have already been in check when
White made the move.

(6) all further positions in which one of the Kings is in check by a piece that isn't a Knight
and that is on one of the 4 central squares.
Why? again obvious, the piece must have moved into the central square and yet it's not a Knight, so it could not have made such a move.

(7) all further positions in which one of the Kings is on one of the 4 central squares and
is in check from a Rook .

Why? (this one is very interesting!) the Rook must be on a non-corner perimeter square,
and must have moved there along the same file or rank in which it is checking the
opposing King, meaning it was ALREADY checking the opposing King.

Can anyone come up with any more illegal or illogical positions?


You can see that if pawns were allowed in our problem, the number of possible illegal positions would grow tremendously and would be extremely difficult, if not impossible, to discover.

Consider for example: are there any legal positions in our problem where on all 4 central files there is a White pawn that is "behind" a Black pawn? Remember that the pawns could not have captured any pieces besides the opposing Queen (we assume all pawn promotions are to Queen).