如何基于给定条件遍历所有可行Nerdle游戏等式？Python实现问询

我正在编写Python代码求解Nerdle游戏，现有基础代码如下，参数对应场景为：数字8、4、3不在最终等式中，加减运算符也不在，遍历的等式不能包含这些元素。

allNumbers = {1,2,3,4,5,6,7,8,9,0}
searchedEq = "00000000"

allOperations = "+-/*" # 四则运算
operationsNotInEq = "+-"
operationsInEq = set(allOperations) - set(operationsNotInEq)

numbersNotInEq = "843"
numbersInEq = list(allNumbers - {int(i) for i in list(numbersNotInEq)})

当前问题 #

在给定条件下，遍历所有可能等式的最优/最简方法是什么？已知可行解数量有限（等式长度固定为8位，仅允许特定数字与运算符），求具体实现建议。

优化遍历的核心思路与实现 #

1. 先明确Nerdle的等式规则

8位Nerdle等式是运算式=结果的结构，总字符数为8（包含等号），必须满足：

• 运算符不能在首位/末位，也不能连续出现
• 多位数不能以0开头（单个0除外）
• 运算式必须合法，且结果为整数
• 所有数字和运算符都在允许的集合内

2. 缩小生成范围，避免无效遍历

直接生成所有8位组合会产生大量无效结果，建议拆分结构分模块生成：

• 先确定8位等式的合法结构：运算式+等号+结果的字符数总和为8，比如：
  • 1位数字+运算符+2位数字=3位数字（如9*12=108）
  • 2位数字+运算符+1位数字=3位数字（如12*9=108）
  • 2位数字+运算符+2位数字=2位数字（如12*3=36）
  • 3位数字+运算符+1位数字=2位数字（如120/3=40）
• 预先生成允许的数字池和运算符池：

  allowed_numbers = {str(n) for n in allNumbers - {int(i) for i in numbersNotInEq}}
  allowed_ops = operationsInEq  # 即{'*', '/'}
  

3. 分步骤生成并验证合法性

下面是可直接复用的简化实现，通过分模块生成提前过滤无效情况：

from itertools import product

allNumbers = {1,2,3,4,5,6,7,8,9,0}
numbersNotInEq = "843"
allowed_numbers = {str(n) for n in allNumbers - {int(i) for i in numbersNotInEq}}
allowed_ops = {'*', '/'}

# 定义8位等式的合法结构：(数字1长度, 数字2长度, 结果长度)，满足 数字1长度+1+数字2长度+1+结果长度=8
valid_structures = [
    (1, 2, 3),
    (2, 1, 3),
    (2, 2, 2),
    (3, 1, 2),
]

def generate_valid_numbers(length):
    """生成指定长度的合法数字字符串，排除以0开头的多位数"""
    if length == 1:
        return allowed_numbers
    # 首位不能为0
    first_digits = allowed_numbers - {'0'}
    other_digits = allowed_numbers
    numbers = set()
    for first in first_digits:
        for rest in product(other_digits, repeat=length-1):
            numbers.add(first + ''.join(rest))
    return numbers

def generate_all_valid_equations():
    valid_eqs = []
    for num1_len, num2_len, res_len in valid_structures:
        num1_list = generate_valid_numbers(num1_len)
        num2_list = generate_valid_numbers(num2_len)
        for num1 in num1_list:
            for num2 in num2_list:
                for op in allowed_ops:
                    # 处理除法的特殊规则
                    if op == '/':
                        num2_int = int(num2)
                        if num2_int == 0:
                            continue
                        num1_int = int(num1)
                        if num1_int % num2_int != 0:
                            continue
                        res = str(num1_int // num2_int)
                    else:
                        res = str(int(num1) * int(num2))
                    # 检查结果长度和数字合法性
                    if len(res) != res_len:
                        continue
                    if all(c in allowed_numbers for c in res):
                        eq = f"{num1}{op}{num2}={res}"
                        if len(eq) == 8:
                            valid_eqs.append(eq)
    return valid_eqs

# 生成并输出结果
valid_equations = generate_all_valid_equations()
print(f"合法等式总数：{len(valid_equations)}")
print("示例等式：", valid_equations[:5])

4. 额外优化建议

• 缓存生成的数字组合：比如把generate_valid_numbers的结果缓存，避免重复生成
• 提前排除无效运算：比如乘法结果超过指定长度时直接跳过，不用生成完整等式
• 用集合去重：如果生成过程中有重复等式（比如不同结构生成同一等式），可以用集合存储结果自动去重

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