众所周知，方位网格的排列可以使用蛮力算法计算，其中从0…((2^cells)-1)的整数循环可以使用位掩码转换为每个网格排列。几个例子:
Grid size 2 (4 cells): 0-->15
Grid size 3 (9 cells): 0-->511
这对于一定大小的网格很有效，但对于大小为7或更大的网格，循环操作的绝对数量将达到数万亿。
还有什么其他选择?
我已经有了6号网格的工作代码，但是一个快速的费米估计有一个7号网格在我的工作站上大约76年，所有cpu最多…: - (
目标应用程序关于上述网格的实际应用，这与《Nurikabe》谜题非常相似，但我只对可以在X或Y轴上镜像的网格感兴趣。所以一些合适的图案可能是菱形(X &Y)，字母D (Y)或字母A (X)。
现有效率由于目标应用程序的变幻莫测，有许多候选对象可以被丢弃:
- 那些不在网格边缘创建单元格的
- 不能在X轴或Y轴上镜像的
- 分离细胞
样本输出(N=4)
Current value is : 28662
##
####
####
##
Current value is : 40953
# #
####
####
# #
Current value is : 63087
####
##
##
####
Current value is : 63903
####
# #
# #
####
Current value is : 65535
####
####
####
####
Grid size 4, done in 22 milliseconds
信息守恒规定不可能在0 (2^cells)以内生成所有数组模式-您必须至少考虑每种情况一次。
然而，你可以通过并行生成每个数组模式来优化它，通过使用打包位集和可能的SIMD。
有一种系统地生成位模式的技术称为最大长度序列。生成算法的关键特征是每个可能的位模式(对于一定数量的单元格)生成EXACTLY一次。它使用异或迭代计算连续值，可以使用SSE/MMX进行优化(达到合理的大小)。
链接:http://web.iitd.ac.in/~ saifkm/docs/EEL319/务实/expt3_319.pdf
有2^n位掩码，大小为n。你不可能希望以小于2^n的复杂度生成它们。您要么需要一个不生成所有位掩码的替代解决方案，要么无法改进此值。
如果您只对可以镜像的网格感兴趣，那么只需生成四分之一或一半的网格，并对其进行镜像。
For a 7x7:
X和Y镜像:生成所有可能的X和Y轴排列2^(7 + 7 - 1)乘以所有可能的3x3排列2^(3 * 3)。由于3x3将在4个角上镜像，因此只有2^13 * 2^9排列4,194,304生成。
X或Y镜像:生成1轴2^7的排列和3x7网格2^21的排列，总共268,435,456
For a 8x8:
X和Y镜像:所有的4x4排列2^16或65536.
X或Y镜像:所有4x8排列2^32 ~ 40亿(现代计算机应该能够在一分钟内完成此操作)。