Farmer crossing river with wolf, duck, bag of corn

The snippet has been edited for a better version 0.2.0 ...

Simple. The farmer secures the duck under his hat - now there is only the farmer, the wolf, and the bag of corn which the wolf won't be interested in. BTW, how does the farmer keep the wolf from eating him? :-)

Here is a C++ implementation.

// The goal is to move everyone from the west side of the river to the east side of the river
//
// Restrictions: Farmer must always stay with the boat.  Farmer can take at most one passenger
//               in the boat.  Duck and corn cannot be on the same side of the river without the
//               farmer.  Wolf and duck cannot be on the same side of the river without the
//               farmer.
//
// States      : Each of the four objects (wolf, duck, corn, farmer) has a state of 0 or 1. 0
//             : represents that the object's location is on the west side of the river, 1
//               means that the object's location is on the east side of the river.  The
//               combined state of the four objects is an integer value from 0 to 15, inclusive.
//               Each of the four objects has its own bit.  The bits are as follows, from least
//               to most significant bit: farmer, wolf, duck corn.
//
//               Farmer = 0001 = 1 (1 to the 0 power)
//               Wolf   = 0010 = 2 (1 to the 1 power)
//               Duck   = 0100 = 4 (1 to the 2 power)
//               Corn   = 1000 = 8 (1 to the 3 power)
//
//               Initial state = 0 (all objects are on west side of bank)
//               Success state = 15(all objects are on east side of bank)
//
//               1100 = 12 = Farmer and wolf on west side, duck and corn on east side
//               0011 =  3 = Farmer and wolf on east side, duck and corn on west side
//
//               Note that if you flip the 4 bits, you'll have the same configuration of
//               objects on the same side, just the east and west are flipped.  Notice also
//               that 3 + 12 equals 15, so if you want everyone to switch sides, you simply
//               subtract a state from 15 to get its flipped state (15 - 12 = 3).
//
//               This fact comes in handy when checking the legality of a certain state, since
//               illegal states involve the farmer being on one side, and certain pairs of
//               objects being on the other side.  State 12 is illegal.  Therefore state 3 is
//               also illegal since 15 - 12 is 3. State 8 (1000) is legal, so is state 7 (0111),
//               since state X's legality is always the same as state 15 minus X.
//
// Illegal states : An illegal state is any state where the farmer is on one side of the
//                  river and the duck and the wolf, or the duck and the corn, are on the
//                  other side.  The following are the illegal states, where * represents
//                  a wildcard state (i.e. the state does not matter).
//
//                  0001(1), 1001(9) - (*001 - farmer east, wolf and duck west, corn wildcard)
//                  0001(1), 0011(3) - (00*1 - farmer east, duck and corn west, wolf wildcard)
//
//                  So states 1, 3, and 9 are illegal.  Subtracting each of these states from 15
//                  (14, 12, 6 - see explanation above) results in a state that is also illegal.
//                  So the illegal states are {1,3,6,9,12,14}.
//
// Approach:        Starting state is state 0.  Ending state is state 15.  The goal is to get all
//                  objects across the river.  The farmer can be alone in the boat or take one
//                  object.  When the farmer is going from West to East, he attempts to take an
//                  object with him.  When going East to West, he tries to go alone since the goal
//                  is for all objects to end up on the East side.  All states are checked to make
//                  sure they are legal and that the objects have not been in that state before.
//
//                  I made the code as it is in order to possibly change the game a little bit
//                  in the future by adding or subtracting objects or adding and subtracting illegal
//                  combinations.  I think the code/algorithm can be improved.




#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
using namespace std;

enum
{
    FARMER = 0, WOLF, DUCK, CORN, NUM_OBJECTS
};

enum
{
    WEST = 0, EAST
};

const int NUM_ILLEGAL_PAIRINGS = 2;
const int ILLEGAL_PAIRINGS[NUM_ILLEGAL_PAIRINGS][2] = {{WOLF, DUCK},{DUCK, CORN}};
const int FARMER_MASK = (1 << FARMER);        // bit-mask = 0001

const string OBJECT_NAMES[NUM_OBJECTS] = {"farmer", "wolf", "duck", "corn"};

const int START_STATE = 0;  // all objects on west side - 0000
const int END_STATE   = 15; // all objects on east side - 1111



bool state_is_legal(int state)
{
    int mask, object1_side, object2_side;
    int farmer_side = ((state & FARMER_MASK) >> FARMER);

    // iterate through all pairs of objects that don't get along.  If any are
    // on the same side without the farmer's presence, then the state is illegal.
    for (int i = 0; i < NUM_ILLEGAL_PAIRINGS; i++)
    {
        mask = (1 << ILLEGAL_PAIRINGS[i][0]);
        object1_side = ((state & mask) >> ILLEGAL_PAIRINGS[i][0]);
        mask = (1 << ILLEGAL_PAIRINGS[i][1]);
        object2_side = ((state & mask) >> ILLEGAL_PAIRINGS[i][1]);

        // a pair of objects have been selected to test.  If both objects
        // are on the same side and the farmer is NOT on this side, this
        // is an illegal state.
        if(object1_side == object2_side && object1_side != farmer_side)
            return false; // state is illegal.
    }

    return true; // all pairings tests have passed.  State is legal.
}


int switch_sides(int state, int object_to_switch)
{
    int mask = (1 << object_to_switch);
    if(mask & state)
        state -= mask; // object is on east side.  Switch to west side.
    else
        state += mask; // object is on west side.  Switch to east side.
    return state;
}


void Display(int state)
{
    string west_group = "(";
    string east_group = "(";
    int mask = 1;
    for(int i = 0; i < NUM_OBJECTS; i++)
    {
        if(mask & state)
            east_group += OBJECT_NAMES[i] + ",";
        else
            west_group += OBJECT_NAMES[i] + ",";
        mask <<= 1;
    }
    west_group += ")";
    east_group += ")";
    cout << setw(30) << right << west_group << " ~~ " << east_group << endl;
}


bool contains(const vector <int>& states, int value)
{
    int size = states.size();
    for(int i = 0; i < size; i++)
    {
        if(states[i] == value)
            return true;
    }
    return false;
}


int main()
{
    int farmer_side, farmer_switch_state, new_state;
    bool farmer_switch_state_valid, new_state_valid;
    vector <int> states;
    int state = START_STATE; // all on west bank.
    states.push_back(state);

    while(state != END_STATE)
    {
        farmer_side = ((state & (1 << FARMER)) >> FARMER);
        farmer_switch_state = switch_sides(state, FARMER);
        farmer_switch_state_valid = state_is_legal(farmer_switch_state) && !contains(states, farmer_switch_state);
        if(farmer_side == EAST && farmer_switch_state_valid)
        {
            // farmer is on east side, travels to west side alone
            states.push_back(farmer_switch_state);
            state = farmer_switch_state;
            continue;
        }
        for(int i = 1; i < NUM_OBJECTS; i++)
        {
            int object_side = ((state & (1 << i)) >> i);
            new_state = switch_sides(farmer_switch_state, i);
            new_state_valid = object_side == farmer_side && state_is_legal(new_state) && !contains(states, new_state);

            if(new_state_valid)
            {
                // farmer is taking an object with him in the boat ride.
                break;
            }
        }

        if(new_state_valid)
        {
            state = new_state;
            states.push_back(state);
            continue;
        }

        if(farmer_switch_state_valid)
        {
            // farmer is traveling west to east alone because he cannot take an object
            state = farmer_switch_state;
            states.push_back(state);
            continue;
        }

        return 1; // No valid state found.  TODO - handle this without aborting.
    }

    int size = states.size();
    for(int i = 0; i < size; i++)
    {
        Display(states[i]);
    }
    return 0;
}

Mistake in the comments above. Fairly obvious, but will point it out anyway. Lines 15 to 18 should be:

// Farmer = 0001 = 1 (2 to the 0 power)
// Wolf = 0010 = 2 (2 to the 1 power)
// Duck = 0100 = 4 (2 to the 2 power)
// Corn = 1000 = 8 (2 to the 3 power)

Base 2, not base 1, so raising 2 to a power, not raising 1 to a power, which makes no sense.

Nice code. The interesting part is that you are using a heuristic instead of a systematic scanning of the whole graph. This approach may be more flexible for generalized versions of the problem.