Possibly Challenging: How do I implement solving logic in this puzzle solver program?

Question

I am trying to make a program that solves the Japanese puzzle game "the River IQ Test" I know, I could just look up the solution but that wouldn't be fun and educational now would it? :)

Here is the objective of the game:

Using a raft, that the user can transport people across a river, the user must transport all the people from the left side side to the right side. Each time the raft is used, it stays on the other side until someone from that side pilots it over to the other side again to get more people.

There are the following people on the left side starting out:

• 1 Prisoner
• 1 Policeman
• 1 Father
• 2 Sons
• 1 Mother
• 2 Daughters

Here is the hierarchical structure of classes:

Passenger

• Pilot
  • Parent
    • Mother
    • Father
  • Policeman
• Prisoner
• Child
  • Daughter
  • Son

the following rules must be obeyed:

• only 2 people on the raft at a time.
• only the Policeman, Father, and Mother can pilot the raft
• the prisoner cannot be placed the raft or either side of the river in the presence of other people, without the presence of the policeman.
• the father cannot be on the raft or on either side of the river, with either daughter, without the presence of the mother.
• the mother cannot be on the raft or on either side of the river, with either son, without the presence of the father.

What i need to accomplish yet is:

• logic that uses trial-and-error solving logic until it solves the puzzle
• logic that prints the final successful solution
• logic that checks to see if everyone made it to the other side.

Here is my current code:

Program Class (Solving Logic should go here)

class Program
{
    Side _leftSide = new Side(Side.RL_Side.RL_LeftSide);
    Side _rightSide = new Side(Side.RL_Side.RL_RightSide);
    Raft _myRaft = new Raft();
    static void Main(string[] args)
    {
        // TODO: put systematic trial-and-error solving logic here
        // TODO: make sure that successful solution is printed to console



        Console.ReadLine();
    }
}

PassengerList Class

public class PassengerList : List<Passenger>
{
    public bool CheckRulesObeyed()
    {
        bool isPoliceman = isPresent<Policeman>();
        bool isPrisoner = isPresent<Prisoner>();
        bool isFather = isPresent<Father>();
        bool isSon = isPresent<Son>();
        bool isMother = isPresent<Mother>();
        bool isDaughter = isPresent<Daughter>();
        // ----------------------------------------------
        bool isPrisoner_NonPoliceman = (isPrisoner && (isFather || isMother || isDaughter || isSon));

        bool isPrisonerRuleViolated = (!(isPoliceman && isPrisoner) && isPrisoner_NonPoliceman);
        bool isDaughterRuleViolated = ((isFather && isDaughter) && !isMother);
        bool isSonRuleViolated = ((isMother && isSon) && !isFather);

        bool AreAllRulesObeyed = !(isPrisonerRuleViolated && isDaughterRuleViolated && isSonRuleViolated);

        return AreAllRulesObeyed;
    }

    private bool isPresent<T>() where T: Passenger
    {
        foreach (Passenger p in this)
        {
            if (p is T)
                return true;
        }
        return false;
    }
}

Side Class (as in, side of the river)

public class Side
{
    public enum RL_Side
    { 
        RL_RightSide,
        RL_LeftSide
    }

    public RL_Side _whichSide;

    public PassengerList _myPeople;

    public Side(RL_Side side)
    {
        _whichSide = side;
        _myPeople = new PassengerList();

        // left side starts with all the people
        if (_whichSide == RL_Side.RL_LeftSide)
        {
            _myPeople.Add(new Prisoner());
            _myPeople.Add(new Policeman());
            _myPeople.Add(new Father());
            _myPeople.Add(new Son());
            _myPeople.Add(new Son());
            _myPeople.Add(new Mother());
            _myPeople.Add(new Daughter());
            _myPeople.Add(new Daughter());
        }
    }

    public bool didEveryoneMakeItToRightSide()
    {
        if (_whichSide == RL_Side.RL_RightSide)
        { 
            // TODO: implement logic that checks and returns if everyone is on the right side.

        }
        return false;
    }
}

Raft Class

public class Raft
{
    public Side _mySide;
    public PassengerList _myPassengers;

    public void ChangeSides(Side Destination)
    {
        _mySide = Destination;
    }

    public bool LoadRaft(Pilot myPilot, Passenger myPassenger)
    {
        bool areRulesObeyed = true;
        _myPassengers.Add(myPilot);
        _myPassengers.Add(myPassenger);

        areRulesObeyed = _myPassengers.CheckRulesObeyed();

        if (areRulesObeyed == false)
        {
            UnloadRaft();
        }

        return areRulesObeyed;

    }
    public void UnloadRaft()
    {
        foreach (Passenger p in _myPassengers)
        {
            _mySide._myPeople.Add(p);
            _myPassengers.Remove(p);
        }
    }
}

Answer 1

I take it that you have never learned PROLOG. These problems are classic in PROLOG and more importantly PROLOG deals only with the essence of the problem. When I saw logic and puzzle in the title it was obvious that you needed a logic language. I know you asked for C#, but this is not a OO problem, as you said it is a logic problem.

See Prolog Programming in Depth pg.229 Section 8.3. MISSIONARIES AND CANNIBALS Notice that the solution is smaller than all of the code you have in the question. Don't get me wrong, many years ago I was in the same boat, pun intended.

Some of the best programmers I know work on problems like this not for the solution but because to solve them on their own they know they will learn something important that they can use latter. Take a few months to understand how PROLOG solves this and you will be much better off than someone giving you suggestions. If you don't understand recursion and how AI solves problems you mostly will by the time you get the solution.

EDIT

Is C# incapable of doing that kind of problem solving, though?

PROLOG has a built in inference engine and back-chaining which is what does the work of finding the solution given the rules. You could create one from scratch, which would be harder than solving your initial problem, however there is an open-source implementation of PROLOG in C#, C#Prolog by John Pool. While you could look at the source code to understand how PROLOG works, the code is heavily optimized so it is not easy to understand unless you understand PROLOG first.

If you know F# or a functional language, How to implement a prolog interpreter in a purely functional language? might help.

Basically the problem boils down to creating a set of rules and then trying combinations of the rules until you get a result that satisfies all of the rules.

Start with these keywords and phrases, searching the internet and questions here.

Unification
Syntactic unification
Back-chaining
Inference engine
How prolog works