4

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?

6

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.

  • Thanks. What "fancier data structures" could I also use to solve this, please? – Wad Aug 12 at 15:26
  • @Wad A vector of bits instead of a string, or a std::set. You could factor "bank" and "boat" into classes with rules inherent in the class. You can check rules as you add them to reduce duplicate work. And so on. If you were building a general "puzzle solver", some of these would be worth considering. But for this one problem, finding ways to abstract it just makes the solution less clear. – btilly Aug 12 at 16:42

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.