以光速解决日本彩色填字游戏

日语填字游戏（也包括非图字游戏）是对像素图像进行加密的逻辑难题。 您需要使用位于行左侧和列上方的数字来解决填字游戏。

填字游戏的大小可以达到150x150。 播放器使用特殊的逻辑来计算每个单元的颜色。 对于初学者来说，该解决方案在填字游戏上可能需要花费几分钟，而在复杂的拼图上则需要数十小时。

好的算法可以更快地解决问题。 文本描述了如何编写一种使用最合适的算法（通常会导致一个解决方案）几乎立即生效的解决方案，以及它们的优化和C ++功能的使用（这将运行时间减少了数十倍）。

在Habr的移动版本中，可能不会显示文本中的公式（并非在所有移动浏览器中都显示）-如果您发现公式存在问题，请使用完整版本或其他移动浏览器

游戏规则

最初，填字游戏画布是白色的。 对于香草黑白填字游戏，您需要恢复黑色单元格的位置。

在黑白填字游戏中，每行（画布左侧）或每列（画布顶部）的数字数量显示相应行或列中有多少个黑色单元格组，数字本身显示这些组中每个单元包含多少个合并单元格。 一组数字 $$$[3，2，5]$ 表示在某一行中有三个连续的组 $$$3$ ， $$$2$ 和 $$$5$ 黑色单元格连续。 可以将组随机排列成一行，而不会违反相对顺序（数字指定了它们的长度，必须猜测位置），但是它们必须至少由一个白格分隔。

正确的例子

在彩色填字游戏中，每个组仍然具有自己的颜色-除白色外，任何其他颜色都是背景色。 可以将不同颜色的相邻组并排放置，但是对于相同颜色的相邻组，仍然需要至少一个白细胞分开。

什么不是日语填字游戏

每个像素图像都可以作为填字游戏进行加密。 但是，可能无法将其还原回来-产生的难题可能具有多个解决方案，或者具有一个解决方案，但不能从逻辑上解决。 然后必须使用量子计算机的萨满技术猜测游戏中剩余的细胞。

这样的填字游戏不是填字游戏，而是拼写狂。 我们相信正确的填字游戏是使您能够以合理的方式得出独特的解决方案。

“逻辑路径”是一种能力，可以分别考虑行/列或它们的交集来逐个还原每个单元格。 如果这不可能，那么考虑的答案选项的数量可能会非常多，远远超出一个人自己能计算出的数量。

错误的非方格图是唯一的解决方案，但无法正常解决。 橙色标记为“无法解决”的单元格。 取自维基百科。

对此限制的解释如下-在最一般的情况下，日语填字游戏是NP完全问题。 但是，如果有一种算法可以在每个时间点明确指示要进一步打开哪些单元格，那么猜测就不会成为完成NP的任务。 人类使用的所有填字游戏（方法除外） 蒙特卡洛 反复试验）基于此。

在大多数Orthodox填字游戏中，宽度和高度除以5，就没有可以立即计数的行（有色单元阻塞所有位置，或者根本不存在的行），并且互补色的数量受到限制。 这些要求不是必需的。

最简单的错误填字​​游戏：

|1 1| --+---+ 1| | 1| | --+---+ 

通常，使用“棋盘”图案模拟渐变的编码像素图不会向后解析。 最好了解一下是否在搜索中输入“ pixelart梯度”。 渐变就像这个2x2 fayl填字游戏。

可能的解决方案

我们有填字游戏的大小，颜色以及所有行和列的描述。 我如何从中组装图片：

全搜索

对于每个单元格，我们对所有可能的状态进行排序并检查是否令人满意。 黑白填字游戏的这种解决方案的复杂性 $$$O（N * M * {2} ^ {N * M}）$ ，用于颜色 $$$O（N * M * {颜色} ^ {N * M}）$ 。 与小丑分类类似，该解决方案也可以称为小丑。 适用于5x5尺寸。

回溯

整理了排列单元格水平组的所有可能方法。 我们将一组单元格放在一行中，检查它是否不破坏列组的描述。 如果破裂，我们再放1个单元格，然后再次检查。 设置-转到下一组。 如果您无法以任何方式放置一个组，我们将回退两个组，重新排列上一个组，依此类推，直到成功放置最后一个组。

每行分别

这个决定要好得多，这是真的。 我们可以分别分析每一行和每一列。 每行将尝试显示最大信息。

该行中每个单元的算法都可以学习更多信息-可能结果是无法以某种颜色对单元进行着色，组将不会收敛。 您无法立即完全扩展行，但是收到的信息将“帮助”更好地打开几列，并且当我们开始分析它们时，它们将再次“帮助”行，依此类推，直到所有单元格都具有一种可能的颜色。

真正真实的决定

一行，两种颜色

对某些单元格已经猜到的黑白“单线”进行有效猜测是一项非常艰巨的任务。 她在以下地方遇见：

• 在ACM ICPC 2006的八分之一决赛中， 您可以尝试自己解决问题 。 时间限制是1秒，组数限制是400，序列的长度也是400。与其他任务相比，它具有很高的复杂性。
• 2016年国际信息奥林匹克 - 条件 通过任务 。 时间限制是2秒，组数限制是100，行的长度是200'000。 这样的限制是过大的，但是解决ACM限制的问题可获得80/100分。 这里的水平也不令人失望，来自世界各地的残酷智商水平的学童已经接受了数年的培训以解决不同的技巧，然后他们去了奥林匹克竞赛（来自该国的只有4个人必须通过），他们决定进行2轮5小时的比赛 如果是史诗般的胜利（铜牌在不同年份中以138-240分获得青铜），则进入牛津大学，然后由清算公司提供给搜索部门，dakimakura拥有漫长而幸福的生活。

单色单行也可以用不同的方法解决，并且 $$$O（N * 2 ^ N）$ （枚举所有选项，检查是否正确，选择所有选项中颜色相同的单元格），以及在某种程度上不那么愚蠢。

主要思想是使用回溯的类似物，但无需进行不必要的计算。 如果我们以某种方式建立了多个组，并且现在处于某种类型的单元中，那么我们需要找出是否有可能从当前单元开始放置其余的组。

 def EpicWin(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertBlack(cell, len[group]) #    and CanInsertWhite(cell + len[group], 1) #    and EpicWin(group + 1, cell + len[group] + 1): #    win = True can_place_black[cell .. (cell + len[group] - 1)] = True can_place_white[cell + len[group]] = True; #         if CanInsertWhite(cell, 1) and EpicWin(group, cell + 1): win = True can_place_white[cell] = True return win EpicWin(0, 0) 

这种方法称为动态编程 。 伪代码得到简化，甚至计算出的值也不存储在此处。

需要使用CanInsertBlack/CanInsertWhite来检查理论上是否可以在正确的位置放置正确大小的组。 他们所需要做的就是确认在指定的单元格范围内没有“ 100％白色”单元格（用于第一个功能）或“ 100％黑色”单元格（对于第二个功能）。 他们可以为 $$$O（1）$ ，这可以使用部分金额来完成：

 white_counter = [ 0, 0, ..., 0 ] #   n def PrecalcWhite(): for i in range(0, (n-1)): if is_anyway_white[i]: # 1,  i-  100%  white_counter[i]++ if i > 0: white_counter[i] += white_counter[i - 1] def CanInsertBlack(cell, len): #     [cell, cell + len - 1] ans = white_counter[cell + len - 1] if cell > 0: ans -= white_counter[cell - 1] #  ans -     cell  (cell + len - 1) return ans == 0 

具有部分和的相同巫术等待形式的行

 can_place_black[cell .. (cell + len[group] - 1)] = True 

在这里，我们可以代替= True将数字增加1。并且，如果我们需要在某个数组中的某个段上进行大量添加 $$$数组$ ，此外，我们在使用其他数组之前不会使用此数组（他们说此任务是“离线解决”的），而不是循环：

 #     for i in range(L, R + 1): array[i]++ 

您可以这样做：

 #     array[L]++ array[R + 1]-- #    for i in range(1, n): array[i] += array[i - 1] 

因此，整个算法适用于 $$$O（k * n）$ 在哪里 $$$k$ -黑电池的组数， $$$n$ 是字符串的长度。 然后我们去了ACM ICPC的半决赛，或者获得了实习者的铜牌。 ACM解决方案（Java） 。 IOI解决方案（C ++） 。

一行多色

当我们仍然不清楚如何解决时，当我们切换到多色非图时，我们学到了一个可怕的事实-事实证明，每一列都受到所有列的神奇影响！ 通过一个示例可以更清楚地看到：

资料来源- 解决日语填字游戏的方法

虽然双色非图通常没有它，但它们不需要回顾正交朋友。
如图所示，在左边的示例中，三个最右端的单元格为空，因为如果您为这些单元格上色，则配置会中断 用来画自己的那些颜色 非白色。

但是这个笑话在数学上是可以确定的-每个单元格必须给一个数字，其中 $$$我$ 第ith位将表示是否可以给该单元格 $$$我$ 颜色。 最初，所有单元格都有一个值 $$$2 ^ {颜色}-1$ 。 动态的决定不会有太大变化。

您可以观察到以下效果：在相同的左示例中，根据行的版本，最右边的单元格可以具有蓝色或白色。
根据列的版本，此单元格具有绿色或白色。
根据常识版本，此单元将只有白色。 然后我们继续计算答案。

如果我们认为零位是“白色”，第一个是“蓝色”，第二个是“绿色”，则该行计算了最后一个单元的状态 $$$011$ 和列 $$$101$ 。 这意味着该单元的状态是真实的 $$$011 \＆101 = 001$

 source = [...] #   result = [0, 0, ..., 0] #   len = [...] #    clrs = [...] #    def CanInsertColor(color, cell, len): for i in range(cell, cell + len): if (source[i] & (1 << color)) == 0: #     color    return False; return True def PlaceColor(color, cell, len): for i in range(cell, cell + len): result[i] |= (1 << color) #   color  OR def EpicWinExtended(group, cell): if cell >= last_cell: #   return group == group_size win = False #        if group < group_size #    and CanInsertColor(clrs[group], cell, len[group]) #    and SequenceCheck() #       ,  #         and EpicWin(group + 1, cell + len[group]): #    win = True PlaceColor(clrs[group], cell, len[group]) PlaceColor(0, cell + len[group], 1) #   -    #         #   -  0 if CanInsertWhite(0, cell, 1) and EpicWinExtended(group, cell + 1): win = True PlaceColor(0, cell, 1) return win 

多行多色

不断更新所有行和列的状态（如上一段所述），直到没有一个单元具有一位以上。 在每次迭代中，在更新所有行和列之后，我们通过相互AND来更新其中所有单元格的状态。

初步结果

假设我们没有像啄木鸟那样编写代码，也就是说，我们不会错误地复制对象而不是通过引用传递对象，我们不会在任何地方发明自行车，我们也不会发明自行车，因为我们使用__builtin_popcount和__builtin_ctz （ gcc功能 ）进行位操作，所以一切都干净整洁。

让我们看一下程序的时间，该程序从文件中读取难题并完全解决。 值得评估编写和测试所有这些东西的机器的优势：

 RAM - 4GB  - AMD E1-2500,  1400MHz  L1 - 128KiB, 1GHz  L2 - 1MiB, 1GHz  - 2,  - 2   « SoC   »   2013    28  

显然，之所以选择这样的超级计算机，是因为对它的优化比对飞行的shaitan机器的影响更大。

因此，在最复杂的填字游戏上运行我们的算法（根据nonograms.ru）之后，我们得到的结果不是很好-从47到60秒（包括从文件和解决方案中读取）。 应该注意的是，网站上的“复杂性”是经过精心计算的-在该程序的所有版本中，相同的填字游戏也是最难的，而档案馆认为其他最复杂的填字游戏都处于最佳状态。

颜色填字游戏编号9596，最大难度

为了进行快速测试，对基准进行了功能测试。 为了获得他的数据，我使用特殊脚本使用nonograms.ru（这是Internet上最大的非图形档案之一）sparsil 4683彩色填字游戏（来自10906 ）和1406黑白（来自8293 ），使用特殊脚本并将其保存为程序可以理解的格式。 我们可以假设这些填字游戏是随机样本，因此基准测试将显示足够的平均值。 另外，在脚本中记录了几十个最“复杂”的填字游戏（也是最大的大小和颜色数量）的数量，以供笔装载。

最佳化

在这里，您可以看到可能的优化技术，这些技术（1）是在编写整个算法时进行的；（2）将工作时间从半分钟缩短到了几分之一秒；（3）这些优化可能会进一步有用。

在编写算法时

• 位操作的特殊功能，在我们的例子中， __builtin_popcount用于计数数字的二进制表示形式，而__builtin_ctz用于计算第一个最小单位之前的零个数。 这些功能可能不会在某些编译器中出现。 对于Windows，此类类似物适用：

 #ifdef _MSC_VER # include <intrin.h> # define __builtin_popcount __popcnt #endif 

• 阵列组织-较小的尺寸排在首位。 例如，最好使用数组[2] [3] [500] [1024]，而不要使用[1024] [500] [3] [2]。
• 最重要的是代码的一般性以及避免不必要的计算麻烦。

什么减少了工作时间

• 编译时的-O2标志。
• 为了不将完全解析的行/列再次投入算法，您可以在单独的std :: vector / array中为每行设置标志，用完整的解决方案标记它们，如果没有其他要解决的问题，不要放开。
• 一个动态问题的多次重复解决方案的细节表明，每次创建新的解决方案时，应重置一个特殊的数组，该数组包含标记问题的“已计算”部分的标志。 在我们的例子中，这是一个二维数组/向量，其中第一个维是组数，第二个是当前单元格（请参阅上面的EpicWin伪代码，该数组不是，但思路很明确）。 您可以执行此操作，而不是清零-让我们拥有一个“计时器”变量，该数组由数字组成，这些数字显示了该片最后一次被重新计数时的最后一个“时间”。 开始新任务时，“计时器”增加1。而不是检查布尔标志，应检查数组元素和“计时器”的相等性。 这在算法未涵盖所有可能状态的情况下尤其有效（这意味着将数组“归零”已经花了健康的时间）归零。
• 用STL中的类似物或更合适的东西替换相同类型的简单操作（带有赋值的循环等）。 有时它比自行车快。
• C ++中的std::vector<bool>将所有布尔值压缩为数字中的单个位，这比访问该地址上的常规值时慢一点。 如果程序非常非常频繁地使用这些值，则用整数类型替换布尔值会对性能产生良好的影响。
• 其他弱点可以通过探查器进行查找和编辑。 我本人使用Valgrind，它的性能分析很方便通过kCachegrind查看。 探查器内置在许多IDE中。

这些编辑结果足以在基准上获取此类数据：

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source2/ -e [2018-08-04 22:57:40.432] [Nonograms] [info] Starting a benchmark... [2018-08-04 22:58:03.820] [Nonograms] [info] Average time: 0.00497556, Median time: 0.00302781, Max time: 0.215925 [2018-08-04 22:58:03.820] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 22:58:03.820] [Nonograms] [info] 0.215925 seconds, file 9596 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.164579 seconds, file 4462 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.105828 seconds, file 15831 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.08827 seconds, file 18353 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0874717 seconds, file 10590 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0831248 seconds, file 4649 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0782811 seconds, file 11922 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0734325 seconds, file 4655 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.071352 seconds, file 10828 [2018-08-04 22:58:03.820] [Nonograms] [info] 0.0708263 seconds, file 11824 

 izaron@izaron:~/nonograms/build$ ./nonograms_solver -x ../../nonogram/source/ -e -b [2018-08-04 22:59:56.308] [Nonograms] [info] Starting a benchmark... [2018-08-04 23:00:09.781] [Nonograms] [info] Average time: 0.0095679, Median time: 0.00239274, Max time: 0.607341 [2018-08-04 23:00:09.781] [Nonograms] [info] Top 10 heaviest nonograms: [2018-08-04 23:00:09.781] [Nonograms] [info] 0.607341 seconds, file 5126 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.458932 seconds, file 19510 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.452245 seconds, file 5114 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.19975 seconds, file 18627 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.163028 seconds, file 5876 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.161675 seconds, file 17403 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.153693 seconds, file 12771 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.146731 seconds, file 5178 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.142732 seconds, file 18244 [2018-08-04 23:00:09.781] [Nonograms] [info] 0.136131 seconds, file 19385 

您可能会注意到，平均而言，黑白填字游戏比彩色填字游戏“难”。 这证实了游戏爱好者的观察，他们也认为“色彩”的平均解决起来比较容易。

因此，无需进行根本性的更改（例如用fastcall重写C或汇编程序插入中的所有代码并降低帧指针），就可以在一台非常普通的计算机上实现高性能。 Pareto原则可能适用于优化-事实证明，次要优化会产生很大影响，因为这段代码很关键，而且经常被调用。

进一步优化

以下方法可以大大提高程序性能。 其中有些功能并非在所有情况下都可以使用，但是在某些条件下不能使用。

• 用C风格和其他1972年重写代码。 我们将ifstream替换为模拟副本，将vector替换为数组，了解所有编译器选项，并为每个处理器时钟周期而战。
• 并行化。 例如，在代码中，有一段代码是行被顺序更新，然后是列：

  ... if (!UpdateGroupsState(solver, dead_rows, row_groups, row_masks)) { return false; } if (!UpdateGroupsState(solver, dead_cols, col_groups, col_masks)) { return false; } return true; 

这些函数彼此独立，除了变量求解器（OneLineSolver类型）外，它们没有共享内存，因此您可以创建两个求解器对象（这里显然只有一个是求解器），并在同一函数中启动两个线程。 效果是这样的：在颜色填字游戏中，“最难”的解决速度是原来的两倍，而在黑白中，解决速度最快的是三分之一，并且由于创建线程的成本相对较高，平均时间也有所增加。

但是总的来说，我不建议在当前程序中正确地使用它，而要冷静地使用它-首先，创建线程是一项昂贵的操作，您不应该经常为微秒任务创建线程，其次，通过程序参数的某种组合，线程可以引用哪个外部存储器，例如，在创建解决方案图片时-应该考虑并保护它。

如果任务很艰苦，并且我将拥有大量数据和多核计算机，那么我会走得更远-您可以创建几个恒定线程，每个线程都有自己的OneLineSolver对象，以及另一个控制工作分配和按需分配的线程安全结构它提供了对解决方案的下一行/列的引用。 解决了另一个问题之后的线程再次转向该结构以解决其他问题。 原则上，非图问题可以在不完成前一个问题的情况下开始，例如，当该结构参与所有单元的相互“与”运算时，一些流是自由的，什么也不做。 可以通过CUDA在GPU上完成更多的并行化-有很多选择。

• 使用经典数据结构。 请注意-当我显示颜色非图的解决方案的伪代码时，CanInsertColor和PlaceColor函数根本不起作用 $$$O（1）$ ，不像黑白非图。 在程序中看起来像这样：

 bool OneLineSolver::CanPlaceColor(const vector<int>& cells, int color, int lbound, int rbound) { // Went out of the border if (rbound >= cells.size()) { return false; } // We can paint a block of cells with a certain color if and only if it is // possible for all cells to have this color (that means, if every cell // from the block has color-th bit set to 1) int mask = 1 << color; for (int i = lbound; i <= rbound; ++i) { if (!(cells[i] & mask)) { return false; } } return true; } void OneLineSolver::SetPlaceColor(int color, int lbound, int rbound) { // Every cell from the block now can have this color for (int i = lbound; i <= rbound; ++i) { result_cells_[i] |= (1 << color); } } 

也就是说，它适用于生产线， $$$O（N）$ （稍后将解释这种代码的含义）。

让我们看看如何获​​得最佳的复杂性。 以CanPlaceColor 。 此函数检查段中向量的所有数字中的 $$$[lbound，rbound]$ 位数 $$$颜色$ 设置为1。等效于此，您可以 $$$和$ 该段的所有编号并检查位数 $$$颜色$ 。 使用事实，即操作 $$$和$ 可交换的 ，以及求和，最小值/最大值，乘积或运算 $$$Xor$ ，用于快速计数 $$$和$ , . :

1. SQRT-. $$$O(\sqrt{N})$ , $$$O(\sqrt{N})$ 。 .
2. . $$$O(N\log{N})$ , $$$O(\log{N})$ 。 .
3. (Sparse Table). $$$O(N\log{N})$ , $$$O(1)$ 。 .

, - ( $$$O(N)$ , $$$O(1)$ ) , , , $$$\varphi$ , $$$\varphi(\alpha, \beta) \in \{\alpha, \beta\}$ , — (, ...)

SetPlaceColor . . SQRT- ( " "). - .

- — .

, — , ? :

1. . $$$\log$ , , — ( magic number , ). , $$$N=10^{5}$ , $$$O(N^2)$ 10 , $$$O(N\log{N})$ 0.150 , $$$N$ , . , ( ): $$$O(N\sqrt{N})$ versus $$$O(N\log^2{N})$ 。 $$$N$ ( ) — 15-30.
2. , .

— , - — $$$N$ , . , ~25% ~11% , . - , , , .

— , . .

• . , , - . : , , "" ? , , ! . , .
• (, 1337 1000x1000) . std::bitset , — , .

, . "" . , C++ ( rope , ), hashtable , 3-6 / 4-10 /, unordered_map. , boost.

ROFL Omitting Format Language

, , , -.

ROFL — , "GNU's Not Unix". , , , , , . Omitting — (, , : — ).

, Matroska — 4 [52][4F][46][4C], , , , 3 , — , .

, MIT, — , .

GitHub . , , (, ). Magick++ args .

, ( ). nonograms.ru , , .

nonograms.ru .. KyberPrizrak , , , ! nonograms.ru, .

.