How to find all the numbers in a sequence if some are missing in [Python]

Question

I'm a newbie and have been banging my head against the wall with this problem. I'm sure it's super easy, I just can't figure it out. The trouble I'm having is verifying all the numbers in a sequence if some are missing. So for example let's say I want to verify a sudoku square row and column are valid. Each row and column have to have numbers from 1 to n exactly once in any order. If a sudoku square is of length 3 then numbers 1, 2 and 3 should appear in any order in the rows and columns. My code checks for this but I'm having trouble checking for if I have a row or column like this one:

[4,4,1,2]

It's missing 3. This is how far I got with that code:

for ith, col in enumerate(matrix):
       for num in col:
          for i in range(1, seq + 1)

Here's are all the requirements for the problem:

# Sudoku [http://en.wikipedia.org/wiki/Sudoku]
# is a logic puzzle where a game
# is defined by a partially filled
# 9 x 9 square of digits where each square
# contains one of the digits 1,2,3,4,5,6,7,8,9.
# For this question we will generalize
# and simplify the game.

# Define a procedure, check_sudoku,
# that takes as input a square list
# of lists representing an n x n
# sudoku puzzle solution and returns the boolean
# True if the input is a valid
# sudoku square and returns the boolean False
# otherwise.

# A valid sudoku square satisfies these
# two properties:

#   1. Each column of the square contains
#       each of the whole numbers from 1 to n exactly once.

#   2. Each row of the square contains each
#       of the whole numbers from 1 to n exactly once.

# You may assume the the input is square and contains at
# least one row and column. 

correct = [[1, 2, 3],
           [2, 3, 1],
           [3, 1, 2]]

incorrect = [[1, 2, 3, 4],
             [2, 3, 1, 3],
             [3, 1, 2, 3],
             [4, 4, 4, 4]]

incorrect2 = [[1, 2, 3, 4],
              [2, 3, 1, 4],
              [4, 1, 2, 3],
              [3, 4, 1, 2]]

incorrect3 = [[1, 2, 3, 4, 5],
              [2, 3, 1, 5, 6],
              [4, 5, 2, 1, 3],
              [3, 4, 5, 2, 1],
              [5, 6, 4, 3, 2]]

incorrect4 = [['a', 'b', 'c'],
              ['b', 'c', 'a'],
              ['c', 'a', 'b']]

incorrect5 = [[1, 1.5],
              [1.5, 1]]

correct2 = [[1, 2, 3, 4],
            [2, 4, 1, 3],
            [3, 1, 4, 2],
            [4, 3, 2, 1]] 

This is the code I've written so far:

def checkSquare(square): # Checks to see if it's a perfect square matrix(3X3, 4X4, etc)

    colLen = len(square[0]) # Counts the number of columns in matrix
    rowLen = len(square) # Counts the number of rows in the matrix

    #print("Check the length of the columns:", colLen)
    #print("Check the length of the rows:", rowLen)
    if colLen == rowLen:
        #print("True")
        return True
    else:
        #print("False")
        return False

def checkSequenceRow(square):
    seq = len(square) # seq is the 'n' in 1 to n
    for row in range(len(square)):
        for num in range(1, seq+1): # for loop that will go from 1 to seq or 'n'
            if num not in square[row]: # if num not in the row
                print("False")
                return False
        row = row + 1
    print("True")
    return True

''''''
def checkSequenceCol(square):
    seq = len(square)
    columns = zip(*square)
    for icol, column in enumerate(columns):
        for col in column:
            if col not in range(1, seq + 1):
                print("False")
                return False
    print("True")
    return True

def check_sudoku(square):
    if checkSquare(square) & checkSequenceRow(square) & checkSequenceCol(square) == True:
        print("True")
        return True
    else:
        print("False")
        return False

checkSequenceCol(incorrect)

Any help would be great.

Answer 1

Just adding to Maokai answer to make it more simple:

a = [4,4,1,2]
b = set(range(1, len(a) + 1)).difference(set(a))
print(sorted(list(b)))

Code above will print missing numbers from provided array as list

Answer 2

I would use set for comparison: set creates a collection of unique items, and comparisons between two sets are only True if all elements are shared across both sets. You can get a set of the row or column and then compare it to a set created from the len of the row or column (starting the range at 1). For accessing the columns, I would convert the list of lists to a numpy array.

def check_row(square):
    for row in square:
        if set(row) != set(range(1, len(row) + 1)):
            print(False)
            return False
    print(True)

def check_col(square):
    # Numpy array 
    square = np.array(square)
    for i in range(square.shape[1]):
        # Select the column
        col = square[i, :]
        if set(col) != set(range(1, len(col) + 1)):
            print(False)
            return False
    print(True)

This passes all the test cases you provided.

Answer 3

I would give this a try. I'll give you checkSequenceRow, and hopefully you can adapt for the other function. What you are missing, based on your description, is a record of numbers you have already seen, hence [4, 4, 1, 2]. This code is close to what you have done, so it should be easy to understand, but Python's set is a better, more pythonic way. I would encourage you to investigate it.

def checkSequenceRow(square):
    for row in range(len(square)):  # go row by row
        seen = []
        n = len(row)
        for number in range(len(row)): # validate the row
            if number in seen: # found a duplicate
                return False
            elif number < 1 or number > n: # found an invalid value
                return False
            else:
                seen.append(number) # keep track of this valid value
    return True

Answer 4

You can use python's Set for this purpose.

Let's say you have an array a with length n, and you want to know if it is from 1 to n, you can check it this way:

set(a) == set(range(1, len(a) + 1))

The left hand side makes a set from a, while the right hand side generates a set {1, 2, ..., n}. If they are equal, you should be able to claim that a has all the elements from 1 to n.

In your example above, set([4, 4, 1, 2]) results in a set {1, 2, 4}, so it is not equal to the desirable set {1, 2, 3, 4}.