UD5工具箱
Regex Crossword（正则表达式填字游戏）
Regex Crossword 是一种将传统填字游戏与正则表达式结合的益智游戏。游戏提供一个空的字符网格（通常为正方形）和一组正则表达式规则。每行有一个对应的正则表达式约束该行的字符序列，每列也有一个对应的正则表达式约束该列的字符序列。玩家的目标是在网格中填入字符，使每一行和每一列的字符序列都满足对应的正则表达式。与传统填字游戏不同，Regex Crossword 不依赖词汇知识，而是考验玩家对正则表达式语法的理解和逻辑推理能力。
约束传播（Constraint Propagation）
约束传播是求解器使用的一种优化技术，通过逐步缩小每个格子的可能字符范围来减少搜索空间。基本思路是：对于每个格子，初始时可能的字符是字符集中的所有字符；然后根据行和列的正则表达式约束，逐步排除不可能的字符。例如，如果某个格子所在的行正则表达式要求第一个字符是元音字母，那么该格子的可能字符范围就会缩小为元音字母子集。约束传播会反复迭代，直到没有更多的字符可以被排除或所有格子都只有一种可能的字符。约束传播大幅减少了需要回溯搜索的空间，是求解器高效运行的关键。
回溯搜索（Backtracking Search）
回溯搜索是一种系统性的搜索算法，用于在约束传播无法完全求解时寻找满足所有约束的解。基本思路是：选择一个仍有多种可能字符的格子，尝试其中一个可能的字符，然后继续进行约束传播和搜索；如果当前选择导致矛盾（某个格子没有任何可能的字符），则回退到上一步，尝试另一个可能的字符。回溯搜索通过深度优先的方式遍历所有可能的字符组合，直到找到满足所有约束的解或确认无解。结合约束传播，回溯搜索可以高效地求解各种难度的 Regex Crossword 问题。
正则表达式（Regular Expression）
正则表达式是一种用于描述字符模式的语法，广泛应用于文本搜索、数据验证和字符串处理。在 Regex Crossword 中，正则表达式用于约束网格中每行或每列的字符序列。常用的正则表达式语法包括：点号（.）匹配任意单个字符；方括号（[abc]）匹配括号内包含的任意一个字符；星号（*）匹配前一个元素零次或多次；加号（+）匹配前一个元素一次或多次；问号（?）匹配前一个元素零次或一次；圆括号（(...)）用于分组；竖线（|）表示选择（或）；脱字符（^）匹配行首；美元符号（$）匹配行尾。
字符集（Character Set）
字符集是求解器中定义可用字符范围的配置。不同的 Regex Crossword 游戏使用不同的字符集，常见的有：大写字母（A-Z，26 个字符）、小写字母（a-z，26 个字符）、数字（0-9，10 个字符）、大写字母加数字（A-Z + 0-9，36 个字符）。字符集的选择直接影响求解的搜索空间大小——字符越少，每个格子的可能选择越少，搜索空间越小，求解速度越快。自定义字符集允许玩家输入任意字符组合，以适配各种特殊的 Regex Crossword 变体。
网格大小（Grid Size）
网格大小是 Regex Crossword 游戏中网格的行数和列数，决定了游戏的规模和难度。常见的网格大小有 2x2（4 个格子）、3x3（9 个格子）、4x4（16 个格子）、5x5（25 个格子）和 6x6（36 个格子）。网格越大，需要满足的约束越多，可能的解空间也越大，求解难度相应增加。非正方形网格（如 2x3、3x5）也在一些变体中出现。求解器支持任意行数和列数的网格。
固定约束（Fixed Constraint）
固定约束是指玩家手动输入到网格中已确定的字符。这些字符在求解过程中被视为硬性约束，求解器保证不会修改这些位置的字符。固定约束允许玩家保留自己通过推理得出的结论，只在不确定的位置使用算法求解。在网格界面中，固定约束的格子通常以不同的视觉样式（如黄色边框）标识，与求解器自动填充的字符形成对比。固定约束可以随时修改或清除。
解（Solution）
解是满足所有行和列正则表达式约束的网格填充方案。一个 Regex Crossword 问题可能有零个解（约束矛盾）、一个解（唯一解）或多个解（约束不够严格）。求解器可以查找第一个解、限制解的数量或查找所有可能的解。多个解的存在说明正则表达式约束不够严格，存在多种满足条件的字符组合。在正式的 Regex Crossword 游戏中，通常设计为有唯一解。
回溯搜索中的剪枝（Pruning）
剪枝是回溯搜索中的优化技术，用于提前终止不可能产生解的搜索分支。在 Regex Crossword 求解中，剪枝通常通过约束传播实现：在每次尝试填入一个字符后，立即进行约束传播检查是否产生矛盾（某个格子没有任何可能的字符）。如果检测到矛盾，则不需要继续搜索该分支，直接回退。剪枝大幅减少了实际需要探索的搜索空间，使求解器能够高效处理较大的网格和复杂的正则表达式。