HáromKancsóÁllapot

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

namespace mesting_3kancso
{
    /// <summary>
    /// Minden állapot osztály őse.
    /// </summary>
    abstract class AbsztraktÁllapot : ICloneable
    {
        public abstract bool ÁllapotE();

        public abstract bool CélÁllapotE();

        public abstract int OperátorokSzáma();

        // A szuper operátoron keresztül lehet elérni az összes operátort.
        // Igazat ad vissza, ha az i. alap operátor alkalmazható a belső állapotra.
        public abstract bool SzuperOperátor(int i);

        public virtual object Clone() { return MemberwiseClone(); }

        public override bool Equals(Object a) { return false; }

        public override int GetHashCode() { return base.GetHashCode(); }
    }


    /// <summary>
    /// A csúcs tartalmaz egy állapotot, a csúcs mélységét, és a csúcs szülőjét.
    /// Így egy csúcs egy egész utat reprezentál a start csúcsig.
    /// </summary>
    class Csúcs
    {
        // A csúcs tartalmaz egy állapotot, a mélységét és a szülőjét
        AbsztraktÁllapot állapot;
        int mélység;
        Csúcs szülő; // A szülőkön felfelé haladva a start csúcsig jutok.
        // Konstruktor:
        // A belső állapotot beállítja a start csúcsra.
        // A hívó felelőssége, hogy a kezdő állapottal hívja meg.
        // A start csúcs mélysége 0, szülője nincs.
        public Csúcs(AbsztraktÁllapot kezdőÁllapot)
        {
            állapot = kezdőÁllapot;
            mélység = 0;
            szülő = null;
        }
        // Egy új gyermek csúcsot készít.
        // Erre még meg kell hívni egy alkalmazható operátor is, csak azután lesz kész.
        public Csúcs(Csúcs szülő)
        {
            állapot = (AbsztraktÁllapot)szülő.állapot.Clone();
            mélység = szülő.mélység + 1;
            this.szülő = szülő;
        }
        public Csúcs GetSzülő() { return szülő; }
        public int GetMélység() { return mélység; }
        public bool TerminálisCsúcsE() { return állapot.CélÁllapotE(); }
        public int OperátorokSzáma() { return állapot.OperátorokSzáma(); }
        public bool SzuperOperátor(int i) { return állapot.SzuperOperátor(i); }
        public override bool Equals(Object obj)
        {
            Csúcs cs = (Csúcs)obj;
            return állapot.Equals(cs.állapot);
        }
        public override int GetHashCode() { return állapot.GetHashCode(); }
        public override String ToString() { return állapot.ToString(); }
        // Alkalmazza az összes alkalmazható operátort.
        // Visszaadja az így előálló új csúcsokat.
        public List<Csúcs> Kiterjesztes()
        {
            List<Csúcs> újCsúcsok = new List<Csúcs>();
            for (int i = 0; i < OperátorokSzáma(); i++)
            {
                // Új gyermek csúcsot készítek.
                Csúcs újCsúcs = new Csúcs(this);
                // Kiprobálom az i.dik alapoperátort. Alkalmazható?
                if (újCsúcs.SzuperOperátor(i))
                {
                    // Ha igen, hozzáadom az újakhoz.
                    újCsúcsok.Add(újCsúcs);
                }
            }
            return újCsúcsok;
        }
    }

    /// <summary>
    /// Minden gráfkereső algoritmus őse.
    /// A gráfkeresőknek csak a Keresés metódust kell megvalósítaniuk.
    /// Ez visszaad egy terminális csúcsot, ha talált megoldást, egyébként null értékkel tér vissza.
    /// A terminális csúcsból a szülő referenciákon felfelé haladva áll elő a megoldás.
    /// </summary>
    abstract class GráfKereső
    {
        private Csúcs startCsúcs; // A start csúcs csúcs.
        // Minden gráfkereső a start csúcsból kezd el keresni.
        public GráfKereső(Csúcs startCsúcs)
        {
            this.startCsúcs = startCsúcs;
        }
        // Jobb, ha a start csúcs privát, de a gyermek osztályok lekérhetik.
        protected Csúcs GetStartCsúcs() { return startCsúcs; }
        /// Ha van megoldás, azaz van olyan út az állapottér gráfban,
        /// ami a start csúcsból egy terminális csúcsba vezet,
        /// akkor visszaad egy megoldást, egyébként null.
        /// A megoldást egy terminális csúcsként adja vissza.
        /// Ezen csúcs szülő referenciáin felfelé haladva adódik a megoldás fordított sorrendben.
        public abstract Csúcs Keresés();
        /// <summary>
        /// Kiíratja a megoldást egy terminális csúcs alapján.
        /// Feltételezi, hogy a terminális csúcs szülő referenciáján felfelé haladva eljutunk a start csúcshoz.
        /// A csúcsok sorrendjét megfordítja, hogy helyesen tudja kiírni a megoldást.
        /// Ha a csúcs null, akkor kiírja, hogy nincs megoldás.
        /// </summary>
        /// <param name="egyTerminálisCsúcs">
        /// A megoldást képviselő terminális csúcs vagy null.
        /// </param>
        public void megoldásKiírása(Csúcs egyTerminálisCsúcs)
        {
            if (egyTerminálisCsúcs == null)
            {
                Console.WriteLine("Nincs megoldás");
                return;
            }
            // Meg kell fordítani a csúcsok sorrendjét.
            Stack<Csúcs> megoldás = new Stack<Csúcs>();
            Csúcs aktCsúcs = egyTerminálisCsúcs;
            while (aktCsúcs != null)
            {
                megoldás.Push(aktCsúcs);
                aktCsúcs = aktCsúcs.GetSzülő();
            }
            // Megfordítottuk, lehet kiírni.
            foreach (Csúcs akt in megoldás) Console.WriteLine(akt);
        }
    }

    /// <summary>
    /// A backtrack gráfkereső algoritmust megvalósító osztály.
    /// A három alap backtrack algoritmust egyben tartalmazza. Ezek
    /// - az alap backtrack
    /// - mélységi korlátos backtrack
    /// - emlékezetes backtrack
    /// Az ág-korlátos backtrack nincs megvalósítva.
    /// </summary>
    class BackTrack : GráfKereső
    {
        int korlát; // Ha nem nulla, akkor mélységi korlátos kereső.
        bool emlékezetes; // Ha igaz, emlékezetes kereső.
        public BackTrack(Csúcs startCsúcs, int korlát, bool emlékezetes)
            : base(startCsúcs)
        {
            this.korlát = korlát;
            this.emlékezetes = emlékezetes;
        }
        // nincs mélységi korlát, se emlékezet
        public BackTrack(Csúcs startCsúcs) : this(startCsúcs, 0, false) { }
        // mélységi korlátos kereső
        public BackTrack(Csúcs startCsúcs, int korlát) : this(startCsúcs, korlát, false) { }
        // emlékezetes kereső
        public BackTrack(Csúcs startCsúcs, bool emlékezetes) : this(startCsúcs, 0, emlékezetes) { }
        // A keresés a start csúcsból indul.
        // Egy terminális csúcsot ad vissza. A start csúcsból el lehet jutni ebbe a terminális csúcsba.
        // Ha nincs ilyen, akkor null értéket ad vissza.
        public override Csúcs Keresés() { return Keresés(GetStartCsúcs()); }
        // A kereső algoritmus rekurzív megvalósítása.
        // Mivel rekurzív, ezért a visszalépésnek a "return null" felel meg.
        private Csúcs Keresés(Csúcs aktCsúcs)
        {
            int mélység = aktCsúcs.GetMélység();
            // mélységi korlát vizsgálata
            if (korlát > 0 && mélység >= korlát) return null;
            // emlékezet használata kör kiszűréséhez
            Csúcs aktSzülő = null;
            if (emlékezetes) aktSzülő = aktCsúcs.GetSzülő();
            while (aktSzülő != null)
            {
                // Ellenőrzöm, hogy jártam-e ebben az állapotban. Ha igen, akkor visszalépés.
                if (aktCsúcs.Equals(aktSzülő)) return null;
                // Visszafelé haladás a szülői láncon.
                aktSzülő = aktSzülő.GetSzülő();
            }
            if (aktCsúcs.TerminálisCsúcsE())
            {
                // Megvan a megoldás, vissza kell adni a terminális csúcsot.
                return aktCsúcs;
            }
            // Itt hívogatom az alapoperátorokat a szuper operátoron
            // keresztül. Ha valamelyik alkalmazható, akkor új csúcsot
            // készítek, és meghívom önmagamat rekurzívan.
            for (int i = 0; i < aktCsúcs.OperátorokSzáma(); i++)
            {
                // Elkészítem az új gyermek csúcsot.
                // Ez csak akkor lesz kész, ha alkalmazok rá egy alkalmazható operátort is.
                Csúcs újCsúcs = new Csúcs(aktCsúcs);
                // Kipróbálom az i.dik alapoperátort. Alkalmazható?
                if (újCsúcs.SzuperOperátor(i))
                {
                    // Ha igen, rekurzívan meghívni önmagam az új csúcsra.
                    // Ha nem null értéket ad vissza, akkor megvan a megoldás.
                    // Ha null értéket, akkor ki kell próbálni a következő alapoperátort.
                    Csúcs terminális = Keresés(újCsúcs);
                    if (terminális != null)
                    {
                        // Visszaadom a megoldást képviselő terminális csúcsot.
                        return terminális;
                    }
                    // Az else ágon kellene visszavonni az operátort.
                    // Erre akkor van szükség, ha az új gyermeket létrehozásában nem lenne klónozást.
                    // Mivel klónoztam, ezért ez a rész üres.
                }
            }
            // Ha kipróbáltam az összes operátort és egyik se vezetett megoldásra, akkor visszalépés.
            // A visszalépés hatására eggyel feljebb a következő alapoperátor kerül sorra.
            return null;
        }
    }

    struct Kancsó
    {
        public int Max;
        public int Akt;
    }

    class HáromKancsóÁllapot : AbsztraktÁllapot
    {
        Kancsó[] kancsók = new Kancsó[3];

        public HáromKancsóÁllapot()
        {
            kancsók[0].Max = 8;
            kancsók[0].Akt = 8;
            kancsók[1].Max = 5;
            kancsók[1].Akt = 0;
            kancsók[2].Max = 3;
            kancsók[2].Akt = 0;
        }

        public HáromKancsóÁllapot(HáromKancsóÁllapot másolandó)
        {
            kancsók[0].Max = másolandó.kancsók[0].Max;
            kancsók[0].Akt = másolandó.kancsók[0].Akt;
            kancsók[1].Max = másolandó.kancsók[1].Max;
            kancsók[1].Akt = másolandó.kancsók[1].Akt;
            kancsók[2].Max = másolandó.kancsók[2].Max;
            kancsók[2].Akt = másolandó.kancsók[2].Akt;
        }

        public override bool ÁllapotE()
        {
            return true;
        }

        public override bool CélÁllapotE()
        {
            return kancsók[0].Akt == 4 || kancsók[1].Akt == 4 || kancsók[2].Akt == 4;
        }

        public override int OperátorokSzáma()
        {
            return 6;
        }

        public bool PreÁllapot(int honnan, int hova)
        {
            return honnan != hova && kancsók[honnan].Akt != 0 && kancsók[hova].Akt != kancsók[hova].Max;
        }

        public override bool SzuperOperátor(int i)
        {
            switch (i)
            {
                case 0: return Tölt(2, 1);
                case 1: return Tölt(2, 0);
                case 2: return Tölt(1, 0);
                case 3: return Tölt(1, 2);
                case 4: return Tölt(0, 1);
                case 5: return Tölt(0, 2);
                default: return false;
            }
        }
        public bool Tölt(int honnan, int hova)
        {
            if (!PreÁllapot(honnan, hova)) return false;

            int szabad = kancsók[hova].Max - kancsók[hova].Akt;
            if (kancsók[honnan].Akt < szabad)
            {
                kancsók[hova].Akt += kancsók[honnan].Akt;
                kancsók[honnan].Akt = 0;
            }
            else
            {
                kancsók[hova].Akt += szabad;
                kancsók[honnan].Akt -= szabad;
            }

            return ÁllapotE();
        }

        public override object Clone()
        {
            return new HáromKancsóÁllapot(this);
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < kancsók.Length; i++)
            {
                sb.Append(String.Format("| {0}: {1} liter |", i+1, kancsók[i].Akt));
            }

            return sb.ToString();
        }
    }


    class Program
    {
        static void Main(string[] args)
        {
            Csúcs startCsúcs;
            GráfKereső kereső;

            startCsúcs = new Csúcs(new HáromKancsóÁllapot());
            kereső = new BackTrack(startCsúcs, 10, true);
            kereső.megoldásKiírása(kereső.Keresés());

            Console.ReadLine();
        }
    }
}