StateSpaceRepresentationFollowingTheMathematicalDescription

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace StateSpaceRepresentationFollowingTheMathematicalDescription
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Operator> operators = new List<Operator>();
            operators.Add(new MoveMonksAndCannibals(0,1));
            operators.Add(new MoveMonksAndCannibals(0,2));
            operators.Add(new MoveMonksAndCannibals(1,0));
            operators.Add(new MoveMonksAndCannibals(2,0));
            operators.Add(new MoveMonksAndCannibals(1, 1));
            State startState = new MonksAndCannibalsState();
            StateSpaceRepresentation monksAndCannibalsProblem = new StateSpaceRepresentation(startState, operators);
            BackTrack bt = new BackTrack(monksAndCannibalsProblem);
            Node terminalNode = bt.GraphSearch();
            if (terminalNode == null) Console.WriteLine("There is no solution");
            else
            {
                Console.WriteLine("A solution is:");
                terminalNode.PrintPath();
            }
            Console.ReadLine();
        }
    }
    /// <summary>
    /// The common interface for states of the state-space representation
    /// </summary>
    abstract class State
    {
        public abstract bool IsState();
        public abstract bool IsGoalState();
        public override abstract bool Equals(Object a);
        public override int GetHashCode() { return base.GetHashCode(); }
    }
    /// <summary>
    /// The common interface for operators of the state-space representation
    /// </summary>
    abstract class Operator
    {
        public State Operate(State a)
        {
            if (!PreCondition(a)) return null;
            State b = operate(a);
            if (!PostCondition(b)) return null;
            return b;
        }
        public abstract bool PreCondition(State a);
        protected abstract State operate(State a);
        public abstract bool PostCondition(State a);
        public bool IsApplicableOn(State a)
        {
            if (!PreCondition(a)) return false;
            State b = operate(a);
            if (!PostCondition(b)) return false;
            return true;
        }
    }
    class StateSpaceRepresentation
    {
        State startState;
        List<Operator> operators;
        public StateSpaceRepresentation(State startState, List<Operator> operators)
        {
            this.startState = startState;
            this.operators = operators;
        }
        public bool IsState(State state) { return state.IsState(); }
        public State GetStartState() { return startState; }
        public bool IsGoalState(State state) { return state.IsGoalState(); }
        public List<Operator> GetOperators() { return operators; }
    }

    /// <summary>
    /// Monks and Cannibals Problem
    /// Note that this class is immutable!
    /// </summary>
    class MonksAndCannibalsState : State
    {
        int monksOnLeft, cannibalsOnLeft, boat, monksOnRight, cannibalsOnRight;
        public int MonksOnLeft { get { return monksOnLeft; } }
        public int CannibalsOnLeft { get { return cannibalsOnLeft; } }
        public int Boat { get { return boat; } }
        public int MonksOnRight { get { return monksOnRight; } }
        public int CannibalsOnRight { get { return cannibalsOnRight; } }

        public MonksAndCannibalsState(int monksOnLeft, int cannibalsOnLeft, int boat, int monksOnRight, int cannibalsOnRight)
        {
            this.monksOnLeft = monksOnLeft;
            this.cannibalsOnLeft = cannibalsOnLeft;
            this.boat = boat;
            this.monksOnRight = monksOnRight;
            this.cannibalsOnRight = cannibalsOnRight;
        }

        // this creates the start state
        public MonksAndCannibalsState()
        {
            monksOnLeft = 3;
            cannibalsOnLeft = 3;
            boat = 1; // 1: left, -1: right
            monksOnRight = 0;
            cannibalsOnRight = 0;
        }
        public override bool IsState()
        {
            return monksOnLeft + monksOnRight == 3 &&
                cannibalsOnLeft + cannibalsOnRight == 3 &&
                monksOnLeft >= 0 && monksOnLeft <= 3 &&
                cannibalsOnLeft >= 0 && cannibalsOnLeft <= 3 &&
                monksOnRight >= 0 && monksOnLeft <= 3 &&
                cannibalsOnRight >= 0 && cannibalsOnRight <= 3 &&
                (boat == 1 || boat == -1) &&
                (monksOnLeft >= cannibalsOnLeft || monksOnLeft == 0) &&
                (monksOnRight >= cannibalsOnRight || monksOnRight == 0);
        }
        public override bool IsGoalState()
        {
            return monksOnRight == 3 && cannibalsOnRight == 3 && boat == -1;
        }
        public override bool Equals(object obj)
        {
            MonksAndCannibalsState other = (MonksAndCannibalsState) obj;
            return this.monksOnLeft == other.monksOnLeft &&
                this.cannibalsOnLeft == other.cannibalsOnLeft &&
                this.boat == other.boat &&
                this.monksOnRight == other.monksOnRight &&
                this.cannibalsOnRight == other.cannibalsOnRight;
        }
        public override int GetHashCode()
        {
            return (monksOnLeft.GetHashCode() * 1 +
                cannibalsOnLeft.GetHashCode() * 3 +
                monksOnRight.GetHashCode() * 5 +
                cannibalsOnRight.GetHashCode() * 7) * boat;
        }
        public override string ToString()
        {
            return monksOnLeft + ", " + cannibalsOnLeft + ", " + boat + ", " + monksOnRight + ", " + cannibalsOnRight;
        }
    }
    class MoveMonksAndCannibals : Operator
    {
        int numberOfMonksToMove, numberOfCannibalsToMove;
        public MoveMonksAndCannibals(int numberOfMonksToMove, int numberOfCannibalsToMove)
        {
            this.numberOfMonksToMove = numberOfMonksToMove;
            this.numberOfCannibalsToMove = numberOfCannibalsToMove;
        }
        public override bool PreCondition(State a)
        {
            MonksAndCannibalsState state = (MonksAndCannibalsState)a;
            if (state.Boat == 1) // the boat is on the left side
            {
                return state.MonksOnLeft >= numberOfMonksToMove &&
                       state.CannibalsOnLeft >= numberOfCannibalsToMove;
            }
            else // the boat is on the right side
            {
                return state.MonksOnRight >= numberOfMonksToMove &&
                       state.CannibalsOnRight >= numberOfCannibalsToMove;
            }
        }
        protected override State operate(State a)
        {
            MonksAndCannibalsState state = (MonksAndCannibalsState)a;
            int monksOnLeft, cannibalsOnLeft, boat, monksOnRight, cannibalsOnRight;
            monksOnLeft = state.MonksOnLeft;
            cannibalsOnLeft = state.CannibalsOnLeft;
            boat = state.Boat;
            monksOnRight = state.MonksOnRight;
            cannibalsOnRight = state.CannibalsOnRight;
            if (boat == 1) // the boat is on the left
            {
                monksOnLeft -= numberOfMonksToMove;
                cannibalsOnLeft -= numberOfCannibalsToMove;
                boat = -1;
                monksOnRight += numberOfMonksToMove;
                cannibalsOnRight += numberOfCannibalsToMove;
            }
            else
            {
                monksOnLeft += numberOfMonksToMove;
                cannibalsOnLeft += numberOfCannibalsToMove;
                boat = +1;
                monksOnRight -= numberOfMonksToMove;
                cannibalsOnRight -= numberOfCannibalsToMove;
            }
            return new MonksAndCannibalsState(monksOnLeft, cannibalsOnLeft, boat, monksOnRight, cannibalsOnRight);
        }
        public override bool PostCondition(State a)
        {
            return a.IsState();
        }
        public override string ToString()
        {
            return numberOfMonksToMove + ", " + numberOfCannibalsToMove;
        }
    }
    class Node
    {
        State state;
        int depth;
        Node parentNode;
        List<Operator> operators;
        int indexOfLastTestedOperator = -1;
        public Node(State state, List<Operator> operators)
        {
            this.state = state;
            depth = 0;
            parentNode = null;
            this.operators = new List<Operator>(operators); // we clone the list of operators
        }
        public Node(State state, int depth, Node parentNode, List<Operator> operators) : this(state, operators)
        {
            this.depth = depth;
            this.parentNode = parentNode;
        }
        public bool IsTerminalNode() { return state.IsGoalState(); }
        public Node GetParentNode() { return parentNode; }
        public int GetDepth() { return depth;  }
        public Node GetNextChildNode()
        {
            State newState;
            do
            {
                indexOfLastTestedOperator++;
                if (indexOfLastTestedOperator == operators.Count) return null;
                newState = operators[indexOfLastTestedOperator].Operate(state);
            } while (newState==null);
            return new Node(newState, depth + 1, this, operators);
        }
        public override bool Equals(object obj)
        {
            Node csúcsToCompare = (Node)obj;
            return state.Equals(csúcsToCompare.state);
        }
        public override int GetHashCode()
        {
            return state.GetHashCode();
        }
        public override string ToString()
        {
            return "depth = " + depth + ", state = " + state;
        }
        public void PrintPath()
        {
            Node actualNode = this;
            Stack<Node> path = new Stack<Node>();
            while (actualNode != null)
            {
                path.Push(actualNode);
                actualNode = actualNode.GetParentNode();
            }
            foreach (Node act in path) Console.WriteLine(act);
        }
    }
    class BackTrack
    {
        StateSpaceRepresentation problemRepresentation;
        public BackTrack(StateSpaceRepresentation problemRepresentation)
        {
            this.problemRepresentation = problemRepresentation;
        }
        public Node GraphSearch()
        {
            State startState = problemRepresentation.GetStartState();
            List<Operator> operators = problemRepresentation.GetOperators();
            Node actualNode = new Node(startState, operators);
            while(!actualNode.IsTerminalNode())
            {
                Node newNode = actualNode.GetNextChildNode();
                while (newNode == null)
                {
                    actualNode = actualNode.GetParentNode(); // backtrack
                    if (actualNode == null) return null;
                    newNode = actualNode.GetNextChildNode();
                }
                actualNode = newNode;
                // cycle detection
                Node parentNodeForCicleDetection = actualNode.GetParentNode();
                while (parentNodeForCicleDetection != null)
                {
                    if (actualNode.Equals(parentNodeForCicleDetection))
                    {
                        actualNode = actualNode.GetParentNode(); // backtrack
                        break;
                    }
                    parentNodeForCicleDetection = parentNodeForCicleDetection.GetParentNode();
                }
            }
            return actualNode;
        }
    }
}