Zebra Puzzle Generator 解析用人类式演绎求解器生成多项式时间可解的斑马逻辑谜题【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research斑马谜题Zebra Puzzle是一类经典的约束逻辑谜题若干个实体排成一排每类属性国籍、颜色、饮品等在 n 个位置上恰好出现一次玩家只能依据若干条线索推理出完整排布。Google Research 开源仓库中的zebra_puzzle_generator项目提供了一个与众不同的生成器——它不以“有解”为终点而是要求生成的谜题必须能被一个只允许特定推理规则的人类式求解器解出从而在设计上保证所有谜题可在多项式时间内求解并同步产出逐步推理解答。本文基于 zebra_puzzle_generator/README.md 及仓库源码完整讲解该库的符号化数据模型、七种线索类型、生成—校验闭环、演绎推理求解器以及符号到自然语言的映射管线读者读完即可理解其工作原理并上手运行。一、项目概览一个“可解性优先”的斑马谜题生成库根据 zebra_puzzle_generator/README.md该项目是一个“用于生成随机斑马谜题及其解法的库”Library for generating random Zebra puzzles and their solutions。其核心设计理念可以提炼为三点随机生成每次运行都会采样全新的谜题实例而非从固定题库中抽取人类式可解生成器内部使用一个“只能做出特定类型演绎推理”only make certain types of deductions的求解器作为裁判只有被该求解器解出的谜题才会被接受。README 明确指出This ensures that all puzzles generated are solvable in polynomial time——即这一约束从设计上保证了所有生成谜题都在多项式时间内可解不会出现需要指数级穷举才能破解的谜题附带逐步解答生成过程不仅产出谜题本身还记录求解器的完整推理链可进一步映射为人类可读的逐步解题文本。仓库中该模块的文件构成如下均位于zebra_puzzle_generator/目录文件职责README.md项目说明与运行方式main.py命令行入口与默认超参数配置zebra_puzzle_generator.pyRandomZebraPuzzleGenerator生成器主逻辑zebra_solver.pyZebraPuzzleSolver演绎推理求解器zebra_utils.py数据模型、属性宇宙、符号↔自然语言映射工具requirements.txt依赖声明当前内容为python3从代码结构看整个模块遵循一条清晰的“符号化—生成—求解—映射”流水线zebra_utils.py定义符号化数据结构zebra_puzzle_generator.py负责采样线索并调用求解器验收zebra_solver.py以受限推理规则求解最后由SymbolicToNaturalLanguageMapper把符号谜题与符号解翻译成自然语言。二、快速开始从命令行生成谜题README 给出了唯一一条运行命令需在仓库根目录下执行python -m zebra_puzzle_generator/main.py入口脚本 main.py 基于absl.app搭建使用ml_collections.ConfigDict管理超参数。默认配置在get_config()中定义见 main.pyconfig ml_collections.ConfigDict() config.n 5 # 实体人数量 config.m1 5 # 类别属性数量随后 main.py 构造生成器并调用生成接口puzzle_generator zebra_puzzle_generator.RandomZebraPuzzleGenerator( ncfgs.n, m1cfgs.m1, m21, # 数值属性数量固定为 1 ) puzzle, ground_truth, _, detailed_solution, ordered_fills ( puzzle_generator.generate_symbolic_zebra_puzzle() )puzzleSymbolicZebraPuzzle包含过滤后的线索列表ground_truthSymbolicZebraGroundTruth即答案表detailed_solution逐步推理块每个块是一组ZebraSolverStepordered_fills按推理顺序排列的“填格”信息。环境说明requirements.txt 目前只声明了python3但源码实际导入了abslapp/logging与ml_collections因此运行前需要确保这两个第三方库可用例如pip install absl-py ml-collections。三、符号化数据模型谜题在代码中如何表示所有核心数据结构定义在 zebra_utils.py 中均为dataclassSymbolicZebraPuzzle谜题本体字段n实体数、m1类别属性数、m2数值属性数当前仅支持 1、clues线索列表Clue一条线索字段number编号从 1 起、clue_type线索类型字符串、lhs_list/rhs_list实体列表用于inbetween等涉及多个实体的线索SymbolicZebraGroundTruth标准答案核心字段是answer_table——一个(m1m2) × n的二维表第 0 行固定为位置索引[0, 1, ..., n-1]其余每行是某个属性值在 n 个位置上的一个排列ZebraSolverStep求解器的一步推理记录包含用到的clue_list、推理原因reason、辅助信息auxiliary_info以及当时的答案表快照current_answer_table——它是生成“逐步解答”的原始素材。实体的统一表示是一个三元组(类型, 属性下标, 值)(n, attr, value)数值属性numerical实体如“住在第 3 栋房子的人”(c, attr, value)类别属性categorical实体如“喜欢可乐的人”。get_attr_num()负责把实体映射到答案表中的行号数值实体行号即其属性下标类别实体行号需要加上m2偏移见 zebra_utils.pyconvert_to_readable_entity()则反向把“行号 值”还原成实体元组。属性宇宙Attribute Universe是自然语言层的内容来源。zebra_utils.py 定义了Attribute类字段包括attr_typecategorical/numerical、name、values候选值列表、verb搭配动词、referring_phrase_generator指代短语生成函数、comparatory_phrases比较短语仅数值属性等。仓库内置了丰富的预置属性类别属性CATEGORICAL_ATTRIBUTES见 zebra_utils.pyname32 个名字、nationality32 个国家、house_color10 种颜色、drink、car、sport、cigarette、musical_instrument、food、profession、hobby37 项、animal百余项等 20 余类数值属性NUMERICAL_ATTRIBUTES见 zebra_utils.pyhouse_position1–10用于“在左/在右/相邻”类空间关系、age10–25 岁、height_in_inches150–170 英寸并配有neighbor_phrase、immediate_left_phrase等短语模板。映射器在生成文本时会随机抽取 m1 个类别属性并为每个属性随机采样 n 个互不重复的值见 zebra_utils.py因此每次生成的谜题在主题和用词上都千差万别。四、七种线索类型与抽样权重生成器支持 7 种线索类型默认权重定义在 zebra_puzzle_generator.pyclue_type_weights: Dict[str, int] { : 4, !: 1, nbr: 2, ends: 2, immediate-left: 2, left-of: 2, inbetween: 1}线索类型语义以自然语言表达默认权重某实体就是某实体同一位置4!某实体不是某实体不同位置1nbr某实体与某实体相邻2ends某实体位于两端之一2immediate-left某实体紧挨在某实体左边2left-of某实体在某实体左侧的某处2inbetween某实体位于另两个实体之间有序1权重可通过构造函数的clue_type_weights参数覆盖见 zebra_puzzle_generator.py。需要注意一个边界条件当实体数n 3时生成器会把inbetween的权重置 0因为少于 3 个实体时无法形成“夹在中间”的合法线索见 zebra_puzzle_generator.py。生成线索时每种类型还有各自的采样约束例如/!的左右属性不允许相同避免冗余immediate-left/left-of要求左侧实体不在最右端inbetween要求三个实体在答案表中严格递增排列且中间实体必须存在见 zebra_puzzle_generator.py。这些约束都由一个共享的 ground truth 答案表驱动保证采样出的线索必然与真实答案一致。五、谜题生成流程从答案表到可解线索集RandomZebraPuzzleGenerator.generate_symbolic_zebra_puzzle()见 zebra_puzzle_generator.py是生成器的核心整体是一个“采样线索 → 校验去重 → 求解器验收 → 迭代直到可解”的闭环第 1 步采样答案表。首先生成一个随机的 ground truth第 0 行为位置索引其余每一行是属性值的一个随机排列。该表既是谜题的隐藏答案也是后续所有线索采样的“真值来源”。第 2 步偏置采样线索。生成器维护sampled_clue_dict与sampled_attr_dict两个统计字典。sample_attr()见 zebra_puzzle_generator.py在无中间结果时按1/(eps 已采样次数)反比加权选择属性并把数值属性的权重额外除以 5 以“保持数值属性稀缺”sample_entity()见 zebra_puzzle_generator.py则优先选择尚未填满的行与未填充的位置。这种“偏向未解部分”的策略在源码注释中被明确说明有助于减少冗余线索让生成器更快收敛到可解谜题。第 3 步去重与去冗余。每条新线索都要经过两道闸门check_duplicate()见 zebra_puzzle_generator.py按线索类型检查是否与已有线索语义重复例如A B与B A视为重复check_redundant()见 zebra_utils.py若线索涉及的实体都已在当前答案表中被确定位置则该线索不再提供任何新信息直接丢弃。第 4 步求解器验收。只有积累到超过 4 条线索后才会运行求解器源码注释说明求解开销较大见 zebra_puzzle_generator.py。这里以hard_deduceFalse调用ZebraPuzzleSolver.solve()——也就是说验收标准是谜题必须能被“纯人类式”的简单演绎推理解出。verboseTrue时还会打印当前已解百分比fraction_answer_table_solved与线索数量。循环持续到求解器返回solvedTrue。第 5 步过滤未使用线索。谜题可解后生成器通过find_clues_used()见 zebra_puzzle_generator.py扫描求解器的推理链剔除那些从未被用到的线索并重新编号见 zebra_puzzle_generator.py得到精简、无冗余线索的最终谜题。第 6 步对称性打散与最终求解。为了让谜题表达更多样生成器对、!、nbr三类对称线索以约 25% 的概率交换左右操作数flip 0.75见 zebra_puzzle_generator.py。最后用相同求解器重新求解一遍收集按推理顺序排列的fills列表每次推理块新增的填格作为下游自然语言解答的基础。六、人类式演绎求解器推理规则与多项式时间保证ZebraPuzzleSolverzebra_solver.py同时维护两张核心表答案表answer table(m1m2) × n第 0 行固定为位置其余单元格初始为None推理过程中逐步被填实候选表possible answers每个单元格保存一个候选值列表初始为完整值域推理时不断收缩。is_solved()检查答案表是否全部填满check_invalid_state()校验“每行取值唯一”等一致性约束见 zebra_solver.py。6.1 按线索类型实施的推理规则deduce_from_clue_list()见 zebra_solver.py是推理引擎的主体对每条线索执行对应的确定性规则每条规则产生带reason标签的ZebraSolverStep线索推理模式reason行为,grounded一侧实体已确定位置则把另一侧实体填入同一位置,negative-grounded两侧均未确定时依据已填位置与候选关系互相剔除候选值!!,grounded一侧已确定位置从该位置剔除另一侧实体nbrnbr,grounded/nbr,possible-locations已确定一侧时排除非相邻位置均未确定时利用“相邻”约束互相收缩候选位置endsends,one-end-filled/ends,middle-positions一端被占则填入另一端或从所有中间位置剔除该实体immediate-leftimmediate-left,grounded/immediate-left,possible-locations直接填入紧邻位置或基于候选位置互相排除left-ofleft-of,unique-grounded/left-of,possible-locations结合最左/最右可行位置收缩候选唯一时直接填表inbetweeninbetween,possible-locations基于三实体的最左/最右可行位置交叉收缩候选此外还有全局性的fill_by_elimination()见 zebra_solver.py当某个单元格只剩一个候选值时直接填入单选填格或某个值在全行只剩一个可放位置时填入单位置填格并把结果记录为fill-by-elimination推理步。6.2 主循环线索组合的迭代演绎solve()方法见 zebra_solver.py的主循环策略是将线索构造成单条、两两排列、三元排列三种粒度的组合clue_singlets clue_pair_perms clue_triplet_perms不断尝试用这些组合进行演绎只要有一步填格成功就接受并继续同时动态检测哪些线索在当前答案表下已冗余check_redundant将其剔除后重新计算组合空间从而逐步缩小搜索范围。求解期间verboseTrue会打印每次“Progress!”以及当前的答案表。6.3 硬推理hard_deduce与计算边界求解器还实现了一个hard_deduce_from_clue_list()见 zebra_solver.py当简单演绎无法推进时对候选位置数较少的实体做受限的穷举分配验证对 4 条、5 条线索的组合施加 20 000 / 10 000 的数量上限来控制搜索空间见 zebra_solver.py。但生成器在验收与最终求解时都显式传入hard_deduceFalse见 zebra_puzzle_generator.py这正是 README 所强调的“人类式求解器”的落点被接受的所有谜题都只依赖上述确定性、局部的演绎规则即可解出从而在推理层避免了指数级回溯保证了多项式时间可解性。七、符号到自然语言的映射谜题文本与逐步解答SymbolicToNaturalLanguageMapperzebra_utils.py负责把符号谜题、符号解与答案表渲染成人类可读的文本是“同时生成逐步解答”这一目标的关键实现。谜题前言preamble见 zebra_utils.py会生成类似这样的开场白There are 5 people next to each other in a row who have the following characteristics. Everyone has a different name: Alex, Barbara, Bob, Charlie, Doug. ... Match the people to the correct value for each of their characteristics using the clues provided below.线索文本map_symbolic_clues()见 zebra_utils.py把每条符号线索翻译成带编号的英文陈述例如The person who likes Coke is the person who lives in the blue house.nbrThe person who drinks tea lives next to the person who drives a Honda.endsThe person who smokes Camel is at one of the ends.inbetweenThe person who plays tennis is somewhere in between the person who likes cats and the person who is 25 years old in that order.数值化问题与答案create_puzzle_question_and_answer()见 zebra_utils.py从求解链的中间推理块与最后推理块中各取一个“填格”构造一个可自动判分的数值问题设两个实体最终位置分别为 $x$、$y$求 $(n1)y x$ 的值同时返回带推理过程的answer_with_cot与纯数值answer非常便于评测或微调场景使用。逐步解答文本map_symbolic_solution()见 zebra_utils.py把symbolic_solution中每个ZebraSolverStep按reason分派到对应的自然语言模板例如fill-by-eliminationHence, we have that only the person who drinks tea can occur at the 3rd position.,groundedSince we know that the person who likes Coke is at the 2nd position, we use Clue 1 to deduce that the person who lives in the blue house is also at the 2nd position.hard-deduceClues 1 and 3 together imply that the person who likes cats can only occur at the 4th position.每个推理块末尾还会用get_answer_table_as_text()见 zebra_utils.py渲染当前答案表的文本表格最终给出“Hence the solved table indicating everybodys position is:”以及完整排布——这正是文档所称“generate the step-by-step solution to the puzzles”的完整形态。八、许可证与使用边界根据 README.md 的 License 说明Zebra Puzzle Generator 采用Apache License, Version 2.0开源该模块不是 Google 官方支持的产品not an officially supported Google product仓库相关疑问可联系nishanthdgoogle.com。使用层面的两个实际边界也需要留意其一当前实现只支持 1 个数值属性生成器与数据结构中均有m2 1的断言/注释见 zebra_puzzle_generator.py其二main.py只演示了符号层面的生成与求解若需要自然语言谜题文本需要进一步调用SymbolicToNaturalLanguageMapper完成映射。附源码阅读索引运行入口与默认参数zebra_puzzle_generator/main.py生成器主逻辑线索采样、去重、验收、过滤zebra_puzzle_generator/zebra_puzzle_generator.py演绎求解器推理规则、消去法、硬推理zebra_puzzle_generator/zebra_solver.py数据模型、属性宇宙、符号↔自然语言映射zebra_puzzle_generator/zebra_utils.py依赖声明zebra_puzzle_generator/requirements.txt综上zebra_puzzle_generator的价值不在于“能生成谜题”而在于把“人类式可解、多项式时间可解、附带逐步解答”作为一等公民内建到生成管线中求解器既是验收裁判又是解答生成器这种“生成—求解互为校验”的架构对任何希望构造可控难度、可自动判分推理数据集的研究与工程场景都具有直接的参考意义。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Zebra Puzzle Generator 解析：用人类式演绎求解器生成多项式时间可解的斑马逻辑谜题
Zebra Puzzle Generator 解析用人类式演绎求解器生成多项式时间可解的斑马逻辑谜题【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research斑马谜题Zebra Puzzle是一类经典的约束逻辑谜题若干个实体排成一排每类属性国籍、颜色、饮品等在 n 个位置上恰好出现一次玩家只能依据若干条线索推理出完整排布。Google Research 开源仓库中的zebra_puzzle_generator项目提供了一个与众不同的生成器——它不以“有解”为终点而是要求生成的谜题必须能被一个只允许特定推理规则的人类式求解器解出从而在设计上保证所有谜题可在多项式时间内求解并同步产出逐步推理解答。本文基于 zebra_puzzle_generator/README.md 及仓库源码完整讲解该库的符号化数据模型、七种线索类型、生成—校验闭环、演绎推理求解器以及符号到自然语言的映射管线读者读完即可理解其工作原理并上手运行。一、项目概览一个“可解性优先”的斑马谜题生成库根据 zebra_puzzle_generator/README.md该项目是一个“用于生成随机斑马谜题及其解法的库”Library for generating random Zebra puzzles and their solutions。其核心设计理念可以提炼为三点随机生成每次运行都会采样全新的谜题实例而非从固定题库中抽取人类式可解生成器内部使用一个“只能做出特定类型演绎推理”only make certain types of deductions的求解器作为裁判只有被该求解器解出的谜题才会被接受。README 明确指出This ensures that all puzzles generated are solvable in polynomial time——即这一约束从设计上保证了所有生成谜题都在多项式时间内可解不会出现需要指数级穷举才能破解的谜题附带逐步解答生成过程不仅产出谜题本身还记录求解器的完整推理链可进一步映射为人类可读的逐步解题文本。仓库中该模块的文件构成如下均位于zebra_puzzle_generator/目录文件职责README.md项目说明与运行方式main.py命令行入口与默认超参数配置zebra_puzzle_generator.pyRandomZebraPuzzleGenerator生成器主逻辑zebra_solver.pyZebraPuzzleSolver演绎推理求解器zebra_utils.py数据模型、属性宇宙、符号↔自然语言映射工具requirements.txt依赖声明当前内容为python3从代码结构看整个模块遵循一条清晰的“符号化—生成—求解—映射”流水线zebra_utils.py定义符号化数据结构zebra_puzzle_generator.py负责采样线索并调用求解器验收zebra_solver.py以受限推理规则求解最后由SymbolicToNaturalLanguageMapper把符号谜题与符号解翻译成自然语言。二、快速开始从命令行生成谜题README 给出了唯一一条运行命令需在仓库根目录下执行python -m zebra_puzzle_generator/main.py入口脚本 main.py 基于absl.app搭建使用ml_collections.ConfigDict管理超参数。默认配置在get_config()中定义见 main.pyconfig ml_collections.ConfigDict() config.n 5 # 实体人数量 config.m1 5 # 类别属性数量随后 main.py 构造生成器并调用生成接口puzzle_generator zebra_puzzle_generator.RandomZebraPuzzleGenerator( ncfgs.n, m1cfgs.m1, m21, # 数值属性数量固定为 1 ) puzzle, ground_truth, _, detailed_solution, ordered_fills ( puzzle_generator.generate_symbolic_zebra_puzzle() )puzzleSymbolicZebraPuzzle包含过滤后的线索列表ground_truthSymbolicZebraGroundTruth即答案表detailed_solution逐步推理块每个块是一组ZebraSolverStepordered_fills按推理顺序排列的“填格”信息。环境说明requirements.txt 目前只声明了python3但源码实际导入了abslapp/logging与ml_collections因此运行前需要确保这两个第三方库可用例如pip install absl-py ml-collections。三、符号化数据模型谜题在代码中如何表示所有核心数据结构定义在 zebra_utils.py 中均为dataclassSymbolicZebraPuzzle谜题本体字段n实体数、m1类别属性数、m2数值属性数当前仅支持 1、clues线索列表Clue一条线索字段number编号从 1 起、clue_type线索类型字符串、lhs_list/rhs_list实体列表用于inbetween等涉及多个实体的线索SymbolicZebraGroundTruth标准答案核心字段是answer_table——一个(m1m2) × n的二维表第 0 行固定为位置索引[0, 1, ..., n-1]其余每行是某个属性值在 n 个位置上的一个排列ZebraSolverStep求解器的一步推理记录包含用到的clue_list、推理原因reason、辅助信息auxiliary_info以及当时的答案表快照current_answer_table——它是生成“逐步解答”的原始素材。实体的统一表示是一个三元组(类型, 属性下标, 值)(n, attr, value)数值属性numerical实体如“住在第 3 栋房子的人”(c, attr, value)类别属性categorical实体如“喜欢可乐的人”。get_attr_num()负责把实体映射到答案表中的行号数值实体行号即其属性下标类别实体行号需要加上m2偏移见 zebra_utils.pyconvert_to_readable_entity()则反向把“行号 值”还原成实体元组。属性宇宙Attribute Universe是自然语言层的内容来源。zebra_utils.py 定义了Attribute类字段包括attr_typecategorical/numerical、name、values候选值列表、verb搭配动词、referring_phrase_generator指代短语生成函数、comparatory_phrases比较短语仅数值属性等。仓库内置了丰富的预置属性类别属性CATEGORICAL_ATTRIBUTES见 zebra_utils.pyname32 个名字、nationality32 个国家、house_color10 种颜色、drink、car、sport、cigarette、musical_instrument、food、profession、hobby37 项、animal百余项等 20 余类数值属性NUMERICAL_ATTRIBUTES见 zebra_utils.pyhouse_position1–10用于“在左/在右/相邻”类空间关系、age10–25 岁、height_in_inches150–170 英寸并配有neighbor_phrase、immediate_left_phrase等短语模板。映射器在生成文本时会随机抽取 m1 个类别属性并为每个属性随机采样 n 个互不重复的值见 zebra_utils.py因此每次生成的谜题在主题和用词上都千差万别。四、七种线索类型与抽样权重生成器支持 7 种线索类型默认权重定义在 zebra_puzzle_generator.pyclue_type_weights: Dict[str, int] { : 4, !: 1, nbr: 2, ends: 2, immediate-left: 2, left-of: 2, inbetween: 1}线索类型语义以自然语言表达默认权重某实体就是某实体同一位置4!某实体不是某实体不同位置1nbr某实体与某实体相邻2ends某实体位于两端之一2immediate-left某实体紧挨在某实体左边2left-of某实体在某实体左侧的某处2inbetween某实体位于另两个实体之间有序1权重可通过构造函数的clue_type_weights参数覆盖见 zebra_puzzle_generator.py。需要注意一个边界条件当实体数n 3时生成器会把inbetween的权重置 0因为少于 3 个实体时无法形成“夹在中间”的合法线索见 zebra_puzzle_generator.py。生成线索时每种类型还有各自的采样约束例如/!的左右属性不允许相同避免冗余immediate-left/left-of要求左侧实体不在最右端inbetween要求三个实体在答案表中严格递增排列且中间实体必须存在见 zebra_puzzle_generator.py。这些约束都由一个共享的 ground truth 答案表驱动保证采样出的线索必然与真实答案一致。五、谜题生成流程从答案表到可解线索集RandomZebraPuzzleGenerator.generate_symbolic_zebra_puzzle()见 zebra_puzzle_generator.py是生成器的核心整体是一个“采样线索 → 校验去重 → 求解器验收 → 迭代直到可解”的闭环第 1 步采样答案表。首先生成一个随机的 ground truth第 0 行为位置索引其余每一行是属性值的一个随机排列。该表既是谜题的隐藏答案也是后续所有线索采样的“真值来源”。第 2 步偏置采样线索。生成器维护sampled_clue_dict与sampled_attr_dict两个统计字典。sample_attr()见 zebra_puzzle_generator.py在无中间结果时按1/(eps 已采样次数)反比加权选择属性并把数值属性的权重额外除以 5 以“保持数值属性稀缺”sample_entity()见 zebra_puzzle_generator.py则优先选择尚未填满的行与未填充的位置。这种“偏向未解部分”的策略在源码注释中被明确说明有助于减少冗余线索让生成器更快收敛到可解谜题。第 3 步去重与去冗余。每条新线索都要经过两道闸门check_duplicate()见 zebra_puzzle_generator.py按线索类型检查是否与已有线索语义重复例如A B与B A视为重复check_redundant()见 zebra_utils.py若线索涉及的实体都已在当前答案表中被确定位置则该线索不再提供任何新信息直接丢弃。第 4 步求解器验收。只有积累到超过 4 条线索后才会运行求解器源码注释说明求解开销较大见 zebra_puzzle_generator.py。这里以hard_deduceFalse调用ZebraPuzzleSolver.solve()——也就是说验收标准是谜题必须能被“纯人类式”的简单演绎推理解出。verboseTrue时还会打印当前已解百分比fraction_answer_table_solved与线索数量。循环持续到求解器返回solvedTrue。第 5 步过滤未使用线索。谜题可解后生成器通过find_clues_used()见 zebra_puzzle_generator.py扫描求解器的推理链剔除那些从未被用到的线索并重新编号见 zebra_puzzle_generator.py得到精简、无冗余线索的最终谜题。第 6 步对称性打散与最终求解。为了让谜题表达更多样生成器对、!、nbr三类对称线索以约 25% 的概率交换左右操作数flip 0.75见 zebra_puzzle_generator.py。最后用相同求解器重新求解一遍收集按推理顺序排列的fills列表每次推理块新增的填格作为下游自然语言解答的基础。六、人类式演绎求解器推理规则与多项式时间保证ZebraPuzzleSolverzebra_solver.py同时维护两张核心表答案表answer table(m1m2) × n第 0 行固定为位置其余单元格初始为None推理过程中逐步被填实候选表possible answers每个单元格保存一个候选值列表初始为完整值域推理时不断收缩。is_solved()检查答案表是否全部填满check_invalid_state()校验“每行取值唯一”等一致性约束见 zebra_solver.py。6.1 按线索类型实施的推理规则deduce_from_clue_list()见 zebra_solver.py是推理引擎的主体对每条线索执行对应的确定性规则每条规则产生带reason标签的ZebraSolverStep线索推理模式reason行为,grounded一侧实体已确定位置则把另一侧实体填入同一位置,negative-grounded两侧均未确定时依据已填位置与候选关系互相剔除候选值!!,grounded一侧已确定位置从该位置剔除另一侧实体nbrnbr,grounded/nbr,possible-locations已确定一侧时排除非相邻位置均未确定时利用“相邻”约束互相收缩候选位置endsends,one-end-filled/ends,middle-positions一端被占则填入另一端或从所有中间位置剔除该实体immediate-leftimmediate-left,grounded/immediate-left,possible-locations直接填入紧邻位置或基于候选位置互相排除left-ofleft-of,unique-grounded/left-of,possible-locations结合最左/最右可行位置收缩候选唯一时直接填表inbetweeninbetween,possible-locations基于三实体的最左/最右可行位置交叉收缩候选此外还有全局性的fill_by_elimination()见 zebra_solver.py当某个单元格只剩一个候选值时直接填入单选填格或某个值在全行只剩一个可放位置时填入单位置填格并把结果记录为fill-by-elimination推理步。6.2 主循环线索组合的迭代演绎solve()方法见 zebra_solver.py的主循环策略是将线索构造成单条、两两排列、三元排列三种粒度的组合clue_singlets clue_pair_perms clue_triplet_perms不断尝试用这些组合进行演绎只要有一步填格成功就接受并继续同时动态检测哪些线索在当前答案表下已冗余check_redundant将其剔除后重新计算组合空间从而逐步缩小搜索范围。求解期间verboseTrue会打印每次“Progress!”以及当前的答案表。6.3 硬推理hard_deduce与计算边界求解器还实现了一个hard_deduce_from_clue_list()见 zebra_solver.py当简单演绎无法推进时对候选位置数较少的实体做受限的穷举分配验证对 4 条、5 条线索的组合施加 20 000 / 10 000 的数量上限来控制搜索空间见 zebra_solver.py。但生成器在验收与最终求解时都显式传入hard_deduceFalse见 zebra_puzzle_generator.py这正是 README 所强调的“人类式求解器”的落点被接受的所有谜题都只依赖上述确定性、局部的演绎规则即可解出从而在推理层避免了指数级回溯保证了多项式时间可解性。七、符号到自然语言的映射谜题文本与逐步解答SymbolicToNaturalLanguageMapperzebra_utils.py负责把符号谜题、符号解与答案表渲染成人类可读的文本是“同时生成逐步解答”这一目标的关键实现。谜题前言preamble见 zebra_utils.py会生成类似这样的开场白There are 5 people next to each other in a row who have the following characteristics. Everyone has a different name: Alex, Barbara, Bob, Charlie, Doug. ... Match the people to the correct value for each of their characteristics using the clues provided below.线索文本map_symbolic_clues()见 zebra_utils.py把每条符号线索翻译成带编号的英文陈述例如The person who likes Coke is the person who lives in the blue house.nbrThe person who drinks tea lives next to the person who drives a Honda.endsThe person who smokes Camel is at one of the ends.inbetweenThe person who plays tennis is somewhere in between the person who likes cats and the person who is 25 years old in that order.数值化问题与答案create_puzzle_question_and_answer()见 zebra_utils.py从求解链的中间推理块与最后推理块中各取一个“填格”构造一个可自动判分的数值问题设两个实体最终位置分别为 $x$、$y$求 $(n1)y x$ 的值同时返回带推理过程的answer_with_cot与纯数值answer非常便于评测或微调场景使用。逐步解答文本map_symbolic_solution()见 zebra_utils.py把symbolic_solution中每个ZebraSolverStep按reason分派到对应的自然语言模板例如fill-by-eliminationHence, we have that only the person who drinks tea can occur at the 3rd position.,groundedSince we know that the person who likes Coke is at the 2nd position, we use Clue 1 to deduce that the person who lives in the blue house is also at the 2nd position.hard-deduceClues 1 and 3 together imply that the person who likes cats can only occur at the 4th position.每个推理块末尾还会用get_answer_table_as_text()见 zebra_utils.py渲染当前答案表的文本表格最终给出“Hence the solved table indicating everybodys position is:”以及完整排布——这正是文档所称“generate the step-by-step solution to the puzzles”的完整形态。八、许可证与使用边界根据 README.md 的 License 说明Zebra Puzzle Generator 采用Apache License, Version 2.0开源该模块不是 Google 官方支持的产品not an officially supported Google product仓库相关疑问可联系nishanthdgoogle.com。使用层面的两个实际边界也需要留意其一当前实现只支持 1 个数值属性生成器与数据结构中均有m2 1的断言/注释见 zebra_puzzle_generator.py其二main.py只演示了符号层面的生成与求解若需要自然语言谜题文本需要进一步调用SymbolicToNaturalLanguageMapper完成映射。附源码阅读索引运行入口与默认参数zebra_puzzle_generator/main.py生成器主逻辑线索采样、去重、验收、过滤zebra_puzzle_generator/zebra_puzzle_generator.py演绎求解器推理规则、消去法、硬推理zebra_puzzle_generator/zebra_solver.py数据模型、属性宇宙、符号↔自然语言映射zebra_puzzle_generator/zebra_utils.py依赖声明zebra_puzzle_generator/requirements.txt综上zebra_puzzle_generator的价值不在于“能生成谜题”而在于把“人类式可解、多项式时间可解、附带逐步解答”作为一等公民内建到生成管线中求解器既是验收裁判又是解答生成器这种“生成—求解互为校验”的架构对任何希望构造可控难度、可自动判分推理数据集的研究与工程场景都具有直接的参考意义。【免费下载链接】google-researchGoogle Research项目地址: https://gitcode.com/gh_mirrors/go/google-research创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考