0
\$\begingroup\$

I am trying to list all the possible positions in a small board game (nannon) (using C++)

So far I have decided to split it into two parts, the pieces that are in home positions and end positions (which aren't on the board) and the pieces that are in play (on the board).

Now, I can list the positions when the pieces are on the board with the STL algorithm next_permutation (on a 6 point structure like : point_1 = "White", point_2="empty"......point_5="Black", point_6="empty")

I am left with how to list all the positions of pieces which are off the board.

I have decided to have a set of bins:

white in home position
white in end position
White in play
black in home position
black in end position
black in play

white has three pieces that can be put in any of these bins (e.g 2 in home bin and 1 in play bin), same goes for black, like this:

white in home position = 2
white in end position = 0
White in play = 1
black in home position = 0
black in end position = 1
black in play = 2

Any ideas of how I go about this?

p.s: (i tried just adding the home/end/in-play bins to the "board" structure and running next_permutation but that gives nonsensical positions like black pieces in the home bin. I guess I could just list them ALL and then prune the nonsensical ones but that seems like over kill)

\$\endgroup\$
  • \$\begingroup\$ There's a fixed set of pieces right? Instead of listing the positions and enumerating which pieces can be in them, I might try listing the pieces and enumerating the positions where they can be. That way you don't have to worry about representing empty positions. Also try sorting the pieces by position, to eliminate combinations that differ only by changing the order of pieces. \$\endgroup\$ – Nathan Reed Jul 31 '13 at 22:35
  • \$\begingroup\$ Why are you trying to do this? Are you making a game based on a state engine and want to predetermine all states? If so, it may be way easier to define rules and go from there. Moving between a bunch of predetermined states is unnecessary for many games. \$\endgroup\$ – mobo Aug 1 '13 at 5:55
  • \$\begingroup\$ Thanks Nathan, that really helped. Anyway to give you points for your comment?? \$\endgroup\$ – cleerline Aug 1 '13 at 15:02
  • \$\begingroup\$ @cleerline No, but I posted a (slightly expanded) version as an answer. \$\endgroup\$ – Nathan Reed Aug 1 '13 at 21:35
0
\$\begingroup\$

Instead of listing the positions and enumerating which pieces can be in them, I might try listing the pieces and enumerating the positions where they can be. That way you don't have to worry about representing empty positions.

Another thing to cut down on combinations is to sort the pieces by position, to eliminate combinations that differ only by changing the order of pieces. So if you placed the first piece in position 3, let's say, you wouldn't consider positions 1-3 for the second piece; it would be limited to positions 4 and higher (assuming that only one piece can be in a position). The third piece would be limited to positions past the second piece, and so on. You have to be careful to ensure you have enough positions left to place all the pieces, so there are upper limits on each piece's position as well.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.