Using MATLAB with Chessboard arrangements problem

4 次查看（过去 30 天）
Mr.Fritzy cat
Mr.Fritzy cat 2011-5-6
I'm trying to create codes that can calculate the possibility of chessboard arrangements. The board is 8x8 colored squares. Each player has 8 pawns, 2 knight, 2 rooks, 2 bishops, 1 king and 1 queen. All pieces can be lost.
Please suggest how to write codes to calculate the number of board configurations.
  10 个评论
显示 8更早的评论
Will Dampier
Will Dampier 2011-5-9
@Andrew: Yeah, at least it wasn't a copy-paste of my hand-out ... those are always the worst.

请先登录，再进行评论。

请先登录，再回答此问题。

采纳的回答

Sean de Wolski
Sean de Wolski 2011-5-6
All this nerd can say is: Good luck on your incredibly difficult project!
ps. Look at John's Variable Precision Integers on the FEX. You're going to need it.
  3 个评论
显示 1更早的评论
Sean de Wolski
Sean de Wolski 2011-5-6
Yeah, even vpi can't handle that:
>> ten = vpi(10);
>> ten^(ten^50)
??? Error using ==> vpi.power at 36
the exponent must not be larger than 2^53
Error in ==> vpi.mpower at 39
b = a.^k;
Walter Roberson
Walter Roberson 2011-5-6
It wouldn't be possible to write them all down... not enough elementary particles in the Universe.

请先登录，再进行评论。

更多回答（4 个）

Walter Roberson
Walter Roberson 2011-5-7
By the way: It has been shown that for sufficiently large problems such as this, as long as "Moore's Law" continues to hold, that you are better off waiting to start the computation.
If you have a particular amount to invest, then roughly 18 months from now, that amount would buy you twice the processing power and thus get the solution twice as quickly. If your computation was going to take 36 months, waiting those 18 months before starting would allow you to finish at the same time, and if your computation was going to take more than 36 months, then waiting those 18 months to start would get the result sooner. But roughly 36 months from now processors will be twice as fast again, so if your computation is going to take more than 72 months, you are better off waiting 36 months before starting... but then you might as well wait 48 months and buy the faster processors available then.
The longer your program would take on today's processors, the longer you should wait to start in order to finish sooner !!
As the computation that is proposed would take more than twice the expected lifetime of the universe, you are best off not starting it within the lifetime of this universe at all, and to instead dedicate your efforts to figuring out how to construct the next universe as purpose-built computer hardware to solve your problem.
Andrew Newell
Andrew Newell 2011-5-8
If the positions don't need to be legal, you can use combinatorial calculations. For example, let's first suppose that you can't remove any of the pieces. The number of possible positions for the White king is 64. When this king has chosen his spot, the other king has only 63 positions. Thus, there are 64*63 ways the two kings can be arranged. Now look at the white bishops. If you could tell the difference between them, you could say that there are 62*61 combinations of bishop positions. However, they are identical, so for each position there is another that looks the same because the two bishops have been swapped. Thus, there are (62*61)/2 different positions. This can be calculated using the MATLAB function nchoosek:
nchoosek(62,2)
ans =
1891
The total number of positions for the two kings and the two white bishops is the product:
64*63*nchoosek(62,2)
ans =
7624512
In the same way you can keep choosing positions for pieces until all the pieces are accounted for.
EDIT: I got the reasoning below wrong the first time. Here is the corrected version:
Suppose you can remove pieces. The white king has 65 choices: one off the board and 64 on. If White is off the board, the black king still has 65 choices. If White is on the board, there are 64 choices for the black king - 63 on the board and one off. The sum of the possibilities is
1*65 + 64*64
ans =
4161
If the two pieces are identical, e.g., two White knights, there are 65 cases where one piece is off the board and one is on, while the number of positions must be divided by two when both are on the board:
1*65 + 64*63/2
ans =
2081
  9 个评论
显示 7更早的评论
Walter Roberson
Walter Roberson 2011-5-10
You have to be careful with the "65", in that any number of pieces can be in that 65th spot. Makes the combinatorics harder to handle.
Andrew Newell
Andrew Newell 2011-5-10
Right - I slipped up with the two knights (another edit).

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2011-5-9
11530507514326328290083073687940191225693801
if the empty board is included.
(The solution is at most 3 lines of Maple, and once the second line has been seen, it becomes obvious why it can be reduced to 1 or 2 lines.)
  11 个评论
显示 9更早的评论
Andrew Newell
Andrew Newell 2011-5-10
I'm surprised that this does seem to handle the off-board cases correctly, but your expression does agree with my analysis for just two knights.
Bjorn Gustavsson
Bjorn Gustavsson 2011-5-10
Walter, just to throw a spanner in the works: About (==exactly) half the pawns can reach the eight (or first) row...
...and then be promoted.

请先登录，再进行评论。

Will Dampier
Will Dampier 2011-5-10
Now, 15 hours after the deadline I've finally gotten all submissions I'll post my solution based on Andrew's solution. Its much shorter, simpler, faster and easier to understand then my original method and gives nearly an identical answer.
The general idea is that when the board is empty and I have a black king in my hand there are 64+1 (64 on the board and 1 off) places I can put it. For the black queen there are 63+1 remaining places ... assuming I put the king down on the board, otherwise there are 64+1 places. So the number of places for the black queen is 63+1 + 64+1.
When I go to put down the black knights there are 62+2 remaining. Since they're indistinguishable the number of combinations is nchoosek(62+2,2). Again this is assuming the black king and black queen were put down.
So assuming we have a count of the number of pieces in each class we can easily generalize this. If N is the number of pieces already placed, M is the number of items in this class and C is the number combinations:
C = 0;
for k = (64-N):64
C = C+nchoosek(k+M, M);
end
So the entire thing can be implemented as:
iboard = [2,3,4,5,6,4,3,2,ones(1,8),zeros(1,32),-ones(1,8), ...
-2,-3,-4,-5,-6,-4,-3,-2];
%count the pieces ... could've easily just started here
class_counts = histc(iboard, -6:6);
class_counts(7) = []; %remove the zeros
num_places = zeros(size(class_counts));
for i = 1:length(class_counts)
%go through each piece type
rem = 64-sum(class_counts(1:i)); %calculate the number of remaining places
%since pieces can also be lost: rem+class_num
for k = rem:64
%need to deal with the issues of when previous pieces are 'missing'
num_places(i) = num_places(i)+nchoosek(k+class_counts(i), ...
class_counts(i));
end
end
%number of configurations is the product of these.
num_boards = prod(num_places);
This gives a result of ~7.79E58 which generally makes sense. Most of the estimates of number of legal boards is ~10^47. So our superset should be much larger.
  6 个评论
显示 4更早的评论
Will Dampier
Will Dampier 2011-5-10
although simply removing it gives an estimate that is far too low ...

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Conway's Game of Life 的更多信息

标签

产品

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by