Expert: Josh - 7/30/2008

Question
QUESTION: Suppose you have a game board 3x5. The number of squares is therefore 15. But a piece can't be in the center square - leaving 14 possible positions.

And further suppose you have two identical checkers.

How many unique positions can they be in? (Remember the board is symetrical both horizontally and vertically)

ANSWER: Hi Bill,

Let's label the board as follows:

A B C
D E F
G x I
J K L
M N O

Some observations:
For the first pick, A,C,M,O are indistinguishable.
Similarly, B,N are indistinguishable.
(won't name them all)

Guiding principles:
[P.1] To identify each set of indistinguishable positions,
a) select a square in raster scan order (top to bottom, left to right);
b) reflect the square about the horizontal and vertical axes of symmetry,
c) include all squares highlighted in step b in the current set (headed by the chosen element).
d) delete these squares from the candidate list (make them illegible for selection)

[P.2] The first pick determines the orientation of the board, any symmetry disappears in subsequent selection. (From here on, the position is relative to the first pick)

From P.1, we get
Set 1: {A,C,M,O}
Set 2: {B,N}
Set 3: {D,F,J,L} *assumption is true only if board can be flipped back to front, if this is illegal, you can split this into {D,L} and {F,J} when it matters whether the long edge is to the left of a corner point and a short edge is to the right of a corner point (or vice versa).
Set 4: {E,K}
Set 5: {G,I}

I think I have everything covered.
Now, the first checker can sit in 5 different (unique) positions according to the earlier assumptions.
For the second checker, we are left with (14-1) unique positions by P.2.
Given the checkers are identical, the order in which the squares are chosen does not matter. The number of combination is the product of the two.

---------- FOLLOW-UP ----------

QUESTION: So the answer is 14 x 5 = 70 but I am a bit confused.

Set 3 may be split into two different sets if "(D,L) are always different, but (D,F) are always the same" but isn't that also true of (A,O) and (A,C) ?

Soooooooo, I think the answer for my particular situation is FIVE (not SIX) times 14, so your added comment (whether you are right or wrong) is not relevant in this case.

ANSWER: Hi Bill,

Thanks for the follow-up question. I should apologize for any confusion I may have caused and use this opportunity to find the right answer.

I think you meant to say that "(D,L) are always the same, but (D,F) are always different, because the board has a long edge and a short edge. You are right in saying that the same argument applies to {A,C,M,O} in addition to {D,F,J,L}. So long as the square does not lie on the axes of symmetry (either horizontal, or vertical), a given square is only indistinguishable from one other square given by its "horizontal and vertical" reflection combined. e.g., A and O are indistinguishable, but A and M, for instance, are distinguishable, viz., for A, the long edge is to the left of the vertex, for M, the long edge is to the right of the vertex. So, very well done.

Revising the answer from my previous reply, we have 7 sets of squares to position the checker in the first instance. They are {A,O}, {B,N}, {C,M}, {D,L}, {E,K}, {F,J} and {G,I}.

As stated previously, the first placement fixes the orientation of the board, thus all symmetry is gone for subsequent selections.

The mistake I made last time is not accounting for the fact that two combination like [A,B] and [B,A] are identical as the checkers appear the same. So, we have a permutation problem after all, and we should
proceed as follows.

Suppose we place the first checker at A or O. Since the center square is out of bounds, and the second checker cannot coincide with the square occupied by the first checker, we have 13 squares to choose from.

Next, suppose we place the first checker at B or N. To avoid over counting, we eliminate all positions occupied by the first checker that we have considered thus far from the list of candidate positions. Remember that A and O are indistinguishable. So, we subtract 1 from (15-2) and end up with 12 squares to choose from for the second checker. (We subtract 3 from the total number of squares because we cannot use the center square, and either B or N is assumed to be occupied by the first checker, and either A or O has been used without replacement.)

Repeating this argument, we have progressively less squares to choose from. The number of squares available for the second checker for each of the seven sets are:
13, 12, 11, 10, 9, 8 and 7, respectively.

Add these up, we obtain 70 unique combination.

I hope this clears things up. Thanks for getting to the bottom of this.

---------- FOLLOW-UP ----------

QUESTION: Since the number of follow-up questions is limited, I suggest that you contact me directly at photografr7@yahoo.com

Now that I know the answer is 70 (this problem was driving me crazy), I combined your answer with the second half of the question (the easier half, answer: 10), resulting in a total answer of 70 x 10 = 700!

This is the purpose of all of this: I am a game designer. One of my games looks surprisingly simplistic (as do all my games) but (based on these calculations) the game appears to be remarkable complex!

I don't know the terminology, so I'll call the position of the playing pieces BEFORE the game begins "the initial board position". Chess has ONE initial board position. my game has 700... remarkable!

Answer
Hi Bill,

I would prefer to answer questions in this forum rather than through private correspondence. This way, it's easier for me to adjust the quota and handle these in my own time. Game design requires a lot of software skills, it is something that I struggle quite a bit. Perhaps the transitional effects, rather than the initial conditions, might be a more suitable measure of a game's complexity; without venturing into behavior analysis. Feel free sending in new questions.