标题
十六宫数独
题目描述
十六宫数独（Hexadoku）是 数独的 加强版。
给定一个 的方格盘，其中一部分格子已经填好了符号。你需要在剩余的格子中填入符号，使得：
- 每一行中，
0 到 9 以及 a 到 f 共 个符号恰好各出现一次；
- 每一列中，这 个符号恰好各出现一次；
- 每个 的粗线宫（共 个）中，这 个符号恰好各出现一次。
现在给出 个未填满的十六宫数独，请你分别把它们补充完整并输出。
数据保证：每个数独至少有一个解。SPJ 会校验你输出的解与题目某个合法解完全一致即通过，不要求唯一。
输入格式
输入第一行一个整数 ，表示数独的个数。
接下来依次给出 个数独。每个数独占 行，每行一个长度为 的字符串，由数字 0-9、小写字母 a-f 以及 x 组成，表示该行的 个格子；其中 x 表示该格待填，其余字符表示已填好的符号。
相邻两个数独之间用一个空行分隔。
输出格式
按照输入顺序输出 个完整的数独。每个数独占 行，每行 个字符（0-9、a-f）。
相邻两个数独之间用一个空行分隔。
数据范围与提示
对于全部数据，，每个数独保证至少有一个解。
设每个数独中已填好的符号个数为 （满盘共 格）。本题按子任务（subtask）计分，每个子任务内采用 min 计分——只要其中任意一个测试点未通过，整个子任务记 分，后续子任务仍继续评测：
| 子任务 |
分值 |
数据约束 |
| Subtask 1 |
|
|
| Subtask 2 |
|
|
| Subtask 3 |
|
| Subtask 4 |
|
|
| Subtask 5 |
|
|
| Subtask 6 |
|
|
共 组测试数据，每个子任务 组。
提示： 的搜索空间远大于 ，请使用回溯搜索并利用行、列、宫剪枝；每次挑选候选符号最少的格子进行填写（MRV 启发式）可以显著减少搜索量。提示数 时，纯 MRV 回溯在时限内通常不够，必须配合约束传播：
- naked singles：每次填格后若某格只剩一个候选，立即填入并重复；
- hidden singles（推荐）：某行/列/宫的某个符号只有一个可放位置时立即填入；
- 或者直接采用 Dancing Links / 精确覆盖（按 4 类约束建 1024 列的稀疏矩阵，用最少覆盖列的启发式）。
Subtask 6 提示数最少，传播是必要条件，Dancing Links 通常最快。