c# - 可能具有挑战性 : How do I implement solving logic in this puzzle solver program?

Question

我正在尝试制作一个解决日本益智游戏“River IQ 测试”的程序，我知道，我可以查找解决方案，但现在这不会很有趣，也没有教育意义，不是吗？ :)

这是游戏的目标:

使用木筏，用户可以运送人过河，用户必须将所有人从左侧运送到右侧。每次使用木筏时，它都会停留在另一边，直到另一边的人再次将它引到另一边以吸引更多人。

左边有以下人开始:

• 1 名囚犯
• 1 名警察
• 1 位父亲
• 2个儿子
• 1 位母亲
• 2个女儿

这是类的层次结构:

乘客

• 飞行员
  • 家长
    • 妈妈
    • 父亲
  • 警察
• 犯人
• child
  • 女儿
  • 儿子

必须遵守以下规则:

• 一次只能有 2 个人在木筏上。
• 只有警察、父亲和母亲可以驾驶木筏
• 在没有警察在场的情况下，囚犯不能在其他人在场的情况下被放置在木筏上或河的任何一侧。
• 父亲不能在没有母亲在场的情况下与女儿一起在木筏上或河的两边。
• 母亲不能在没有父亲在场的情况下与儿子一起在木筏上或河的两边。

我还需要完成的是:

• 在解决难题之前使用试错法解决逻辑的逻辑
• 打印最终成功解决方案的逻辑
• 检查是否每个人都到达另一边的逻辑。

这是我当前的代码:

程序类(解决逻辑应该在这里)

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();
    }
}

乘客列表类

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;
    }
}

边类(如河边)

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;
    }
}

木筏类

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

我看你是没学过PROLOG。这些问题是 PROLOG 中的经典问题，更重要的是 PROLOG 只处理问题的本质。当我在标题中看到逻辑和谜题时，很明显你需要一种逻辑语言。我知道您要求使用 C#，但这不是 OO 问题，因为您说这是逻辑问题。

参见 Prolog Programming in Depth第 229 页第 8.3 节。传教士和食人者请注意，该解决方案比问题中的所有代码都小。不要误会我的意思，很多年前我在同一条船上，双关语。

我认识的一些最优秀的程序员处理此类问题不是为了解决问题，而是因为要自己解决这些问题，他们知道他们会学到一些重要的东西，以后可以使用。花几个月时间了解 PROLOG 如何解决这个问题，你会比别人给你建议要好得多。如果您不了解递归以及 AI 如何解决问题，那么在您获得解决方案时，您多半会明白这一点。

编辑

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

PROLOG 有一个内置的 inference engine和 back-chaining这就是在给定规则的情况下找到解决方案的工作。您可以从头开始创建一个，这比解决您最初的问题更难，但是有一个 C# 中 PROLOG 的开源实现，C#Prolog约翰·普尔。虽然您可以查看源代码以了解 PROLOG 的工作原理，但代码经过了大量优化，因此除非您先了解 PROLOG，否则它并不容易理解。

如果您了解 F# 或函数式语言，How to implement a prolog interpreter in a purely functional language ？可能有帮助。

基本上，问题归结为创建一组规则，然后尝试组合规则，直到获得满足所有规则的结果。

从这些关键字和短语开始，在此处搜索互联网和问题。

统一
句法统一
后链
推理机
序言是如何工作的