Problem statement

https://leetcode.com/problems/valid-sudoku/

Solution

We just need to check all 27 conditions - for every row, every column and every square.

  1. First 3 lines of code to check rows and columns: we check each row in board and in transposed board *board and collect all elements which are not equal to .
  2. Next 4 lines of code to check all 9 cells: first we create all centers of 3x3 cells and then again collect all elements, not equal to .

Complexity

Time complexity is O(n^2), where n is size of board, space complexity is O(n).

Code

class Solution:
    def isValidSudoku(self, board):
        for row in chain(board, zip(*board)):
            cand = [i for i in row if i != "."]
            if len(set(cand)) != len(cand): return False
            
        for x, y in product([1,4,7],[1,4,7]):
            cand = [board[x+i][y+j] for i,j in product([-1,0,1],[-1,0,1])]
            cand = [i for i in cand if i != "."]
            if len(set(cand)) != len(cand): return False
        
        return True