5 * 5格，每格3 * 3格的格必须是4格“灯”

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平方米。希望只有一个功能搜索“灯”，而不是9，I`ve试着写是这样的：

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)) 

但它不工作，他说，格[行] [列] == 1是超出范围。

所以，问题是：

1. 我不会写工作计数器，它应该会自动显示所有的小广场3 * 3
2. 我不知道怎么写的所有组合“灯”。

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

Answer 1

的问题是关于学习的东西有关编程。据我所看到的，应该用一个简单的回溯机制：

import numpy as np 

#initialize the grid with the middle set to one 
grid = np.zeros((5,5)) 
grid[2,2] = 1 

首先，我们需要一个简单的检查功能，即返回True如果全球网格 优雅充满的：

# a method to check all sub squares starting at row and column 0 through 2 
def checkgrid(): 
    # row 0 through 2 
    for r in xrange(3): 
     # column 0 through 2 
     for c in xrange(3): 
      # sum up all entries of grid matrix 
      if grid[r:r+3, c:c+3].sum() != 4: 
       return False 
    return True 

在这里，我们走的主要方法。这个想法如下：每个网格条目都有一个 唯一的标识符，它的“idx”在0到24之间。目标是找到一个有效的配置 其中六个在24个网格条目（25-中间条目）上正确传播。 所有可能的binom(24, 6)=134596解决方案都通过一个简单的循环和递归调用来枚举其余条目，直到检查方法第一次返回True，即找到有效配置时。

# method that is recursively applied to set the next one 
def recursive_trial(first, depth, maxdepth): 
    # all ones are placed: check the grid 
    if depth == maxdepth: 
     return checkgrid() 
    # enumerate possible grid positions as idx == 5 * r + c 
    for idx in xrange(first, 25 - (maxdepth - depth + 1)): 
     # get row and column idx 
     r = idx/5 
     c = idx % 5 
     # skip the middle 
     if grid[r,c] == 1: 
      continue 
     # set entry to one 
     grid[r,c] = 1 
     # call method recursively to place missing ones until 7 in the remainder of the array 
     if recursive_trial(idx + 1, depth + 1, maxdepth): 
      return True 
     # set entry back to zero 
     grid[r,c] = 0 
    # at this point, we failed with the current configuration. 
    return False 

的调用

recursive_trial(0, 0, 6) 
print grid 

收益率（以毫秒为单位的事）

[[ 0. 0. 1. 0. 0.] 
[ 0. 0. 0. 0. 0.] 
[ 1. 1. 1. 1. 1.] 
[ 0. 0. 1. 0. 0.] 
[ 0. 0. 0. 0. 0.]] 

Answer 2

这是我将如何解决这个问题：

grid = [[0,0,0,0,0],[0,0,0,0,0],[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,0]] 
grid33total = [[0,0,0],[0,0,0],[0,0,0]] 
for i in range(3): 
    for j in range(3): 
     grid33total[i][j] = sum(sum(x[0+i:3+i]) for x in grid[0+j:3+j]) 
total = sum(sum(x) for x in grid33total) 

阵列grid33total包含的“灯”用于每个3×3的正方形的数目。

Answer 3

直到有人想出了一个更聪明的算法，我可以为您提供蛮力解决方案来枚举所有网格。

将网格的每一行表示为从0（一排中所有灯都熄灭）到31（所有灯都点亮）的“二进制”数字。然后，一个网格将是这种数字的五元组。有32^5 = 33554432个网格 - 如果高效完成的话，可以在几分钟内暴力破解。

为了在开始于行r和列c一个3x3正方形检查多个光源（比特）（其中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 

Answer 4

所以，幸运的是努力和帮助下，我已经有一个解决方案上来。

import itertools 
from pprint import pprint 
import sys 


def check(grid): 
    count = 0 
    for row in range(3): 
     for column in range(3): 
      s = 0 
      for right in range(3): 
       for down in range(3): 
        if grid[row+right][column+down] == 1: 
         s += 1 
         if s == 4: 
          count += 1 
    if count != 9: 
     return False 
    else: 
     return True 


for n in range(4, 25): 
    for comb in itertools.combinations(range(25), n): 
     grid = [[0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0], 
       [0, 0, 0, 0, 0]] 
     for index in comb: 
      row = index // 5 
      column = index % 5 
      grid[row][column] = 1 
      if check(grid): 
       print(n) 
       pprint(grid) 
       sys.exit() 

我决定使用itertools.combinations。

row = index // 5 
column = index % 5 
grid[row][column] = 1 

是一个非常有趣的方式来确定是否必须有“1”或“0”。程序查看整数除法的结果（//），这将是一个行号，然后是残差（％），这将是一个列号。然后在这里放置“1”。

我知道，它不是如此美丽和短小，因为nbits解决方案，但它也是一个可能的变种。在我的电脑上，它的工作时间只有五分钟。