1
$\begingroup$

This is my first question in this forum. I hope you will help me.

I was asked by a colleague to solve this puzzle. The puzzle goes like this:

I have an m x n grid where each cell can be in either of two states: on or off.

Initially the cells are in off state. I would like to have an algorithm that takes an integer input, l, and the grid, and gives me all the possible grid patterns where each pattern must have at least one off-block, where an off-block is a block of l contiguous cells all in off state.

Constraints:

  1. There should not be a cell in an off state either before or after an off-block.
  2. The off-block can be found not only in the vertical and horizontal orientation but also in the diagonal orientation.

The values of m and n can be as large as 32 and l is typically between 3 and 10 and it cannot be greater than either m or n.

Examples

Let's assume we have a 4 x 4 grid, let l be 3, 0 denote the off state and 1 denote the on state.

Some valid patterns

|---|---|---|---| | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | | 1 | 1 | 0 | 0 | |---|---|---|---| has 3 off-blocks

|---|---|---|---| | 1 | 0 | 1 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 0 | |---|---|---|---| has 1 off-block

Some invalid patterns

|---|---|---|---| | 0 | 0 | 1 | 0 | | 0 | 0 | 0 | 1 | | 0 | 0 | 0 | 1 | | 1 | 1 | 0 | 0 | |---|---|---|---| The main diagonal contains 4 (more than 3) contiguous cells in off state.

|---|---|---|---| | 1 | 0 | 1 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 0 | 1 | |---|---|---|---| Must contain at least one off-block

My approaches

These are what I have come up so far:

First approach: Brute force

My first approach was to list all the possible grid patterns and check each one of them if it satisfies the constraints. I immediately realized that this is not scalable. For instance, for a 4 x 4 grid I will have 2^16 possible grid patterns.

Second approach: After each off-block, turn on the next cell. This procedure is repeated both in the horizontal and the vertical orientations.

Take for instance a 6 x 6 grid, let l be 3.

Initially, this is the 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 | 0 | 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 | 0 | 0 | |---|---|---|---|---|---|

Starting from the first row, turn on the the cell after each off-block along the horizontal orientation of each row and we get the following pattern:

|---|---|---|---|---|---| | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | |---|---|---|---|---|---|

Starting from the first column of the above grid, turn on the the cell after each off-block along the vertical orientation of each column and we get the following pattern:

|---|---|---|---|---|---| | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | | 1 | 1 | 1 | 1 | 1 | 1 | | 0 | 0 | 0 | 1 | 0 | 0 | | 0 | 0 | 0 | 1 | 0 | 0 | |---|---|---|---|---|---|

With this approach I can satisfy the first constraint. In order to get the other patterns I need to turn on the remaining off cells. The only option that I see is to adapt a brute force to deal with the remaining cells.

Moreover, turning a cell on may permit turning a neighbouring cell off, resulting in a valid new pattern. For example from the following pattern where l is 2

|---|---|---|---| | 0 | 0 | 1 | 0 | | 0 | 0 | 1 | 0 | | 1 | 1 | 1 | 1 | | 0 | 0 | 1 | 0 | |---|---|---|---|

we can get the pattern below by turning on the cell at coordinate(1,1) and turning off the cell at coordinate(2,2)

|---|---|---|---| | 0 | 0 | 1 | 0 | | 0 | 1 | 1 | 0 | | 1 | 1 | 0 | 1 | | 0 | 0 | 1 | 0 | |---|---|---|---|

Therefore, even with the second approach I cannot gaurantee to produce all the possible patterns.

I hope the above the description is self-contained to understand the problem.

Thank you

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! What's the context where you ran across this problem? I encourage you to cite the source of the problem. Also, what approaches have you considered? What did you try, and where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 15 '17 at 20:04
  • $\begingroup$ When you say "number of contiguous cells", do you mean "number of contiguous cells that are on"? Finally... do you want to output a list of all such patterns? Or just output a count of the number of such patterns? Also, how large will typical values of n,m,l be? Can you edit your question to address this feedback? $\endgroup$ – D.W. Mar 15 '17 at 20:06
  • $\begingroup$ @D.W. I meant at most l contiguous off cells. Yes I want the list of patterns as the output. Typically, the values of n and m can be upto 32, but I could also have a larger grid. $\endgroup$ – Haileyesus Mar 15 '17 at 20:11
  • $\begingroup$ A straightforward recursive procedure would do the trick very efficiently. $\endgroup$ – Yuval Filmus Mar 15 '17 at 20:24
  • $\begingroup$ How large will typical values of l be? What's the source where you saw this problem? Please edit the question to incorporate all information into the question. We want questions to be self-contained, so people don't have to read the comments to understand what you are asking. $\endgroup$ – D.W. Mar 15 '17 at 20:26
1
$\begingroup$

You want the set of grids that contains at least one contiguous off-block.

There is a simple iterative algorithm for this. Enumerate the set of all locations and all orientations for the off-block. For each such, fill in the grid with that off-block, and fill in the two squares on either end of the off-block per your first constraint; then the rest of the squares can be filled in arbitrarily, so enumerate all possibilities for them.

There will be exponentially many such filled-in grids, so this procedure will be computationally infeasible for all but the smallest grids. Moreover, every procedure that correctly solves this problem will be computationally infeasible: the output (list of valid solutions) is exponentially long, so it will take exponentially long just to construct that output. No amount of cleverness or algorithmic tricks will let you avoid this. It is an inherent consequence of the problem statement. The problem is simply not solvable (within any reasonable amount of time), except for small grids.

$\endgroup$
  • $\begingroup$ Initially, this is what I had in mind but, as you have noticed, this is not computationally feasible. I have implemented the solution suggested by @Yuval Filmus but running the program gave me a grid with all the cells set to on except the bottom right corner. $\endgroup$ – Haileyesus Mar 16 '17 at 20:52
  • $\begingroup$ @Haileyesus, I edited my answer. See the last paragraph. $\endgroup$ – D.W. Mar 16 '17 at 20:55
  • $\begingroup$ Thank you for the clarification. You are right, since there are exponential many possible patterns, print each of them by itself is infeasible. $\endgroup$ – Haileyesus Mar 16 '17 at 20:57
  • $\begingroup$ @Haileyesus I'm afraid you haven't implemented my algorithm properly. My implementation produces many answers. $\endgroup$ – Yuval Filmus Mar 16 '17 at 22:14
  • 1
    $\begingroup$ @D.W. If I understand the OP's constraints correctly, then they disallow long off-blocks. It's not enough that one off-block has just the correct length, since there could be other off-blocks. Also, your algorithm enumerates some solutions more than once. $\endgroup$ – Yuval Filmus Mar 16 '17 at 22:18
0
$\begingroup$

For an off-on matrix $M$, let $\ell(M)$ be the maximum contiguous run (horizontally, vertically, or diagonally, in both diagonal orientations) of off cells. You seem to be asking for the list of all $n\times m$ off-on matrices $M$ with $\ell(M) = \ell$.

One way to generate this list is using the following recursive procedure, which gets as input a partially filled off-on matrix $M$:

  • If $M$ is complete filled, output it if $\ell(M) = \ell$.
  • Otherwise, locate the first unfilled cell in $M$, set it on, and run the procedure recursively.
  • Set the same cell to off, and check whether this introduces a contiguous run of off cells of length $\ell+1$. If it doesn't, run the procedure recursively.

Implementing the second step requires an ordering of the cells in the matrix. One possibility is to order the cells top to bottom and left to right.

You run the entire procedure with the empty matrix as input, and then it prints all legal matrices.

In practice I expect this procedure to be quite efficient, since (1) it seems that most of the time a choice which doesn't lead to an immediate run corresponds to a partially filled matrix which can be completed to a legal completely filled matrix, and (2) it seems that most matrices with $\ell(M) \leq \ell$ actually satisfy $\ell(M) = \ell$.

You can test this empirically by comparing the number of generated matrices to the number of recursive calls (divided by $nm$).

$\endgroup$
  • $\begingroup$ I have few doubts. What do you mean by 'completely filled' matrix? Is it a matrix with all 0s or all 1s or a matrix that satisfies the constraints? $\endgroup$ – Haileyesus Mar 16 '17 at 18:02
  • $\begingroup$ A matrix with all offs and ons. $\endgroup$ – Yuval Filmus Mar 16 '17 at 18:02
  • $\begingroup$ If l < min(m, n), then a complete matrix in the first step will never satisfy the condition "L(M) == l"; hence, no output to print. Moreover, the next steps will make the matrix always incomplete. $\endgroup$ – Haileyesus Mar 16 '17 at 18:12
  • $\begingroup$ I'm not sure what you mean. You can program this algorithm and see that it works. I forgot to mention that you have to start it with the empty matrix. $\endgroup$ – Yuval Filmus Mar 16 '17 at 18:14
  • $\begingroup$ Yes, that's basically it, up to some simple optimization. $\endgroup$ – Yuval Filmus Mar 16 '17 at 18:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.