Python狼羊过河问题：无效状态过滤条件逻辑故障求助

问题背景 #

我正在编写Python程序解决狼羊过河问题（又称囚犯与守卫问题、传教士与食人魔问题），核心规则如下：

• 支持自定义初始羊、狼数量（默认3羊3狼）
• 船最多载2只动物，且不能空驶
• 任何时刻两岸狼数不能超过羊数（羊数为0时例外）
• 程序需返回合法移动方案，无解则返回空列表

目前已实现生成所有可能移动的函数，但在有效状态筛选环节遇阻：部分单动物移动产生的无效状态无法被正确过滤——这类状态会导致后续只能将动物送回，陷入循环回到初始状态，属于无意义操作。

状态格式为嵌套列表：[[左岸羊数, 左岸狼数, 船位置(1在左/0在右)], [右岸对应数据]]

• 初始状态示例：[[3,3,1],[0,0,0]]
• 移动2只狼后的状态示例：[[3,1,0],[0,2,1]]

需要过滤的无效状态例如：[[2,3,0],[1,0,1]]、[[3,2,0],[0,1,1]]，但当前eliminate_states函数的c4、c5条件仅排除了其中一个，像[[3,2,0],[0,1,1]]这类状态仍会被保留。

问题代码 #

当前的状态过滤函数如下：

def eliminate_states(self, possible_state_list, official_state_list):
    valid_states = []
    for state in possible_state_list:
        # Condition 1: potential move cannot be in states list
        c1 = state not in official_state_list
        # Condition 2/3: wolves cannot outnumber sheep on LEFT/RIGHT side
        c2 = (state[0][1]<=state[0][0] and state[0][0] > 0) or (state[0][1]>state[0][0] and state[0][0] == 0)
        c3 = (state[1][1]<=state[1][0] and state[1][0] > 0) or (state[1][1]>state[1][0] and state[1][0] == 0)
        # Condition 4/5: Don't sent single sheep/wolf to an empty side (results in unproductive state)
        c4 = not (state[0][0]==1 and state[0][1]==0 and state[0][2]==1) or (state[0][0]==0 and state[0][1]==1 and state[0][2]==1) 
        c5 = not (state[1][0]==1 and state[1][1]==0 and state[1][2]==1) or (state[1][0]==0 and state[1][1]==1 and state[1][2]==1)

        condition_list = [c1,c2,c3,c4,c5]
        if all(condition_list) == True:
            valid_states.append(state)

    return valid_states

求助需求 #

我尝试过直接对比状态列表、改用索引引用等方式，但都未完全解决问题。现在需要排查c4、c5条件的逻辑错误，找出这类无效状态未被过滤的原因。

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