Generating all possible permutations in the fox, goose and beans problem

Question

I have learned graph theory, and am using it to solve the classic Fox, goose and bag of beans puzzle. If we consider that there are three locations for each of the fox (X), goose (G), farmer (F) and beans (B) (near side of river, in the boat, far side of the river), and there are four characters, there are hence 4^3 = 81 combinations. Two of these combinations would be

(Near)    (Boat)    (Far)
F,G,B,X     -         -

(Near)    (Boat)    (Far)
 B,X        F,G        -

...for the starting state and the state when the farmer and the goose have entered the boat respectively.

I want to generate all of these states programatically (in C++, but that is beyond the point), but simply cannot get my head around how to do it. (I know that some of these 81 possible states will be invalid (e.g. that with all characters in the boat at once) but I can search for those and remove them afterwards.)

I am well aware of binary and how I get 81 combinations, and am aware using C++ I could generate all combinations of the characters F,G,X,B, but still cannot figure how to add the three "locations" into this.

Can someone please advise?

Answer 1

Start with deciding how to represent the state.

A simple approach is to say that the state at a location is a string of length 4 in which each character is one of FGBX_. There are three locations, so your starting position is ['FGBX', '____', '____'] and your desired ending location is ['____', '____', 'FGBX'].

And now you can simply have logic that looks like this:

for (f_pos = 0; f_pos < 3; f_pos++) {
   for (g_pos = 0; g_pos < 3; g_pos++) {
       for (b_pos = 0; b_pos < 3; b_pos++) {
           for (x_pos = 0; x_pos < 3; x_pos++) {
               construct state
               if (! check_bank(state[0])) {
                   continue;
               }
               if (! check_boat(state[1])) {
                   continue;
               }
               if (! check_bank(state[2])) {
                   continue;
               }
               do what you want with the valid state
           }
       }
    }
}

There are fancier ways to tackle the problem and fancier data structures, but for a beginning programmer this is hopefully a good approach.