choose_unique_N.py

import random

def choose_unique_N(matrix):
    """Choose N elements from an N x N square matrix, such that;
        1. The elements are chosen at-random
        2. One element per row
        3. One element per column
        4. No duplicate elements
        
       Returns None if and only if there is no set of N elements 
       satisfying the selection constraints.
    """
    assert isinstance(matrix, list)
    N = len(matrix)

    # If the matrix has just one element, return it. This is one
    # of our terminating conditions
    if N == 1:
        return matrix[0]

    # Create an iterable list of all element coordinates, e.g.
    #  [ [ 0, 0 ] , [ 0, 1 ] , [ 1, 0 ], [ 1 , 1 ] ] for a 2x2 matrix
    element_coords = [ ]
    for i in range( N ):
        # Make sure it's a square matrix
        assert isinstance(matrix[i], list)
        assert len(matrix[i]) == N 

        for j in range( N ):
            element_coords.append( [ i, j ] )

    # Shuffle that list of coordinates
    random.shuffle(element_coords)

    # Starting with the first element in our shuffled list, try
    # each one.
    for coord in element_coords:

        # Get the actual candidate element at that position
        candidate = matrix[ coord[0] ][ coord[1] ]

        # form a new sub matrix with the rows and cols that are *not* 
        # the coordinate row or column.
        sub_matrix_coords = filter( lambda xy: xy[0] != coord[0] and xy[1] != coord[1], element_coords )

        # populate the sub-matrix
        sub_matrix = [ [ None ] * (N - 1) ] * (N - 1)
        i = 0
        for x in range( N - 1 ):
            for y in range( N - 1 ):
                sub_matrix[x][y] = matrix[ sub_matrix_coords[ i ][0] ][ sub_matrix_coords[ i ][1] ]
                i += 1

        # Recurse and choose a valid set from our sub-matrix
        sub_matrix_chosen = choose_unique_N(sub_matrix)

        # If set of elements chosen from the sub matrix is non-empty, and doesn't overlap with 
        # our candidate, use it.
        if sub_matrix_chosen != None and candidate not in sub_matrix_chosen:
            sub_matrix_chosen.append(candidate)
            return sub_matrix_chosen

        # or else loop and try the next candidate

    return None