Problem statement

https://binarysearch.com/problems/Latin-Square-Solver/

Solution

The idea is similar that we used in BinarySearch 0073 Sudoku Solver

Complexity

It is exponential, it is difficult to estimate.

Code

class Solution:
    def solve(self, M):
        n = len(M)
        def dfs(M, empty, rows, cols):
            if not empty: return True
            r, c = empty[-1]
            for k in set(range(1, n + 1)) - (rows[r]|cols[c]):
                M[r][c] = k
                for dic in [rows[r], cols[c]]:
                    dic.add(k)
                if dfs(M, empty[:-1], rows, cols): return True
                M[r][c] = '.'
                for dic in [rows[r], cols[c]]:
                    dic.remove(k)

            return False
        
        cols, rows, empty = defaultdict(set), defaultdict(set), []
        
        for row in chain(M, zip(*M)):
            cl = [i for i in row if i]
            if len(cl) != len(set(cl)): return False

        for r, c in product(range(n), range(n)):
            if M[r][c] == 0:
                empty.append((r, c))
            else:
                for dic in [rows[r], cols[c]]:
                    dic.add(M[r][c])
               
        return dfs(M, empty, rows, cols)