Latin Squares

Try starting out with a naive solution where you just go through every value of the matrix and test whether or not that value is in the acceptable range of values and is not repeated in the rows or columns. Then, improve from here.

What data structure could be useful? What data structure has unique interactions with repeats and how could this be useful for our implementation?

How can you test for no repeats in the rows and columns? There is a better way than manually checking every other value in the row and column and comparing with the current value. The better way has to do with the first hint.

When would be a good point to test that values are in the right range of values?

General Solution

1. Create 2 list of sets with a set for every row and every column. The motivation for using sets is that sets guarantee the uniqueness of the values in the set. So, when the algorithm attempts to add a value to the set representing either the row or column that has already appeared in that row or column, the value will not be added again. Thus, in the end, the size of that set will not be $N$ whereas in a latin square all the values are added so the size will be $N$.
2. Iterate through every element in the matrix and insert that element into its corresponding row and column. While iterating through, check to make sure these values are in the acceptable range of values.
3. Finally, iterate through all row sets and column sets and check if the size of sets is less than $N$ or not. If less than $N$, return $0$. Otherwise, return $1$.

This algorithm works largely based off how sets do not allow repeated values. So, when inserting values from the original matrix into the sets, if the value is a repeat in either the row or the column, it will not be inserted into its respective row or column set. Thus, the side of that set will end up being less than $N$.

Walkthrough of Example 2

First, create the 2 lists of sets. There will be 4 sets for the rows and 4 sets for the columns. Then, begin iterating through each element. The first element is a 2 which will be added to the set for row 1 and column 1. Next, add the following value which is also a 2. This time, it is in the second column so add it to that set. Also, attempt to add it to the set for the first row but there is already a 2. Because sets don’t allow repeated values, nothing is added to the set. Continue with the next values in the row which are both 2. As a result, both of these values are not added to the row set because 2 is already in that set but they are added to their column set. After that, continue with the second row. 2 is the first value in this row so it is added to the set for the second row. But, there is already a 2 in the set for the first column so, although an attempt is made, it is not added to the set. Then, the next value is 3 which is new to both its row and column so is successfully added to the second row and second column set. Continue for all values in the matrix. At the end, the size of the row sets will be 1, 2, 2, and 1 for row 1, 2, 3, and 4 respectively. In addition, the size of the column sets will be 1, 2, 1, 2 for columns 1, 2, 3, and 4 respectively. Thus, these sets are not the same size as $N$ so return 0.

Complexity

Iterating through every element in the matrix takes $O(N^2)$ time. Next, inserting values into the sets is $O(1)$. Finally, going through and checking the size of all the row sets and column sets is $O(N)$. Thus, the time complexity of this algorithm is $O(N^2)$.

In terms of additional space, in the worst case, one is storing an additional copy of the matrix in lists of sets. Thus, space would be $O(N^2)$

Sample Solution

def squares(grid, N):
    rows = []
    cols = []
    for _ in range(N): #Initialize the list of sets
        rows.append(set())
        cols.append(set())
    
    for r in range(N):
        for c in range(N):
            curr_val = grid[r][c]
            rows[r].add(curr_val)
            cols[c].add(curr_val)
            if curr_val > N or curr_val <= 0: #Check if the value is out of bounds
                return 0
    for i in range(N):
        if len(rows[i]) != N or len(cols[i]) != N: #Checks for repeated values
            return 0
    return 1

General Solution

The solution is largely similar to the initial solution with how one creates sets and loops through the matrix using sets to find repeats. However, parallelization is accomplished by divvying up the rows and columns to different threads. So, each thread would loop through row i and column i, returning 2 sets representing the corresponding row and column. Then, all the sets are checked to see if they are the correct length.

Complexity

The only potential variation in complexity with the original solution is the complexity for iterating through every element in the matrix as this is now different. Now, every element in the matrix is checked twice, once in a row and once in a column. However, this is still $O(N^2)$. Thus, the time complexity of this algorithm is still $O(N^2)$.

This is a potential disadvantage of this implementation. If there is only one thread, this implementation will actually be slower as it would effectively loop through the matrix twice.

Sample Solution

from multiprocessing import Pool

g = []
size = 0

def helper(index): #This helper method iterates through the row and column corresponding to index and return their sets
    row_set = set()
    col_set = set()
    for i in range(size):
		r_val = g[index][i]
		c_val = g[i][index]
        if r_val > size or c_val > size or r_val <= 0 or c_val <= 0: #Tests if value is out of bounds
            return 0
        row_set.add(r_val)
        col_set.add(c_val)
    return [row_set, col_set]

def squares(grid, N):
    global g, size
    g = grid
    size = N
    with Pool() as pool:
        for diagonal in pool.map(helper, range(size)):
            if not diagonal:
                return 0 #This is the case where a value was out of bounds
            if len(diagonal[0]) != N or len(diagonal[1]) != N:
                return 0 # This is the case where there was a repeated value
            return 1
    return 1