基于ZDD实现计算方块谜题求解器的技术咨询

我正在开发**数块谜题（Calculation Block Puzzles）**的生成器与求解器，这是数独的变体谜题，规则如下：

• 在n×n网格中填入1~n的数字
• 每行、每列的数字不重复（符合拉丁方规则）
• 网格被划分为多个区块，每个区块内的数字需满足指定运算规则（如求和、求积等），运算结果为区块标注值

已完成工作 #

谜题生成流程为：先生成作为答案的拉丁方，再将n×n网格随机划分为区块并匹配拉丁方的运算值。已完成拉丁方生成类与区块划分程序，代码如下：

GridGraph类（区块划分与可视化） #

import random
import networkx as nx
import matplotlib.pyplot as plt

class GridGraph:
  
    def __init__(self, n, latin_square, seed=None):  # 未指定seed时使用当前时间作为种子
        random.seed(seed)
        self.n = n
        self.G = nx.grid_2d_graph(n, n)
        pos = dict((n, n) for n in self.G.nodes())
        nx.set_node_attributes(self.G, pos, 'pos')  # 为节点添加坐标属性
        for edge in self.G.edges():
            self.G.edges[edge]['weight'] = random.random()
        self.latin_square = latin_square
                
    def limit_nodes(self, l):
        T = nx.minimum_spanning_tree(self.G)
        largest_nodelist_T = max(nx.connected_components(T), key=len)
        while len(largest_nodelist_T) > l:
            H = T.subgraph(largest_nodelist_T)
            edges = list(H.edges())
            # 按权重排序边
            edges.sort(key=lambda x: H.edges[x]['weight'])
            e = edges[0]  # 选择权重最小的边
            T.remove_edge(e[0], e[1])
            largest_nodelist_T = max(nx.connected_components(T), key=len)
        self.G = T
        return self.G
        
    def draw_graph(self, title='Graph'):
        """绘制网格图"""
        plt.figure(figsize=(6, 6))
        pos = nx.get_node_attributes(self.G, 'pos')
        # 将坐标旋转90度
        rotated_pos = {node: (y, -x) for node, (x, y) in pos.items()}
        nx.draw_networkx_edges(self.G, rotated_pos, width=5.0)
        nx.draw_networkx(self.G, pos=rotated_pos, with_labels=True)
        nx.draw_networkx_nodes(self.G, rotated_pos, node_size=800)
        plt.suptitle(title)
        plt.show()
        
    def draw_graph2(self, title='Graph'):  # 显示谜题
        """绘制谜题界面"""
        plt.figure(figsize=(6, 6))
        
        for component in nx.connected_components(self.G):
            # 计算区块内数值的和
            component_sum = sum(self.latin_square.square[i][j] for (i, j) in component)
            # 获取区块的最小坐标
            min_i, min_j = min(component)
            # 在区块最小坐标处绘制运算值
            plt.text(min_j, min_i, component_sum, fontsize=20, color='blue', ha='left', va='top')
            # 绘制区块轮廓
            for i, j in component:
                # 上方无区块元素时绘制实线
                if (i-1, j) not in component:
                    plt.plot([j, j+1], [i, i], color='black')
                else:
                    plt.plot([j, j+1], [i, i], linestyle='dashed', color='lightgray')
                # 下方无区块元素时绘制实线
                if (i+1, j) not in component:
                    plt.plot([j, j+1], [i+1, i+1], color='black')
                else:
                    plt.plot([j, j+1], [i+1, i+1], linestyle='dashed', color='lightgray')
                # 左侧无区块元素时绘制实线
                if (i, j-1) not in component:
                    plt.plot([j, j], [i, i+1], color='black')
                else:
                    plt.plot([j, j], [i, i+1], linestyle='dashed', color='lightgray')
                # 右侧无区块元素时绘制实线
                if (i, j+1) not in component:
                    plt.plot([j+1, j+1], [i, i+1], color='black')
                else:
                    plt.plot([j+1, j+1], [i, i+1], linestyle='dashed', color='lightgray')
                    
        # 移除坐标轴标签
        plt.xticks([])
        plt.yticks([])
        # 反转y轴
        plt.gca().invert_yaxis()
        plt.suptitle(title, fontname="MS Gothic")
        plt.title('+', fontsize=20, loc='Right')
        plt.show()
        
    def draw_graph3(self, title='Graph'):  # 显示谜题答案
        """绘制答案界面"""
        plt

Board类（孤立单元格识别） #

已实现识别孤立单元格的方法，代码如下：

import networkx as nx
import matplotlib.pyplot as plt

class Board:
    def __init__(self,grid_graph=None):
        self.grid_graph = grid_graph
        self.n = grid_graph.n if grid_graph else None
        
    def find_single_node_components(self):
        # 找出所有孤立单元格（单独成块的节点）
        single_node_components = [c for c in nx.connected_components(self.grid_graph.G) if len(c) == 1]
        single_node = [node for component in single_node_components for node in component]
        return single_node
    
    def decide_single_node(self,title):
        plt.figure(figsize=(6, 6))
        
        for component in nx.connected_components(self.grid_graph.G):
            # 计算区块内数值的和
            component_sum = sum(self.grid_graph.latin_square.square[i][j] for (i, j) in component)

            if  len(component) == 1:
                (i, j) = component.pop()
                plt.text(j+0.5,i+0.6,component_sum,fontsize=40,color='red',ha='center',va='center')
                component.add((i,j))
            min_i, min_j = min(component)

            plt.text(min_j, min_i, component_sum, fontsize=20, color='blue', ha='left', va='top')

            for i, j in component:
                # 上方无区块元素时绘制实线
                if (i-1, j) not in component:
                    plt.plot([j, j+1], [i, i], color='black')
                else:
                    plt.plot([j, j+1], [i, i], linestyle='dashed',color='lightgray')
                # 下方无区块元素时绘制实线
                if (i+1, j) not in component:
                    plt.plot([j, j+1], [i+1, i+1], color='black')
                else:
                    plt.plot([j, j+1], [i+1, i+1], linestyle='dashed',color='lightgray')
                # 左侧无区块元素时绘制实线
                if (i, j-1) not in component:
                    plt.plot([j, j], [i, i+1], color='black')
                else:
                     plt.plot([j, j], [i, i+1], linestyle='dashed',color='lightgray')
                # 右侧无区块元素时绘制实线
                if (i, j+1) not in component:
                    plt.plot([j+1, j+1], [i, i+1], color='black')
                else:
                    plt.plot([j+1, j+1], [i, i+1], linestyle='dashed',color='lightgray')

        plt.xticks([])
        plt.yticks([])
        plt.gca().invert_yaxis()
        plt.suptitle(title,fontname="MS Gothic")
        plt.title('+',fontsize=20, loc='Right')
        plt.show()

当前任务与需求 #

目前已完成谜题生成程序，接下来需要开发求解器，判断生成的谜题是否无解、有唯一解或多解，无需找出所有解，只需判断解的数量范围。

计划采用**零压缩二叉决策图（ZDD, Zero-suppressed Binary Decision Diagrams）**实现求解器，寻求具体的实现建议与算法指导。

ZDD实现步骤建议 #

1. 问题建模：将谜题约束转化为ZDD变量与约束 #

• 变量定义：为每个单元格(i,j)定义n个布尔变量x_{i,j,k}（k∈[1,n]），表示单元格(i,j)是否填入数字k。
• 约束转化：
  • 拉丁方约束：
    • 行约束：对任意行i，每个数字k恰好对应一个j使得x_{i,j,k}=1；且每个j恰好对应一个k使得x_{i,j,k}=1。
    • 列约束：对任意列j，每个数字k恰好对应一个i使得x_{i,j,k}=1；且每个i恰好对应一个k使得x_{i,j,k}=1。
  • 区块约束：对每个区块，枚举所有满足运算规则（如和为指定值）的数字组合，每个组合对应一组变量的取值（选中组合内的数字对应的变量为1，其余为0）。

2. ZDD构建流程 #

• 步骤1：预处理孤立单元格
  利用已实现的find_single_node_components方法，先固定孤立单元格的数值（其运算值即为填入数字），减少需要处理的变量数量，缩小问题规模。
• 步骤2：构建拉丁方约束的ZDD
  分别构建行约束、列约束的ZDD，再将它们做交集运算，得到满足拉丁方规则的解空间ZDD。
• 步骤3：构建区块约束的ZDD
  对每个区块，生成所有符合运算规则的数字组合对应的ZDD，再将所有区块约束的ZDD与拉丁方约束的ZDD做交集运算，得到整个谜题的解空间ZDD。
• 步骤4：解数量判断
  计算ZDD根节点对应的解计数：
  • 计数=0：谜题无解
  • 计数=1：谜题有唯一解
  • 计数>1：谜题有多解

3. 优化技巧 #

• 变量排序：采用行优先（同一行内按列排序）的变量顺序，能大幅降低ZDD的节点数量，提升构建效率。
• 约束优先级：先处理强约束（如孤立单元格、固定值单元格），再处理弱约束，减少ZDD的规模。
• 利用现有ZDD库：可以使用Python的zdd库（如pyzdd）来简化ZDD的构建与运算，无需从零实现ZDD底层逻辑。

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