python - 5*5的格子，在每3*3的格子里必须有4个 "lights"

Question

很抱歉我问这个问题，但我的编码能力不是很好，所以我无法解决这个问题:有一个网格 5*5，还有一个任务就是寻找最小数量的“灯”，或者说“1”，用一种特殊的方式解决:在大方格的每3*3格中，必有恰好 4 个“灯”。用笔数，我得到的最小数字等于 7(答案是正确的)。所以我的解决方案是这样的:

#creates a list
grid = []

#creates lines
for row in range(5):
    grid.append([])
    #creates columns
    for column in range(5):
        grid[row].append(0)

#one "light" must be in a center
grid[2][2] = 1

#this array counts all "lights" and will notice when there are 4 of them
light_number = []

def counter():
for row in range(0, 3):
    for column in range(0, 3):
        if grid[row][column] == 1:
           light_number.append(1)
print(len(light_number))

正如预期的那样，counter() 仅适用于第一个 3*3 的小方 block 。想要只有一个函数来搜索“灯”而不是 9 个，我试着写这样的东西:

def counter():

#initial range of the counter
row_min = 0
row_max = 3
column_min = 0
column_max = 3

for i in range(9):
    for row in range(row_min, row_max):
        for column in range(column_min, column_max):
            if grid[row][column] == 1:
                #write it in a list
                light_number.append(1)
            column_min += 1
            column_max += 1
        row_min += 1
        row_max += 1
    #print a number of total lights
    print(len(light_number))

但是不行，说grid[row][column] == 1 out of range。

所以，问题是:

1. 我不会写工作计数器，它应该自动看到所有小方 block 3*3
2. 我不知道，如何写“灯”的所有组合。

请，如果您有任何想法，请告诉我。如果您认为可以有另一种解决方案，请也说。提前致谢。

Answer 1

在有人想出更智能的算法之前，我可以为您提供一个暴力解决方案来枚举所有网格。

将网格的每一行表示为从 0(一行中的所有灯都关闭)到 31(所有灯都打开)的“二进制”数字。然后，网格将是此类数字的 5 元组。有 32^5 = 33554432 个网格 - 如果有效地完成，可以在几分钟内暴力破解。

检查从 r 行和 c 列(其中 r 和 c 介于 0 和 2 之间)，使用位移和掩码:

s = (nbits[7 & (g[r + 0] >> (2 - c))]
    +nbits[7 & (g[r + 1] >> (2 - c))]
    +nbits[7 & (g[r + 2] >> (2 - c))])

其中 g 是一个网格，nbits 包含从 0 到 7 的每个数字的位数。如果某些 s != 4 ，网格无效，继续下一个。

综合起来:

import itertools

        # 0 1 2 3 4 5 6 7
nbits = [ 0,1,1,2,1,2,2,3 ]

def check(g):
    for r in range(3):
        for c in range(3):
            s = (nbits[7 & (g[r + 0] >> (2 - c))]
                +nbits[7 & (g[r + 1] >> (2 - c))]
                +nbits[7 & (g[r + 2] >> (2 - c))])
            if s != 4:
                return False
    return True

for g in itertools.product(range(32), repeat=5):
    if check(g):
        print g
        for row in g:
            print '{:05b}'.format(row)
        print