MestInt - Vikiféle

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

abstract class AbsztraktÁllapot
{
    public abstract bool ÁllapotE();
    public abstract bool CélÁllapotE();
    public abstract int OperátorokSzáma();
    // bool helyére AbsztraktÁllapot kell a másik megoldás szerint
    // cél: immutable legyen --> a belső állapota nem fog megváltozni
    public abstract AbsztraktÁllapot SzuperOperátor(int i);
    // kívülről így már nem kell meghívni a klónozást, de belül kell!!
    // az előtt kell klónozni, mielőtt megcsinálod a változtatást
    // mert a klónozás akkor kell, ha azt akarom, hogy az egyik változása ne változtasson a másikon
    // és ha immutable, akkor ne mtudom megváltoztatni
    // : ICloneable nem kell
    // így már a klónozás lehet protected
    protected virtual object Clone() { return MemberwiseClone(); }
    public override bool Equals(Object a) { return false; }
    public override int GetHashCode() { return base.GetHashCode(); }
}

class Csúcs
{
    AbsztraktÁllapot állapot;
    int mélység;
    Csúcs szülő;
    public Csúcs(AbsztraktÁllapot kezdőÁllapot)
    {
        állapot = kezdőÁllapot;
        mélység = 0;
        szülő = null;
    }
    // itt van változás!!!!
    public Csúcs(AbsztraktÁllapot állapot, int mélység, Csúcs szülő) //állapot --> új
    {
        this.állapot = állapot;
        this.mélység = mélység;
        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(); }
    // itt van változás!!!
    public Csúcs SzuperOperátor(int i)
    {
        AbsztraktÁllapot új = állapot.SzuperOperátor(i); //az lesz az új állapot, amit visszaadott a szuperoperátor
        if (új != null) return new Csúcs(új, mélység + 1, this);
        return null;
    }
    public override bool Equals(Object obj)
    {
        // 2 csúcs akkor egyenlő, ha a bennük lévő állapot megegyezik
        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(); }

}

abstract class GráfKereső
{
    private Csúcs startCsúcs;
    public GráfKereső(Csúcs startCsúcs)
    {
        this.startCsúcs = startCsúcs;
    }
    protected Csúcs GetStartCsúcs() { return startCsúcs; }
    public abstract Csúcs Keresés();
    public void megoldásKiírása(Csúcs egyTerminálisCsúcs)
    {
        if (egyTerminálisCsúcs == null)
        {
            Console.WriteLine("Nincs megoldás");
            return;
        }
        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ő();
        }
        foreach (Csúcs akt in megoldás) Console.WriteLine(akt);
    }
}

class BackTrack : GráfKereső
{
    int korlát;
    bool emlékezetes;
    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;
    }
    public BackTrack(Csúcs startCsúcs) : this(startCsúcs, 0, false) { }
    public BackTrack(Csúcs startCsúcs, int korlát) : this(startCsúcs, korlát, false) { }
    public BackTrack(Csúcs startCsúcs, bool emlékezetes) : this(startCsúcs, 0, emlékezetes) { }
    public override Csúcs Keresés() { return Keres(GetStartCsúcs()); }

    private Csúcs Keresés(Csúcs aktCsúcs)
    {
        Stack<int> operatstack = new Stack<int>();
        int aktop = 0;
        while (aktCsúcs != null)
        {
            if (aktCsúcs.TerminálisCsúcsE()) return aktCsúcs;
            int operatorszam = aktCsúcs.OperátorokSzáma();
            for (; aktop < operatorszam; aktop++)
            {
                bool jartamitt = false;
                Csúcs vizsgalt = aktCsúcs.GetSzülő();
                while (vizsgalt != null)
                {
                    if (aktCsúcs.Equals(vizsgalt))
                    {
                        jartamitt = true;
                        break;
                    }
                    vizsgalt = vizsgalt.GetSzülő();
                }
                Csúcs nextcsúcs = aktCsúcs.SzuperOperátor(aktop);
                if (nextcsúcs != null && !jartamitt)
                {
                    operatstack.Push(aktop);
                    aktop = -1;
                    aktCsúcs = nextcsúcs;
                }
            }
            aktCsúcs = aktCsúcs.GetSzülő();
            try
            {
                aktop = operatstack.Pop() + 1;
            }
            catch (InvalidOperationException)
            {
                return null;
            }
        }
        return null;
    }

    // ebben can változás!
    private Csúcs Keres(Csúcs aktCsúcs)
    {
        int mélység = aktCsúcs.GetMélység();
        //úgy mondod, hogy nincs korlátos (mert az a mélységi korlátos backtrackhez kell), hogy korlát=0
        if (korlát > 0 && mélység >= korlát) return null;
        Csúcs aktSzülő = null;
        if (emlékezetes) aktSzülő = aktCsúcs.GetSzülő();
        while (aktSzülő != null)
        {
            if (aktCsúcs.Equals(aktSzülő)) return null;
            aktSzülő = aktSzülő.GetSzülő();
        }
        // ő a bázisfeltétel, ez fogja megállítani a rekurziót
        if (aktCsúcs.TerminálisCsúcsE())
        {
            return aktCsúcs;
        }
        for (int i = 0; i < aktCsúcs.OperátorokSzáma(); i++) // kipróbálja az összes operátort
        {
            Csúcs újCsúcs = aktCsúcs.SzuperOperátor(i); // az új csúcsot úgy kapom meg az aktuális csúcsból, hogy előremegyek a szuperoperátorral
            if (újCsúcs!=null)
            {
                Csúcs terminális = Keres(újCsúcs);
                if (terminális != null)
                {
                    return terminális;
                }
            }
        }
        return null;
    }
}

class ÉhesHuszárÁllapot : AbsztraktÁllapot
{
    static int N = 3;
    int x, y;
    public ÉhesHuszárÁllapot()
    {
        x = 2; // A bal felső sarokból indulunk, ami a margó
        y = 2; // miatt a (2,2) koordinátán van.
    }
    public ÉhesHuszárÁllapot(int n)
    {
        x = 2;
        y = 2;
        N = n;
    }
    public override bool CélÁllapotE()
    {
        // A jobb alsó sarok a margó miatt a (N+1,N+1) helyen van.
        return x == N + 1 && y == N + 1;
    }
    public override bool ÁllapotE()
    {
        // a ló nem a margon van
        return x >= 2 && y >= 2 && x <= N + 1 && y <= N + 1;
    }
    private bool preLóLépés(int x, int y)
    {
        // jó lólépés-e, ha nem akkor return false
        if (!(x * y == 2 || x * y == -2)) return false;
        return true;
    }
    // ebben van változás!!!
    private AbsztraktÁllapot lóLépés(int x, int y)
    {
        if (!preLóLépés(x, y)) return null;
        ÉhesHuszárÁllapot új = (ÉhesHuszárÁllapot)this.Clone(); //vagy copy konstruktorral
        új.x += x;
        új.y += y;
        if (új.ÁllapotE()) return új;
        return null;
        // így nem helyben történik meg az átmenet, hanem az újban!!!
        // és innentől fogva immutable
        // ha így írjuk meg, az újnak kell hívni az ÁllapotE() fv.-ét
    }
    // itt van változás!!!
    public override AbsztraktÁllapot SzuperOperátor(int i)
    {
        switch (i)
        { // itt sorolom fel a lehetséges 8 lólépést
            case 0: return lóLépés(1, 2);
            case 1: return lóLépés(1, -2);
            case 2: return lóLépés(-1, 2);
            case 3: return lóLépés(-1, -2);
            case 4: return lóLépés(2, 1);
            case 5: return lóLépés(2, -1);
            case 6: return lóLépés(-2, 1);
            case 7: return lóLépés(-2, -1);
            default: return null; // ez jelenti azt, hogy nem sikerült
        }
    }
    public override int OperátorokSzáma() { return 8; }
    // A kiíratásnál kivonom x-ből és y-ból a margó szélességét.
    public override string ToString() { return (x - 2) + " : " + (y - 2); }
    public override bool Equals(Object a)
    {
        ÉhesHuszárÁllapot aa = (ÉhesHuszárÁllapot)a;
        return aa.x == x && aa.y == y;
    }
    // Ha két példány egyenlő, akkor a hasítókódjuk is egyenlő.
    public override int GetHashCode()
    {
        return x.GetHashCode() + y.GetHashCode();
    }
}

    class Program
    {
        static void Main(string[] args)
        {
            Csúcs startCsúcs;
            GráfKereső kereső;
            Console.WriteLine("Éheshuszár probléma:");
            startCsúcs = new Csúcs(new ÉhesHuszárÁllapot(8));
            kereső = new BackTrack(startCsúcs, 10, true);
            kereső.megoldásKiírása(kereső.Keresés());
            Console.ReadLine();
        }
    }