Calculating number of checkers (draughts) possible positions
| From: | דניאל דנון | Date: | Wed, 22 Jul 2009 21:49:02 +0000 |
| Subject: | Calculating number of checkers (draughts) possible positions | ||
| Groups: | php.general | ||
| Request: | Send a blank email to php-general+get-295718@lists.php.net to get a copy of this message | ||
I am trying to calculate the number of possible checkers position - at first
without including promotion (queen/king).
Each player starts with 12 pieces in his color,
And the whole board has 32 places (64 / 2).
At first glance I thought - each place can be occupied by either black
piece, white piece, or nothing. Which means 3^32 is the answer.
Then I realized it can't be, since there is maximum of 12 pieces in each
color,
And if are for example 10 white pieces (-2), then: +2 empty squares.
I thought about the following - We got minimum of 8 places that aren't
occupied,
So I start with 1 ^ 8 (which is 1)
I got 12 squares that have either white or nothing - which means 1^8 * 2^12
And of course another 12 taken by black or nothing
Which means 1^8 * 2^12 * 2^12 = 2^24
Its not the final number, There are a lot less, I just don't know how to add
it to the equation...
--
Use ROT26 for best security