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 평방 작동합니다. 그 그리드 [행] [열] == 말,

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

그러나 그것은 작동하지 않습니다 : "빛"이 아닌 구를 검색하기위한 하나의 기능을 가지고 싶은, I`ve는 다음과 같이 작성 시도 1은 이며 범위는입니다.

그래서, 문제는 다음과 같습니다

1. 내가 자동으로 3 * 3
2. 내가 모르는 모든 작은 사각형을 볼 수있는 카운터 작업 쓸 수의 모든 조합을 작성하는 방법 " 등".

아무 생각이 있으시면 알려주세요. 또 다른 해결책이 될 수 있다고 생각한다면 제발, 또한 말하십시오. 미리 감사드립니다.

Answer 1

문제는 프로그래밍에 대해 뭔가를 배우는이었다.최대한 멀리 볼 수있는, 간단한 철수-메커니즘이 사용되어야한다 :

# 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 

:

import numpy as np 

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

첫째, 우리는 글로벌 그리드 가 정상적으로 것들로 가득 경우 True을 반환하는 간단한 검사 기능을 필요

그리고 여기에서는 main 메소드를 사용합니다. 아이디어는 다음과 같습니다 : 모든 그리드 엔트리는 0에서 24 사이의 유일한 식별자 인 "idx"를가집니다. 목표는 올바른 구성 을 찾는 것입니다. 여기서 여섯 개의 요소는 24 개의 그리드 항목 (25 - 중간 항목) 위에 올바르게 펼쳐집니다. 모든 가능한 binom(24, 6)=134596 솔루션은 check-method가 처음으로 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 (모든 표시등이 켜짐)의 "2 진"숫자로 나타냅니다. 그런 다음, 그리드는 그러한 수의 5- 튜플이 될 것입니다. 32^5 = 33554432 격자가 있습니다. 효율적으로 수행되면 수분 내에 무차별 대입이 가능합니다.

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

:

가 행 r 칼럼 c 시작 3 × 광장 등의 수 (비트)을 확인하기 위해 사용하는 비트 시프트 및 마스크 (단 r 및 c하는 0과 2 사이이다) 여기서 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 솔루션과 마찬가지로 너무 아름답고 짧지는 않지만 가능한 변형입니다. 내 컴퓨터에서 그것은 약 5 분 작동합니다.