State-Space Representation & Super Operator Design Pattern

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

namespace StateSpaceRepresentationUsingSuperOperatorDesignPattern
{
    class Program
    {
        static void Main(string[] args)
        {
            State startingState = new MonksAndCannibalsState();
            BackTrack bt = new BackTrack(startingState);
            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 state-space representation
    /// </summary>
    abstract class State : ICloneable
    {
        public abstract bool IsState();
        public abstract bool IsGoalState();
        public abstract int GetNumberOfOperators();
        public abstract bool SuperOperator(int i);
        public abstract object Clone();
        public override abstract bool Equals(Object a);
        public override int GetHashCode() { return base.GetHashCode(); }
    }
    class MonksAndCannibalsState : State
    {
        int monksOnLeft, cannibalsOnLeft, boat, monksOnRight, cannibalsOnRight;
        public MonksAndCannibalsState()
        {
            monksOnLeft = 3;
            cannibalsOnLeft = 3;
            boat = 1; // 1: left, -1: right
            monksOnRight = 0;
            cannibalsOnRight = 0;
        }
        public override object Clone() { return MemberwiseClone(); }
        public override bool IsState()
        {
            return ((monksOnLeft >= cannibalsOnLeft) || (monksOnLeft == 0)) &&
                ((monksOnRight >= cannibalsOnRight) || (monksOnRight == 0));
        }
        public override bool IsGoalState()
        {
            return monksOnRight == 3 && cannibalsOnRight == 3 && boat == -1;
        }public override int GetNumberOfOperators() { return 5; }
        public override bool SuperOperator(int i)
        {
            switch (i)
            {
                case 0: return operate(0, 1);
                case 1: return operate(0, 2);
                case 2: return operate(1, 1);
                case 3: return operate(1, 0);
                case 4: return operate(2, 0);
                default: return false;
            }
        }
        private bool operate(int monksToMove, int cannibalsToMove)
        {
            if (!preCondiction(monksToMove, cannibalsToMove)) return false;
            if (boat == 1)
            {
                monksOnLeft -= monksToMove;
                cannibalsOnLeft -= cannibalsToMove;
                boat = -1;
                monksOnRight += monksToMove;
                cannibalsOnRight += cannibalsToMove;
            }
            else
            {
                monksOnLeft += monksToMove;
                cannibalsOnLeft += cannibalsToMove;
                boat = 1;
                monksOnRight -= monksToMove;
                cannibalsOnRight -= cannibalsToMove;
            }
            if (IsState()) return true;
            return false;
        }
        private bool preCondiction(int monksToMove, int cannibalsToMove)
        {
            if (monksToMove + cannibalsToMove > 2 ||
                monksToMove + cannibalsToMove < 0 ||
                monksToMove < 0 || cannibalsToMove < 0) return false;
            if (boat == 1)
                return monksOnLeft >= monksToMove &&
                    cannibalsOnLeft >= cannibalsToMove;
            else
                return monksOnRight >= monksToMove &&
                    cannibalsOnRight >= cannibalsToMove;
        }
        public override string ToString()
        {
            return monksOnLeft + "," + cannibalsOnLeft + "," + boat +
                "," + monksOnRight + "," + cannibalsOnRight;
        }
        public override bool Equals(Object a)
        {
            MonksAndCannibalsState aa = (MonksAndCannibalsState)a;
            return aa.monksOnLeft == monksOnLeft &&
                aa.cannibalsOnLeft == cannibalsOnLeft && aa.boat == boat;
        }
        public override int GetHashCode()
        {
            return monksOnLeft.GetHashCode() + cannibalsOnLeft.GetHashCode() + boat.GetHashCode();
        }
    }
    class Node
    {
        State state;
        int depth;
        Node parentNode;
        int indexOfLastTestedOperator = -1;
        public Node(State state, int depth, Node parentNode)
        {
            this.state = state;
            this.depth = depth;
            this.parentNode = parentNode;
        }
        public Node(State startState) : this(startState, 0, null) { }
        public Node GetParentNode() { return parentNode; }
        public int GetDepth() { return depth; }
        public bool IsTerminalNode() { return state.IsGoalState(); }
        public Node GetNextChildNode()
        {
            State newState;
            bool isApplicable;
            do
            {
                indexOfLastTestedOperator++;
                if (indexOfLastTestedOperator == state.GetNumberOfOperators()) return null;
                newState = (State)state.Clone();
                isApplicable = newState.SuperOperator(indexOfLastTestedOperator);
            } while (!isApplicable);
            return new Node(newState, depth + 1, this);
        }
        public override bool Equals(Object obj)
        {
            Node otherNode = (Node)obj;
            return state.Equals(otherNode.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
    {
        State startingState;
        public BackTrack(State startingState)
        {
            this.startingState = startingState;
        }
        public Node GraphSearch()
        {
            State startState = (State)this.startingState.Clone();
            Node actualNode = new Node(startState);
            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;
        }
    }
}