模式算法的复杂性

Question

我一直在尝试寻找一种算法来确定图案的复杂性，该坐标系位于图片的左侧，可能的线条位于图片的右侧：

我正在尝试寻找一种算法来确定图案的复杂性，该坐标系位于图片的左侧，可能的线条位于图片的右侧：在此处输入图片描述

构建模式的规则如下：

只能使用描绘的线条
一条线不能单独存在，这意味着它必须至少连接到另一条线。
当您将图案分成四个部分（左上、右上、左下和右下）时，必须至少有两个部分被线条覆盖，因此最少有两行。

好了，到目前为止，模式的定义还不是实际问题。问题是我想要三种难度级别的模式（简单、中等和困难）。以下是不同难度级别的不同模式的一些示例：

我一直在尝试找到一条包含内线（从中心向外展开的线）和外线（边缘线）的规则，但我无法想出一个好的算法来确定模式的复杂性.对我来说，行数肯定是一种可能性，但我对此并不满意，因为根据这条规则，简单和中等之间的区别不会像图片上看到的那样给出。我什至不知道它是否可以用算法来解决，我应该更好地硬编码吗？我对这个问题有点无能为力，非常感谢任何帮助。谢谢。

Answer 1

我暂时把它放在这里，还没有完成，我会继续努力，但是 Python 源代码可以提供帮助：

link_masks = [
  0xB0000, 0xCE000, 0x41800,
  0x28580, 0x15670, 0x02A0C,
  0x00142, 0x000AB, 0x00015
]

easy_patterns = [0xE0C25, 0xC1043, 0xE4F27, 0xF1957]
medium_patterns = [0xD0C67, 0x95E30, 0x95622, 0xC5463]
hard_patterns = [0xE5975, 0xB5E75, 0xF4C75, 0xF5D75]
patterns = [("easy", easy_patterns), ("medium", medium_patterns), ("hard", hard_patterns)]

def getPatternInfos(pattern):
  bs = [True if n == "1" else False for n in str(bin(pattern))[2::]]
  links = {}
  for link in range(len(link_masks)):
    bitwiseLink = str(bin(int(bin(link_masks[link])[2::], 2) & int(bin(pattern)[2::], 2)))[2::]
    links[link] = [True if n == "1" else False for n in bitwiseLink].count(True)
  lines = bs.count(True)
  return bs, links, lines

def checkPatternComplexity(pattern):
  bs, links, lines = getPatternInfos(pattern)
  linksAmount = sum(links.values())
  print("<Pattern>")
  print("Number of lines :", lines)
  printCube(bs)
  print(links)
  print(linksAmount, "links")
  print("Max links :", max(links.values()))
  print("</Pattern>")

def printIfTrue(condition, text = "■ "):
  if condition:
    print(text, end="")
  else:
    print(" "*len(text), end="")

def orOnList(cube, indexes):
  return (sum([cube[i] for i in indexes]) > 0)

def printCube(cube):
  for y in range(9):
    if y == 0: printIfTrue(orOnList(cube, [0, 2, 3]))
    if y == 4: printIfTrue(orOnList(cube, [2, 4, 9, 11, 12]))
    if y == 8: printIfTrue(orOnList(cube, [11, 13, 18]))
    if y in [0, 4, 8]:
      printIfTrue(cube[int((y / 4) + (y * 2))], "■ ■ ■ ")
      if y == 0: printIfTrue(orOnList(cube, [0, 1, 4, 5, 6]))
      if y == 4: printIfTrue(orOnList(cube, [3, 5, 7, 9, 10, 13, 14, 15]))
      if y == 8: printIfTrue(orOnList(cube, [12, 14, 16, 18, 19]))
      printIfTrue(cube[int((y / 4) + (y * 2)) + 1], "■ ■ ■ ")
    elif y in [1, 5]:
      for i in range(7):
        if i in [2, 5]:
          print(" ", end=" ")
        printIfTrue(cube[y * 2 + (1 - (y % 5)) + i])
    elif y in [2, 6]:
      for i in range(5):
        if i in [1, 2, 3, 4]:
          print(" ", end=" ")
        if i in [1, 3]:
          if i == 1 and y == 2:
            printIfTrue(orOnList(cube, [3, 4]))
          elif i == 3 and y == 2:
            printIfTrue(orOnList(cube, [6, 7]))
          if i == 1 and y == 6:
            printIfTrue(orOnList(cube, [12, 13]))
          elif i == 3 and y == 6:
            printIfTrue(orOnList(cube, [15, 16]))
        else:
          printIfTrue(cube[(y * 2 - (1 if y == 6 else 2)) + i + int(i / 4 * 2)])
    elif y in [3, 7]:
      for i in range(7):
        if i in [2, 5]:
          print("  ", end="")
        ri, swap = (y * 2 - 2) + (1 - (y % 5)) + i, [[3, 6, 12, 15], [4, 7, 13, 16]]
        if ri in swap[0]: ri = swap[1][swap[0].index(ri)]
        elif ri in swap[1]: ri = swap[0][swap[1].index(ri)]
        printIfTrue(cube[ri])
    if y == 0: printIfTrue(orOnList(cube, [1, 7, 8]))
    if y == 4: printIfTrue(orOnList(cube, [6, 8, 10, 16, 17]))
    if y == 8: printIfTrue(orOnList(cube, [15, 17, 19]))
    print()

for pattern_group in patterns:
  print("Current Real Complexity :", pattern_group[0])
  for pattern in pattern_group[1]:
    checkPatternComplexity(pattern)

这是生成的输出（例如，您可以在 http://repl.it 上进行测试）：

Current Real Complexity : easy
<Pattern>
Number of lines : 8
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■               ■ 
■               ■ 
■               ■ 
■ ■ ■ ■ ■       ■ 
        ■       ■ 
        ■       ■ 
        ■       ■ 
        ■ ■ ■ ■ ■ 
{0: 2, 1: 2, 2: 2, 3: 2, 4: 2, 5: 2, 6: 0, 7: 2, 8: 2}
16 links
Max links : 2
</Pattern>
<Pattern>
Number of lines : 6
■ ■ ■ ■ ■ ■ ■ ■ ■ 
              ■   
            ■     
          ■       
        ■         
      ■           
    ■             
  ■               
■ ■ ■ ■ ■ ■ ■ ■ ■ 
{0: 1, 1: 2, 2: 2, 3: 0, 4: 2, 5: 0, 6: 2, 7: 2, 8: 1}
12 links
Max links : 2
</Pattern>
<Pattern>
Number of lines : 12
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■       ■       ■ 
■       ■       ■ 
■       ■       ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■       ■       ■ 
■       ■       ■ 
■       ■       ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
{0: 2, 1: 3, 2: 2, 3: 3, 4: 4, 5: 3, 6: 2, 7: 3, 8: 2}
24 links
Max links : 4
</Pattern>
<Pattern>
Number of lines : 12
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■ ■           ■ ■ 
■   ■       ■   ■ 
■     ■   ■     ■ 
■       ■       ■ 
■     ■   ■     ■ 
■   ■       ■   ■ 
■ ■           ■ ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
{0: 3, 1: 2, 2: 3, 3: 2, 4: 4, 5: 2, 6: 3, 7: 2, 8: 3}
24 links
Max links : 4
</Pattern>
Current Real Complexity : medium
<Pattern>
Number of lines : 10
■ ■ ■ ■ ■ ■ ■ ■ ■ 
  ■             ■ 
    ■           ■ 
      ■         ■ 
■ ■ ■ ■ ■       ■ 
      ■ ■       ■ 
    ■   ■       ■ 
  ■     ■       ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
{0: 2, 1: 2, 2: 2, 3: 1, 4: 4, 5: 2, 6: 2, 7: 3, 8: 2}
20 links
Max links : 4
</Pattern>
<Pattern>
Number of lines : 9
■ ■ ■ ■ ■       ■ 
  ■     ■     ■ ■ 
    ■   ■   ■   ■ 
      ■ ■ ■     ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
        ■ ■       
        ■   ■     
        ■     ■   
        ■       ■ 
{0: 2, 1: 2, 2: 2, 3: 1, 4: 7, 5: 2, 6: 0, 7: 1, 8: 1}
18 links
Max links : 7
</Pattern>
<Pattern>
Number of lines : 8
■ ■ ■ ■ ■       ■ 
  ■     ■     ■   
    ■   ■   ■     
      ■ ■ ■       
■ ■ ■ ■ ■ ■ ■ ■ ■ 
        ■         
        ■         
        ■         
■ ■ ■ ■ ■         
{0: 2, 1: 2, 2: 1, 3: 1, 4: 6, 5: 1, 6: 1, 7: 2, 8: 0}
16 links
Max links : 6
</Pattern>
<Pattern>
Number of lines : 9
■ ■ ■ ■ ■ ■ ■ ■ ■ 
        ■     ■   
        ■   ■     
        ■ ■       
■ ■ ■ ■ ■         
      ■ ■         
    ■   ■         
  ■     ■         
■ ■ ■ ■ ■ ■ ■ ■ ■ 
{0: 1, 1: 3, 2: 2, 3: 1, 4: 5, 5: 0, 6: 2, 7: 3, 8: 1}
18 links
Max links : 5
</Pattern>
Current Real Complexity : hard
<Pattern>
Number of lines : 12
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■       ■     ■ ■ 
■       ■   ■   ■ 
■       ■ ■     ■ 
■       ■       ■ 
■     ■ ■ ■     ■ 
■   ■   ■   ■   ■ 
■ ■     ■     ■ ■ 
■       ■ ■ ■ ■ ■ 
{0: 2, 1: 3, 2: 3, 3: 2, 4: 5, 5: 2, 6: 2, 7: 2, 8: 3}
24 links
Max links : 5
</Pattern>
<Pattern>
Number of lines : 13
■ ■ ■ ■ ■       ■ 
■ ■     ■     ■ ■ 
■   ■   ■   ■   ■ 
■     ■ ■ ■     ■ 
■ ■ ■ ■ ■ ■ ■ ■ ■ 
      ■ ■ ■     ■ 
    ■   ■   ■   ■ 
  ■     ■     ■ ■ 
■       ■ ■ ■ ■ ■ 
{0: 3, 1: 2, 2: 2, 3: 2, 4: 8, 5: 3, 6: 1, 7: 2, 8: 3}
26 links
Max links : 8
</Pattern>
<Pattern>
Number of lines : 12
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■ ■     ■       ■ 
■   ■   ■       ■ 
■     ■ ■       ■ 
■ ■ ■ ■ ■       ■ 
      ■ ■ ■     ■ 
    ■   ■   ■   ■ 
  ■     ■     ■ ■ 
■       ■ ■ ■ ■ ■ 
{0: 3, 1: 3, 2: 2, 3: 2, 4: 6, 5: 2, 6: 1, 7: 2, 8: 3}
24 links
Max links : 6
</Pattern>
<Pattern>
Number of lines : 14
■ ■ ■ ■ ■ ■ ■ ■ ■ 
■ ■     ■     ■ ■ 
■   ■   ■   ■   ■ 
■     ■ ■ ■     ■ 
■ ■ ■ ■ ■       ■ 
■     ■ ■ ■     ■ 
■   ■   ■   ■   ■ 
■ ■     ■     ■ ■ 
■       ■ ■ ■ ■ ■ 
{0: 3, 1: 3, 2: 3, 3: 3, 4: 7, 5: 2, 6: 2, 7: 2, 8: 3}
28 links
Max links : 7
</Pattern>

links_masks 包含每个点的可能 link。

您可以编辑 checkPatternComplexity 函数来评估当前模式的复杂性，您可以访问线的数量、每个点的联络数量和所有联络（以位编码）。

以下是每个联络人的位掩码：

X : 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20


1 : 1  0  1  1  0  0  0  0  0   0   0   0   0   0   0   0   0   0   0   0
2 : 1  1  0  0  1  1  1  0  0   0   0   0   0   0   0   0   0   0   0   0
3 : 0  1  0  0  0  0  0  1  1   0   0   0   0   0   0   0   0   0   0   0
4 : 0  0  1  0  1  0  0  0  0   1   0   1   1   0   0   0   0   0   0   0
5 : 0  0  0  1  0  1  0  1  0   1   1   0   0   1   1   1   0   0   0   0
6 : 0  0  0  0  0  0  1  0  1   0   1   0   0   0   0   0   1   1   0   0
7 : 0  0  0  0  0  0  0  0  0   0   0   1   0   1   0   0   0   0   1   0
8 : 0  0  0  0  0  0  0  0  0   0   0   0   1   0   1   0   1   0   1   1
9 : 0  0  0  0  0  0  0  0  0   0   0   0   0   0   0   1   0   1   0   1

我也把编码的第一个12个形状放在这里：

X :  1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20

1 :  1  1  1  0  0  0  0  0  1   1   0   0   0   0   1   0   0   1   0   1
2 :  1  1  0  0  0  0  0  1  0   0   0   0   0   1   0   0   0   0   1   1
3 :  1  1  1  0  0  1  0  0  1   1   1   1   0   0   1   0   0   1   1   1
4 :  1  1  1  1  0  0  1  0  1   0   0   1   0   1   0   1   0   1   1   1
5 :  1  1  0  1  0  0  0  0  1   1   0   0   0   1   1   0   0   1   1   1
6 :  1  0  0  1  0  1  0  1  1   1   1   0   0   0   1   1   0   1   0   0
7 :  1  0  0  1  0  1  0  1  0   1   1   0   0   0   1   0   0   0   1   0
8 :  1  1  0  0  0  1  0  1  0   1   0   0   0   1   1   0   0   0   1   1
9 :  1  1  1  0  0  1  0  1  1   0   0   1   0   1   1   1   0   1   0   1
10 : 1  0  1  1  0  1  0  1  1   1   1   0   0   1   1   1   0   1   0   1
11 : 1  1  1  1  0  1  0  0  1   1   0   0   0   1   1   1   0   1   0   1
12 : 1  1  1  1  0  1  0  1  1   1   0   1   0   1   1   1   0   1   0   1

这是我对点 / links 进行编码的方式：

如果 link 存在，则为 1，否则为 0。

Answer 2

以下是关于可用于模式复杂性的标准的一些想法：

行数
单点连接的线数最大值
使用的对角线数
"subparts"的数量（三角形、正方形等的数量，但是编码有点困难）
至少一条线覆盖的点数

至少这是我在查看您的示例时得出的结论。（难易模式之间的惊人差异）

模式算法的复杂性

Complexity of a pattern algorithm

algorithm

graph-algorithm