Thread: Combinatorics: Chessproblem (probably will take some time answering)

Well, hi everybody. I've got kind of a problem I really would appreciate help with. As I am Swiss, some of my expressions might be unusual and I would ask you for your understanding and forgiveness.
Thank you.

In a 8x8 sized chessboard, both black and white play with 16 pieces each, which limits the pieces on board to 32.
Each colour's pieces consist of:

• 8 pawns
• 2 rooks
• 2 bishops
• 2 knights
• a queen
• a king

How many different (and possible) positions exist?
Take into account that:

• The white pawns cannot reach the first rank and likewise, the black pawns cannot reach the eight rank.
• A bishop can only move on half of the squares, either white or black ones (one of each colour moves but on white squares, the other on black squares only).
• White pawns that reach the eight rank and black pawns that reach the first rank can be promoted to either a rook, knight, bishop or queen of the respective colour, independently of the pieces taken prior to the promotion.
• Pawns may only change the file they move in by taking pieces.
• A pawn cannot reach the opposing rank (8 for white, 1 for black) if the opponent's pawn in the file it's moving in is not taken.
• The two kings must not stand next to each other.
• During play, all pieces except for the two kings may be taken.

So yeah, how the heck would I go about solving that problem?
It would have been fairly easy if it were but "32 pieces on a 8x8 board", methinks, but all those "take-into-considerations" really get the best of me.
Can somebody help me? If you can indeed, it is appreciated if you do too.
Thanks in advance.

Originally Posted by CluelesslyDesperate

Well, hi everybody. I've got kind of a problem I really would appreciate help with. As I am Swiss, some of my expressions might be unusual and I would ask you for your understanding and forgiveness.
Thank you.

So yeah, how the heck would I go about solving that problem?
It would have been fairly easy if it were but "32 pieces on a 8x8 board", methinks, but all those "take-into-considerations" really get the best of me.
Can somebody help me? If you can indeed, it is appreciated if you do too.
Thanks in advance.

I don't think anybody, or anything, so far has yet calculated the actual number of different positions some arbitrary chess match can ahve, but just take into account that:

== After the first move, there're already 400 different possible moves;

== There're more than 72,000 possible moves after the second move is done;

== There're already more than 288 billion (288,000,000,000) different moves after the first 4 moves are made...

As you can see, your question is probably very hard to completely answer it.

Tonio

That's not what he means.

He means you've a finite number of pieces, and a finite number of places to put those pieces - there's a calculable amount of positions.

What you're thinking of is the number of possible games that can be played.

CD's question, while difficult, is by no means impossible...


eg. if you have one king - there are 64 different ways you can set the board up...

Exactly, thank you, Unenlightened.

Maybe I was not clear enough (sorry about that):
The question is not in how many ways you can play chess (is that even calculable?) but in how many valid ways you can set the board up.

E.g. If we add a king of the opposing colour to Unenlightened's example, we would have a valid game with a total of 3'612 different possible positions but 0 possible next moves (draw due to insufficent material) and a huge amount of different plays that could have led to this (I'm not even attempting to calculate that - for the very reason you mentioned, tonio).

Unfortunately, you can set up the board with all pieces and no promotions, but also with pieces taken (until you have but the two kings left) and no promotions or with taken pieces and promoted pawns, which makes it much more complex. And either of the three ways, there are still those annoying rules the pawns come with - which, however, only matters in the latter two situations.

I think this problem can be solved but you're right it will take a lot of time. I'm cracking open my combinatorics book again. A good first step would be to calculate a large and incorrect number just to get started. Then start thinking about incorporating the rules of the game. What about En passant?

En passant - Wikipedia, the free encyclopedia

This is a cool problem...if you're not in school...sorry!

Why would en passant matter? I don't think it's affecting the amount of positions there are.

And what do you mean by "large and incorrect number"?
I was attempting to solve it quite the other way 'round (start with the two kings, then add and re-remove pieces until you've got all combinations, calculate the valid positions for each combination seperately, then summarize) but especially the pawns got me.
Mind explaining?

En passant does not matter I was thinking of this move by move instead of piece by piece! The problem is easier than I thought it was.

What do you have so far? How are you 'attacking' this problem?

You have 64 squares and you choose 32 to place the pieces on. If one of the pieces is lost during play then would it become 64 squares choose 31 pieces?

N = C(64,32) + C(64, 31) + ... + C(64,2) + C(64,1) + C(64,0)

The number N is too large:

"During play, all pieces except for the two kings may be taken."

So would

N - [C(64,1) + C(64,0)]

satisfy the two king rule?

Have you covered the principle of inclusion and exclusion?

What do you mean by "satify the two king rule"?
If you mean it prevents having less than two pieces in play, yes.
If you're saying the amount of positions in a King-King-Game therefore equals C(64,2), however, then I think I'm disagreeing.

Anyway, I've added my attempt (for the sake of lucidity attached as a .doc).
It's a good thing you're saying it's easier than you first thought because if it's easy, that'll probably mean I'm thinking the wrong way (added my strain of thoughts to the .doc as well so you can figure out where).
As you can see, I get stuck pretty early.

EDIT: Documents now reuploaded

Are illegal positions allowed? eg. May two kings stand beside one another?

I can't open your doc to have a look, because Word isn't supported on my computer...


To start off, I'd suggest choosing which squares will be useable 64C32, then focus only on the fillable squares (which can, of course, still be filled by a blank square).

(how do you delete posts?)

The two kings must not stand next to each other.

No, no illegal positions. (Except both kings checked/mated at the same time, as you can't calculate that, can you?)
Reuploaded the .doc and added a .pdf.

I think you need to simplify your problem. This seems to be getting more complicated as it goes along. How about you solve it for the simplest set of conditions first, then amend it.


You have 64 squares. 32 pieces to put on them. Anywhere you choose.
There are 4 unique pieces (the white king and queen, and the black queen and king). Two of these MUST be on the board, the other two may be absent.
Four sets of two identical pieces (the black and white rooks, and the black and white knights). Again these may or may not be on the board.
Two sets of pieces (the bishops) one of which can occupy only black squares, the other white.
Then you have two sets of 8 identical pieces, each group of which cannot occupy a certain 8 squares.

I think the problem is more than complicated enough to start out, without ever considering mating or 'en passant'.

Then I'd suggest that if you get that, you should maybe be able to manipulate your answer to satisfy extra conditions.

You're right I have made a mistake. It is sad how fast your knowledge evaporates when you graduate.

For the kings the permutations are ordered lists P(n,k) = n!/(n-k)!

The C(n,k) = n!/[k!(n-k)!] counts the number of unordered lists. By counting the number of unordered lists I was under counting the number of permutations. For instance, I was counting a black king on A1 with the white king on h1 as an identical arrangement with a white king on A1 and the black king on h1.

I checked your reasoning and I agree the number of chess arrangements for only two kings is 3,612. Also notice:

C(64,2) = 2,016 we know this number is wrong.
P(64,2) = 4,032 where we assume two kings can be next to each other.

You calculated 3,612 arrangements if we follow the rule that no two kings are next to each other. That is P(64,2)-420, I do love a good math high...thanks for the reminder!

[HTML]http://en.wikipedia.org/wiki/420_(cannabis_culture)[/HTML]

For three pieces I am still excluding the 420 king next to king arrangements but now we have another piece floating around. It will be some multiple of 420 that I need to shave off. The third piece can be one of two colors white or black. The third piece can be one of five different pieces: a queen, a rook, a knight, a bishop or a pawn. Lastly it can be placed on any of the remaining 62 squares not already occupied.

However, we have now over counted with the pawns because neither side can have pawns on the first or last row. If a pawn makes it to the other side of the board it is no longer a pawn, because it becomes a different piece in an arrangement we have already counted. Therefore the pawns travel on 16 fewer squares. It shouldn't matter yet which diagonal the bishop travels on because combined the bishops travel on all the squares. For three pieces the total number of legit arrangements is

2[5(62)-16][P(64,2)-420]...I think...but there has to be a better/correct way.

Maybe after we do four pieces we can find a general method. This is a difficult problem but I'm in too deep now to quit. The general rule in chess is that both kings cannot be in check at the same time the "two kings must not stand next to each other." is an example of the general rule.

Let me know what you think.

"Lastly it can be placed on any of the remaining 62 squares not already occupied. "

Meaning you're allowing the possibility for one of the kings to be in check?
Does this then lead to another amendment/complication whereby the 'checking piece' must have been able to legally move to the square from which it is currently checking?

"If a pawn makes it to the other side of the board it is no longer a pawn, because it becomes a different piece in an arrangement we have already counted."

An arrangement you have already counted?
So you're including the possibility, for example, of having 20 rooks on the board in your list of positions?

"Meaning you're allowing the possibility for one of the kings to be in check?"

Yes, 1 king in check is possible and we are also counting the checkmates for example, a white king at A1 with a black queen on B2 and the black king on C3 would be checkmate.

"Does this then lead to another amendment/complication whereby the 'checking piece' must have been able to legally move to the square from which it is currently checking?"

No, and I understand where you are coming from because I had the same thought process initially. I was thinking of this move by move instead of piece by piece. The problem is how many different (meaning unique) and possible (the rules, pieces and board size are the problem's boundary conditions) positions exist?

If we were to do this move by move the problem would be how many different and possible chess games can we play? That is an entirely different problem and to solve it I would use a lot of graph theory. Our problem is how many unique positions (arrangements) of chess pieces we can place on the board. That is why this is a piece by piece instead of a move by move problem.

“["If a pawn makes it to the other side of the board it is no longer a pawn, because it becomes a different piece in an arrangement we have already counted."

An arrangement you have already counted?
So you're including the possibility, for example, of having 20 rooks on the board in your list of positions?]”

No, and the trick I've learned with these problems is to find your boundary conditions (big macro picture thinking) and then build from the bottom (local micro thinking).

Given the constraints of the problem are 20 rooks on the chess board possible?

If a pawn makes it to the other side of the board it is technically a knight, a bishop, a rook or a queen. Therefore counting a pawn on the last row is not possible because they are no longer considered as pawns on the last row. If we tried to we would technically be counting 1 of the 4 other pieces twice.

Something else to think about is if we have 5 black rooks and 5 white rooks are there more unique arrangements than if we only had 10 white rooks?

We start with 2 rooks how many rooks on a chess board are possible?

How many pawns can make it to their last row? Now add 2 or 1 for the pawns who become queens.