Determine if all the elements of a matrix are connected in Python

Question

Note: Do not mention Numpy for matrix creation, as I cannot use that specific library.

I've been working on a Python program that checks if all the elements inside a board (the board size can change) are connected. For example, this board's elements are all connected:

board = [
    [1, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
]

However, the current program I have is faulty, as some specific cases return the opposite Boolean value. What should I be doing instead?

This is the current code I have:

#Should return False, returns False
board1 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 0, 1]
    ]

#Should return True, returns False
board2 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 1, 0]
    ]

#Should return True, returns True
board3 = [
    [0, 1, 0],
    [1, 1, 1],
    [0, 1, 0]
    ]

#Should return True, returns False
board4 = [
    [0, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
    ]
def check(board):
    adjacent_total = []

    for x in range(len(board)):
        for y in range(len(board[0])):
            adjacent = []

            if board[x][y] == 1:

                for i in range (x-1, x+2):
                    for j in range (y-1, y+2):
                        if i == x and j == y:
                            continue
                        if i == len(board) or j == len(board[0]):
                            break

                        if i >= 0 and j >= 0:
                            if board[i][j] == 1:
                                adjacent.append((i,j))

            else:
                adjacent = None
            adjacent_total.append(adjacent)

    for i in adjacent_total:

        if i is None:
            continue
        elif len(i) == 1:
            return False
    return True

print(check(board1))
print(check(board2))
print(check(board3))
print(check(board4))

Answer 1

What about:

import itertools
#Should return False, returns False
board1 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 0, 1]
]

#Should return True, returns False
board2 = [
    [1, 0, 1],
    [1, 0, 1],
    [0, 1, 0]
]

#Should return True, returns True
board3 = [
    [1, 0, 1],
    [1, 1, 1],
    [0, 1, 0]
]

#Should return True, returns False
board4 = [
    [1, 0, 0, 1],
    [0, 1, 1, 0],
    [0, 0, 1, 0],
    [0, 1, 0, 0],
]

class Matrix(object):
    def __init__(self, m):
        self.m = m

    @property
    def numrows(self): return len(self.m)

    @property
    def numcols(self): return len(self.m[0])

    def get(self, r, c):
        return self.m[r][c]

    def set(self, r, c, v):
        self.m[r][c] = v

    def is_valid(self, r, c):
        return (0 <= r < self.numrows) and (0 <= c < self.numcols)

    def neighbors(self, r, c):
        #offsets =
        #    (0,1), (0,-1), (1,0), (-1,0),
        #    (-1,-1), (-1,1), (1,-1), (1,1),
        #]
        offsets = itertools.product([-1,0,1],[-1,0,1])
        neighbors = []
        for (dr,dc) in offsets:
            if (dr,dc) == (0,0): continue
            rr = r + dr
            cc = c + dc
            if self.is_valid(rr, cc): neighbors.append((rr,cc))
        return neighbors

    def find_nonzero(self):
        for (r,c) in self.iter():
            if self.get(r,c) == 1: return (r,c)
        return None

    def iter(self):
        return itertools.product(xrange(self.numrows), xrange(self.numcols))

    def show(self):
        for row in self.m: print(row)


def grow(m, r, c):
    m.set(r, c, 0)
    for (rr,cc) in m.neighbors(r, c):
        if m.get(rr,cc): grow(m, rr, cc)


def check(board):
    m = Matrix(board)

    # Find any non-zero element
    (r,c) = m.find_nonzero()
    print("Found non-zero element at ({},{})".format(r,c))

    # Call grow, a recursive function that "unsets" the neighbors of (r,c) and recurses
    grow(m, r, c)

    m.show()

    # Check if any are still set
    return (m.find_nonzero() is None)    

Usage:

for i,board in enumerate([board1, board2, board3, board4]):
    print("Checking board %d:" % (i+1))
    res = check(board)
    print(res)
    print('---')

Output (with resulting boards from m.show() removed):

Checking board 1:
Found non-zero element at (0,0)
False
---
Checking board 2:
Found non-zero element at (0,0)
True
---
Checking board 3:
Found non-zero element at (0,0)
True
---
Checking board 4:
Found non-zero element at (0,0)
True
---

I create a Matrix class that abstracts a lot of the work. From there, I create a grow function that accepts a Matrix and a (row, column) index. The grow function "unsets" the value at (row, col) and recurses on all the set neighbors.

The result is a matrix where all "connected" elements from the first non-zero element are set to zero.

Then, if the matrix has any non-zero elements left, they weren't connected, and check returns False.