I'm very sorry I'm asking this question, but my coding skills are not so great, so I can not solve this problem: there is a grid 5*5, and a task is to find minimal number of "lights", or "1" settled in a special way: in every 3*3 square of the big square, there must be exactly 4 "lights". Counting with a pen, I've got this minimal number equals 7 (the answer is right). So my solution looks like this:
#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))
As expected, counter() works only for the first little 3*3 square. Wanting to have only one function for searching "lights" and not 9, I`ve tried to write something like this:
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))
But it doesn't work, saying that grid[row][column] == 1 is out of range.
So, the problem is:
Please, if you have ANY idea, tell me. If you think there can be another solution, please, say also. Thanks in advance.
The question was about learning something about programming. As far as I can see, a simple backtrack-mechanism should be used:
import numpy as np
#initialize the grid with the middle set to one
grid = np.zeros((5,5))
grid[2,2] = 1
First, we need a simple check function, that returns True if the global grid is
gracefully filled with ones:
# 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
And here we go with the main method. The idea is the following: Every grid entry has a
unique identifier between zero and 24, its "idx". The aim is to find a valid configuration
where the six ones are spread correctly over the 24 grid entries (25 - middle entry).
All possible binom(24, 6)=134596 solutions are enumerated through a simple loop and a recursive call to place the remaining entries, until the check-method returns True the first time, i.e. when a valid configuration is found.
# 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
A call to
recursive_trial(0, 0, 6)
print grid
yields (in a matter of milliseconds)
[[ 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.]]