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.

Quote:

http://img340.imageshack.us/img340/81/chessboard.jpg
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.

A mistake (one of many no doubt)

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.

Move by Move vs. Piece by Piece and Boundary Conditions

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