1-7 lines Python, 4 solutions


  • 52

    Idea

    Just go through all you see (like "7 in row 3") and check for duplicates.

    Solution 1

    Using Counter. One logical line, seven physical lines.

    def isValidSudoku(self, board):
        return 1 == max(collections.Counter(
            x
            for i, row in enumerate(board)
            for j, c in enumerate(row)
            if c != '.'
            for x in ((c, i), (j, c), (i/3, j/3, c))
        ).values() + [1])
    

    The + [1] is only for the empty board, where max would get an empty list and complain. It's not necessary to get it accepted here, as the empty board isn't among the test cases, but it's good to have.

    Solution 2

    Using len(set).

    def isValidSudoku(self, board):
        seen = sum(([(c, i), (j, c), (i/3, j/3, c)]
                    for i, row in enumerate(board)
                    for j, c in enumerate(row)
                    if c != '.'), [])
        return len(seen) == len(set(seen))
    

    Solution 3

    Using any.

    def isValidSudoku(self, board):
        seen = set()
        return not any(x in seen or seen.add(x)
                       for i, row in enumerate(board)
                       for j, c in enumerate(row)
                       if c != '.'
                       for x in ((c, i), (j, c), (i/3, j/3, c)))
    

    Solution 4

    Iterating a different way.

    def isValidSudoku(self, board):
        seen = sum(([(c, i), (j, c), (i/3, j/3, c)]
                    for i in range(9) for j in range(9)
                    for c in [board[i][j]] if c != '.'), [])
        return len(seen) == len(set(seen))

  • 14
    G

    Your solutions are briliant! Just another way to write Solution2:

    def isValidSudoku(self, board):
        seen = []
        for i, row in enumerate(board):
            for j, c in enumerate(row):
                if c != '.':
                    seen += [(c,j),(i,c),(i/3,j/3,c)]
        return len(seen) == len(set(seen))

  • 3

    Yeah, that's another option, and more efficient. Though Sudoku boards are so tiny I don't think that it matters much :-)

    No need to create lists, btw, adding tuples works and is faster:

    seen += (c,j),(i,c),(i/3,j/3,c)
    

    Mine don't need to work with lists, either, though switching to tuples wouldn't save a single character and would make it a bit harder to read (I'd have four ( in a row).


  • -1
    P

    how do you handle when c<1 or c>9?

    also, can you explain tuple (i/3, j/3, c)? why not (i, j, c)?

    why (c, j) but (i, c)? (the order of c, j, and i)


  • 3

    how do you handle when c<1 or c>9?

    Don't know what you mean. Since c is a string, those comparisons aren't even defined.

    also, can you explain tuple (i/3, j/3, c)? why not (i, j, c)?

    Because (i/3, j/3) identifies one of the nine 3x3 blocks.

    why (c, j) but (i, c)? (the order of c, j, and i)

    To distinguish rows and columns, for example ('4', 4) and (4, '4').


  • 0
    P

    Why won't this work? Even though for such a small board this doesn't matter that much - just want to explore different options.

    class Solution(object):
        def isValidSudoku(self, board):
            seen = set()
            for i, row in enumerate(board):
                for j, c in enumerate(row):
                    if c != '.':
                        comb = (c,j),(i,c),(i/3,j/3,c)
                        if comb in seen: return False
                        else: seen.add(comb)
            return True

  • 1

    Well you can't find duplicates if you completely specify exactly one cell with your triple. You need to instead check the three things separately.


  • 0
    P

    But in

    return len(set(seen)) == len(seen)
    

    why do we treat triple of triples as whole?


  • 0

    Don't know what you mean, neither of us is using a triple of triples. What I use a a list of things like "7 in row 3". And what you're using is things like "7 in row 3 in column 6".


  • 0

    I suggest you test both of our solutions on an example and compare what we have in our seen.


  • 0
    P

    Sorry I meant tuple of triples. I'll do a test then! Thanks for your time


  • 1
    I

    For solution 2, why not only use list comprehension? It's more readable.

    def isValidSudoku(self, board):
        seen=[x for i, row in enumerate(board) 
                    for j, c in enumerate(row) 
                        if c!='.' 
                            for x in ((c,i),(j,c),(i/3,j/3,c))]
        return len(seen)==len(set(seen))

  • 0

    Hmm, I don't remember. Maybe because mine was slightly shorter, or it was one of those cases where I do unusual things just to showcase them. I agree yours is more readable. I think many people don't even know that sum has a second parameter.


  • 0
    J

    Thanks very much for your sharing! I do love your pythonic code and learn a lot every time!


  • 0
    F

    The "+ [1]" trick of Solution-1 needs a bit of change for python3

    max(list(collections.Counter(...)) + [1])


  • 0
    P
    This post is deleted!

  • 0

    Add one regex solution, but much uglier ...

    def isValidSudoku(self, board):
    	return all(map(lambda bulk: re.match(r'(?:([1-9])(?!.*\1))*$', ''.join(bulk).replace('.', '')), 
    			board + zip(*board) + [[board[i][j]
    				for i in range(m, m+3) for j in range(n, n+3)]
    				for m in range(0, 9, 3) for n in range(0, 9, 3)]))

  • 0
    L

    @StefanPochmann Interesting, would adding tuples like "seen += (c,j),(i,c),(i/3,j/3,c)" be equivalent to?:

    seen.append((c,j))
    seen.append((i,c))
    seen.append((i/3,j/3,c))

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.