Enumerating full game tree for small board game

Question

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)

Answer 1

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.