Check for pattern recursively

*Note i refer to thing as a matrix but it is not, it is just a collection of 1's and zeros

Suppose you have a matrix that is always square (n x n). Is it possible to determine if there exists a single column/row/diagonal such that each item is a 1.

Take the matrix below for instance (True):

1 0 0

1 1 0

0 0 1

Another example (True):

1 1 1

0 0 0

0 1 0

And finally one without a solution (False):

0 1 1

1 0 0

0 0 0

Notice how there is a diagonal filled with 1's. The rule is there is either there is a solution or there is no solution. There can be any number of 1's or zeros within the matrix. All i really need to do is, if you have (n x n) then there should be a row/column/diagonal with n elements the same.

If this is not possible with recursions, please let me know what is the best and most efficient method. Thanks a lot, i have been stuck on this for hours so any help is appreciated (if you could post samples that would be great).

EDIT

This is one solution that i came up with but it gets really complex after a while.

Take the first example i gave and string all the rows together so you get:

1 0 0, 1 1 0, 0 0 1

Then add zeros between the rows to get:

1 0 0 0, 1 1 0 0, 0 0 1 0

Now if you look closely, y开发者_C百科ou will see that the distances between the 1's that form a solution are equal. I dont know how this can be implemented though.

In search for an elegant solution I came up with this:

class LineOfOnesChecker(object):

    _DIAG_INDICES = (lambda i: i, lambda i: -i - 1)

    def __init__(self, matrix):
        self._matrix = matrix
        self._len_range = range(len(self._matrix))

    def has_any(self):
        return self.has_row() or self.has_col() or self.has_diag()

    def has_row(self):
        return any(all(elem == 1 for elem in row)
                   for row in self._matrix)

    def has_col(self):
        return any(all(self._matrix[i][j] == 1 for i in self._len_range)
                   for j in self._len_range)

    def has_diag(self):
        return any(all(self._matrix[transf(i)][i] == 1 for i in self._len_range)
                   for transf in self._DIAG_INDICES)

Usage:

print LineOfOnesChecker(matrix).has_any()

You can have a list of n 1's and do an 'AND' for your sets of diagonal elements, row elements and column elements and if any of those AND operation results in a TRUE, then you have your valid pattern.

import sys
matrix = [[1,0,1],[1,0,1],[1,0,1]]
transpose = zip(*matrix)
diagonal1 =  []
for n,elem in enumerate(matrix):
    diagonal1.append(elem[n])
diagonal2 = []
for n,elem in enumerate(transpose):
    diagonal2.append(elem[n])
for row in matrix:
    if reduce(lambda x,y: x and y, row):
        print True
        sys.exit()
for row in transpose:
    if reduce(lambda x,y: x and y, row):
        print True
        sys.exit()
if (reduce(lambda x,y: x and y, diagonal1) or reduce(lambda x, y: x and y, diagonal2)):
    print True
    sys.exit()

From what I understand of the problem, you just need to check whether any row, coloumn or diagonal consists entirely of '1's. This can be done very easily using all in Python, so I don't get why you want to do this recursively.

The more obvious solution (in my mind) is something like this:

#! /usr/bin/env python
boards=[
        ((0,1,0),(1,0,1),(0,1,0)),
        ((1,1,1),(0,0,0),(0,0,0)),
        ((0,0,0),(1,1,1),(0,0,0)),
        ((0,0,0),(0,0,0),(1,1,1)),
        ((1,0,0),(1,0,0),(1,0,0)),
        ((0,1,0),(0,1,0),(0,1,0)),
        ((0,0,1),(0,0,1),(0,0,1)),
        ((1,0,0),(0,1,0),(0,0,1)),
        ((0,0,1),(0,1,0),(1,0,0)),
        ((0,0,0),(0,0,0),(0,0,0))
]

def check(board):
        for row in board:
                if all(row):
                        return True
        for col in xrange(len(board)):
                vector=[board[row][col] for row in xrange(len(board))]
                if all(vector):
                        return True
        diag1=[board[i][i] for i in xrange(len(board))]
        if all(diag1):
                return True

        diag2=[board[i][i] for i in xrange(len(board)-1,-1,-1)]
        if all(diag2):
                return True

        return False

if __name__=='__main__':
        for board in boards:
                if check(board):
                        print "Yes"
                else:
                        print "No"