Minimum toggles of adjacent bits to turn grid to all 1s in polynomial time

Question

I came up with a programming problem that goes something like this:

suppose you have a NxN binary grid. “Tapping” a square toggles it and all edge-adjacent squares. Find the shortest sequence of “taps” that converts the grid to all 1s.

The easiest to see algorithm is a BFS, where we start at a grid of all 1s, and repeatedly visit each board that is one “tap” away from the current board, while making sure that we never visit a board twice. However, since there are 2^(n^2) board states, it’s a pretty inefficient algorithm.

I was able to find a polynomial time (O(n^2)) algorithm for N <= 3, but it breaks down for N>=4, since it relies on the fact that each board is solvable.

Is there a polynomial time algorithm for N>=4?

Thanks!

Edit: Here is an outline of my algorithm for n=3 (also applies for smaller N):

1. Tapping is an xor of the current board with a “plus” of 1s.
2. Tapping the same cell twice is the same as not tapping it at all, since an xor a = 0.
3. Tap order doesn’t matter, since xor is associative. Thus, we can represent a set of taps as a NxN grid, just like a board.

Let A->B denote tapping B onto board A Let 1 denote the NxN grid of all 1s.

Note that 1->(1->(1->(1->(A)))) = A for all boards A with N<=3. To my knowledge, there’s no intuitive proof of this; you just have to expand it out using xor and it eventually resolves.

Let B = 1->(1->(1->A)). By substitution, 1->B = A, so 1->B->B = A->B = 1, by (2) above, so we have found B as desired.

Since every board is reachable, and there are the same number of board states as tap sets, then B is unique, so it is optimal.

Answer 1

It should work with BFS. A propper BFS algorithm does not rely on the fact that there is a solution: when there is none, it just falls through its main loop without results.

Some observations:

• It is never necessary to tap the same cell more than once. If you tapped it twice, it is the same as not tapping it. It is a XOR operation.

• The order of the taps is not important. The effect of tapping the same cells in a different order is the same.

• You can improve a bit on BFS by implementing the A* search algorithm. For the realised cost you could count 5 per performed tap (to represent the maximum number of flipped cells), and for an admissible heuristic you could count the number of cells that are still 0. Note that an A* search uses a priority queue.

• Working with bit representations and using bit operations like AND, OR and XOR, may speed up an implementation, although it doesn't influence the time complexity.

• When you have a 0 cell in the matrix, it is certain that this cell or any of its edge-neighbors needs to be tapped. So it makes sense to select one (only) of the zeroes and consider the 5 taps (at most) as "next" moves.

Here is an implementation in Python with some comments to explain details:

# Import HeapQ as priority queue implementation
from heapq import heappush, heappop

# Define conversion functions between matrix and bitmap representations
def matrix_to_int(matrix):
    n = len(matrix)
    # Foresee an extra column:
    width = n + 1
    result = 0
    # board mask represents the bits that are not in the extra column
    boardmask = 0
    rowmask = (1 << n) - 1  # A mask with n times a 1-bit
    for row in matrix:
        # Add an extra bit after each row: a boundary
        result = result * 2
        boardmask = (boardmask << width) + rowmask
        for bit in row:
            # Store the opposite bit (0 <--> 1)
            result = result * 2 + (1-bit)
    return boardmask, result

def int_to_matrix(n, pattern):
    width = n + 1
    bit = (1 << (width * n - 2))
    matrix = []
    for _ in range(n):
        row = []
        for _ in range(n):
            row.append(int(pattern & bit > 0))
            bit >>= 1
        bit >>= 1  # Skip boundary bit
        matrix.append(row)
    return matrix
   
def solve(matrix):
    n = len(matrix)
    width = n + 1
    # Define a bit pattern of a cross shape (+), having 5 1-bits:
    crosspattern = 2 | (7 << width) | (2 << (width*2))
    # This cross has it center location at (1, 1) instead of (0, 0), 
    #   so define a shift
    crossshift = width + 1
    # Convert the input to a single integer (bit pattern) where 
    #      1 and 0 are swapped, so we now look to clear(!) this pattern
    boardmask, pattern = matrix_to_int(matrix)
    availabletaps = boardmask
    # The admissible heuristic is the number of 1 bits (that we want as 0)
    distance = pattern.bit_count()

    # Each heap entry will have 4 elements: 
    #   - estimated total cost
    #   - realised cost (by previous taps), 
    #   - the current state of the matrix (as a bit pattern)
    #   - the set of positions that can be tapped (as a bit pattern)
    heap = [(distance, 0, pattern, availabletaps)]
    while heap:
        allcost, pastcost, pattern, availabletaps = heappop(heap)
        if pattern == 0:  # solved!
            return int_to_matrix(n, availabletaps ^ boardmask)
        # Foresee the cost of the next tap:
        #    Use a cost of 5 to make sure the heuristic is admissible.
        pastcost += 5
        # Get the first 1 bit in the pattern
        firstbit = pattern & -pattern
        # Get the taps that will set this firstbit to 0
        for dir in -width, -1, 0, 1, width:
            tapbit = firstbit << dir if dir >= 0 else firstbit >> -dir
            if tapbit & availabletaps == 0:
                continue  # Cannot/shouldn't tap here
            # Tap at tapbit: move the cross pattern to this bit
            crossbits = (tapbit * crosspattern) >> crossshift 
            # ... and apply it to the board, discarding the bits outside it
            nextpattern = (pattern ^ crossbits) & boardmask
            # Heuristic for future cost: number of 1 bits in the pattern
            distance = nextpattern.bit_count()
            heappush(heap, (pastcost + distance, pastcost, 
                nextpattern, availabletaps - tapbit))

Here is an example run on a 10x10 matrix:

matrix = matrix = [
    [1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
    [1, 0, 0, 1, 1, 1, 0, 0, 1, 1],
    [0, 1, 0, 0, 1, 0, 1, 1, 0, 0],
    [0, 1, 1, 0, 0, 0, 1, 0, 1, 1],
    [1, 1, 1, 1, 0, 0, 1, 1, 0, 0],
    [1, 0, 0, 0, 1, 0, 1, 0, 1, 1],
    [0, 0, 0, 0, 0, 0, 1, 0, 0, 1],
    [1, 0, 1, 0, 1, 1, 1, 0, 1, 0],
    [1, 0, 0, 0, 1, 0, 0, 1, 1, 0],
    [0, 0, 0, 0, 1, 0, 1, 0, 0, 1]
]
taps = solve(matrix)

The taps matrix will represent the cells that need to be tapped (in any order):

[
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 1, 0, 0, 0], 
    [1, 0, 0, 1, 0, 1, 0, 0, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 1, 1], 
    [0, 0, 0, 0, 1, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 1, 0, 1, 0, 0], 
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 1, 0, 0, 0, 1], 
    [0, 1, 0, 0, 0, 0, 0, 0, 1, 0]
]

As the heuristic function is admissible, the returned solution is guaranteed to represent the minimum of taps needed.