数织求解脚本技术文档

目录

前言

一、脚本概述

二、核心设计思路

1. 技术路线

三、核心模块说明

1. 预生成查表字典模块（pregenPermDict函数）

功能

实现逻辑

输入输出

2. 复杂度计算模块（calculateComplexity函数）

功能

复杂度分层规则

实现逻辑

3. 行 / 列处理核心模块（processLineWithLookup函数）

功能

实现流程

关键代码（位运算修复）

4. 迭代控制模块

功能

核心逻辑

四、使用说明

1. 前置条件

2. 参数调整

3. 运行流程

五、效果验证

六、后续优化方向

代码传送门

实战效果

前言

之前我们介绍了小游戏图案生成的代码，今天我们来求解。传送门

前后给AI提了很多需求，第一天AI给出的程序求解出来给我全部铺满了。最后是给了AI几百字的程序设计提示才完成。这里摘要两段给AI的算法设计思路。

献丑！

1好的，我们继续。目前你生成的还是不对。我重新给一下整体算法思路设计。迭代有大迭代和小迭代。大迭代包括15次行迭代和15次列迭代。每次迭代只标注确定的0和1。每次迭代可以利用之前标注的0和1，来确定新的0和1，每次迭代只能修改不确定的量，变为0或者1。不限制每次迭代修改格子状态的次数。最关键的是每次迭代的设计，要求必须只能修改确定的格子，为此需要引入每行或每列的复杂度。复杂度的计算依据未确定的格子数和数字的构成，比如某一行有15个格子没有确定，但是数字是14，复杂度很低。如果数字是1 3 1，那就很复杂了。随着格子确定越来越多，复杂度会逐渐降低。我们优先处理复杂度低的迭代，复杂度高的迭代可以暂时跳过等待其他迭代更新更多的格子。如果一整个大迭代你都没有更新任何格子，你可以跳出说明太复杂，我们后续优化。核心是你可以解不出，但是不要给出错误答案，这样我们可以逐步改进求解算法。

2 计算复杂度函数大致对的，你的迭代可以不用排序，就按顺序迭代每一行，每次迭代的时候计算复杂度就可以了，复杂度过高就不用更新当前行或列，我给你个阈值5吧，当所有行列的阈值都超过5时，你不用更新任何格子，结束迭代输出当前问题过于困难，之后我慢慢调整。在复杂度低的迭代中，我建议你使用遍历的方式，查找确定的格子，2的15次不算多，你可以生成一个表，为2的15次个数对应的辅助数字，遍历的时候查表即可。我所指的遍历的方式是通过查表，找到当前辅助数字代表的所有可能，然后按位与和按位或操作找到确定的0或1，如果已有确定的位置，要先剔除掉不符合该位置的数

一、脚本概述

本脚本是基于查表 + 位运算 + 复杂度控制的数织（Nonogram）解谜工具，核心目标是通过枚举有效排列、位运算求交集，严格标注 100% 确定的格子，避免错误并高效收敛。

二、核心设计思路

1. 技术路线

• 查表预生成：预计算所有可能的二进制排列（2¹⁵=32768 种），通过字典实现 O (1) 快速查询；
• 复杂度控制：仅处理低复杂度行 / 列，避免无意义计算；
• 位运算求交集：通过逐次累积的按位与 / 或运算，快速找到所有有效排列的 “必 1 格” 和 “必 0 格”；
• 迭代约束：按顺序遍历行 / 列，仅更新不确定格，确保结果无错误。

三、核心模块说明

1. 预生成查表字典模块（pregenPermDict函数）

功能

预计算 0~32767（2¹⁵-1）所有十进制数对应的 15 位二进制数组，存储到字典中，避免重复计算。

实现逻辑

matlab

function permDict = pregenPermDict(N) permDict = containers.Map('KeyType', 'uint32', 'ValueType', 'any'); for dec = 0:(2^N - 1) binStr = dec2bin(dec, N); % 十进制转N位二进制字符串 binArr = str2num(binStr')';% 字符串转1xN二进制数组 permDict(uint32(dec)) = binArr; end end

输入输出

• 输入：N（网格尺寸，如 15）；
• 输出：permDict（字典，key = 十进制数，value = 对应的 1xN 二进制数组）。

2. 复杂度计算模块（calculateComplexity函数）

功能

量化行 / 列的解谜难度，仅处理复杂度≤阈值的行 / 列。

复杂度分层规则

实现逻辑

matlab

function comp = calculateComplexity(line, hint, gridSize) uncertain_num = sum(line == 0.5); hint_seg_num = length(hint); hint_fill_num = sum(hint); if uncertain_num == 0; comp=0; return; end if hint_fill_num == 0; comp=1; return; end if hint_seg_num == 1 diff = uncertain_num - hint_fill_num; comp = diff<=1 ? 1 : (diff<=3 ? 3 : 5); return; end comp = 6; end

3. 行 / 列处理核心模块（processLineWithLookup函数）

功能

对单一行 / 列，通过查表筛选有效排列，再用位运算找必 1 / 必 0 格。

实现流程

关键代码（位运算修复）

% 必1格：逐次按位与（初始值=全1） andDec = uint32(2^gridSize - 1); for idx = 1:length(validPermDecs) andDec = bitand(andDec, uint32(validPermDecs(idx))); end must1Arr = permDict(andDec); % 必0格：逐次按位或（初始值=全0）→取反 orDec = uint32(0); for idx = 1:length(validPermDecs) orDec = bitor(orDec, uint32(validPermDecs(idx))); end must0Arr = 1 - permDict(orDec);

4. 迭代控制模块

功能

按顺序遍历行 / 列，实时计算复杂度，仅处理低复杂度行 / 列，无更新时终止。

核心逻辑

while bigIter < maxBigIter % 1. 按顺序处理所有行（复杂度≤阈值） % 2. 按顺序处理所有列（复杂度≤阈值） % 3. 无更新或所有行列复杂度超阈值→终止 end

四、使用说明

1. 前置条件

• 需提前生成rowHints.mat和colHints.mat文件，存储行 / 列的提示数字；
• MATLAB 版本≥R2019b（支持containers.Map）。

2. 参数调整

• complexityThreshold：复杂度阈值（默认 5，可调整为 10 以处理更复杂的行 / 列）；
• maxBigIter：最大大迭代次数（默认 50）。

3. 运行流程

1. 加载提示数据；
2. 预生成查表字典；
3. 初始化网格；
4. 大迭代处理行 / 列；
5. 验证结果并可视化。

五、效果验证

以 15×15 数织为例（复杂度阈值 = 10）：

• 迭代次数：4 次大迭代后收敛；
• 结果：所有确定格子均符合提示约束，无错误；
• 效率：32768 次查表 + 位运算仅需毫秒级

六、后续优化方向

1. 支持更大网格（如 20×20）：优化查表字典的内存占用；
2. 进阶规则：添加 X-Wing、剑鱼法等高级解谜规则，提升复杂行 / 列的处理能力；
3. 可视化增强：区分 “必 1 格”“必 0 格”“不确定格” 的显示样式。

代码传送门

下载

实战效果

load('rowHints.mat'); load('colHints.mat'); %分别修改行，列的提示数字 save('rowHints.mat','rowHints'); save('colHints.mat','colHints');