带禁止移动规则的汉诺塔Haskell算法修改求助

针对你提出的禁止移动规则，我们需要调整递归逻辑，核心是处理单个盘子的禁止移动（通过中转柱子间接完成），并让递归子问题自动继承规则约束。

修改后的代码如下：

type HanoiMovement = (Integer, Char, Char)

hanoi :: Integer -> [HanoiMovement]
hanoi n = hanoiGen 'l' 'r' 'm' n
    where
        -- 定义禁止的直接移动对
        forbiddenMoves = [('l', 'm'), ('m', 'r')]
        -- 判断单次移动是否合法
        isAllowed :: Char -> Char -> Bool
        isAllowed src dest = (src, dest) `notElem` forbiddenMoves
        
        -- 处理单个盘子的移动：若直接移动禁止，则通过中转柱子完成
        moveSingle :: Integer -> Char -> Char -> Char -> [HanoiMovement]
        moveSingle disk src dest aux =
            if isAllowed src dest
                then [(disk, src, dest)]
                else [(disk, src, aux), (disk, aux, dest)]
        
        -- 递归生成移动步骤
        hanoiGen :: Char -> Char -> Char -> Integer -> [HanoiMovement]
        hanoiGen _ _ _ 0 = []
        hanoiGen src dest aux n =
            -- 1. 将n-1个盘子从源柱移到辅助柱
            hanoiGen src aux dest (n-1) ++
            -- 2. 移动最大的盘子（第n个）从源柱到目标柱（处理禁止移动）
            moveSingle n src dest aux ++
            -- 3. 将n-1个盘子从辅助柱移到目标柱
            hanoiGen aux dest src (n-1)

关键修改说明 #

1. 禁止移动判断：定义forbiddenMoves存储禁止的直接移动对，用isAllowed函数快速判断单次移动是否合法。
2. 单个盘子的中转处理：moveSingle函数负责处理单个盘子的移动逻辑，如果直接移动被禁止，就通过第三个柱子分两步完成（比如禁止l→m时，走l→r→m的间接路径）。
3. 递归逻辑适配：将原代码中直接生成大盘子移动步骤的[(n,s,z)]替换为调用moveSingle，确保大盘子的移动也遵循禁止规则；递归子问题会自动处理所有层级的移动约束，无需额外修改。

测试示例（n=2） #

调用hanoi 2会生成以下符合规则的步骤：

[(1,'l','r'), (1,'r','m'), (2,'l','r'), (1,'m','l'), (1,'l','r')]

所有步骤均无l→m或m→r的直接移动，且始终保持大盘在小盘下方的约束。

内容的提问来源于stack exchange，提问作者iTzTomy