prepbook
  • Introduction
  • Some common stuff
    • python __repr__
    • HackerRank input tips
  • Data Structures and Algorithms
    • Breadth first search
    • Depth First Search
    • Dijkstra
    • A* Search Algorithm
    • Binary Search
    • python counter
    • Sorting
      • Merge Sort
      • Quick Sort
    • Priority Queue
  • Multiprocessing vs Threading
  • Common Coding
    • Find loop in lin list
    • Maximum sum subarray
  • Coding
    • Valid palindrome
    • Palindrome number
    • Remove duplicates from sorted array
    • Island perimeter
    • Serialize and Deserialize Binary Tree
    • Valid Soduku
    • Word Pattern
    • Word Pattern II
    • Group Anagrams
    • Implement Trie
    • Deep copy list with random node
    • Palindrome Permutation
    • Combination Sum
    • Clone Graph
    • Generate parenthesis
    • Fibonacci Number
    • LRU Cache
    • Merge two sorted arrays in place
    • Hamming Distance
    • Merge K sorted arrays
    • Kth smalles element in BST
    • Kth largest element in an array
    • Remove duplicates from sorted list
    • Power of 2
    • Nested list weight sum
    • SIngle number in a list
    • Factor combinations
    • Delete node from BST
  • hacker Rank
    • Coding
      • print staircase
      • Drawing book
      • Challenge 0
      • Min-Max sum
  • WorkRelatedCoding
    • Rectangle Overlap
  • Python tips
Powered by GitBook
On this page

Was this helpful?

  1. Coding

Valid Soduku

PreviousSerialize and Deserialize Binary TreeNextWord Pattern

Last updated 5 years ago

Was this helpful?

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

Note: A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

class Solution(object):
    def isValidSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: bool
        """
        if not board:
            return False

        inspectH = {}   
        rows = len(board)
        cols = len(board[0])

        if rows != 9 or cols != 9:
            return False

        for i in xrange(rows):

            row_name = "row_" + str(i)   
            #print row_name

            for j in xrange(cols):

                item = board[i][j]
                if item == '.':
                    continue

                ***# 1. keep collecting the items respective to each column***
                col_name = "col_" + str(j)
                if col_name not in inspectH:
                    inspectH[col_name] = [item]
                else:
                    inspectH[col_name].append(item)

                ***# 2. keep collecting the items respective to each row***
                if row_name not in inspectH:
                    inspectH[row_name] = [item]
                else:
                    inspectH[row_name].append(item)

                ***# 3. keep collecting the items with respect to each basket
                # this will help inspect each internal 3x3 soduku grids
                # after every 3 rows***
                if j <= 2:
                    basket_name = "basket_1"
                elif j <= 5:
                    basket_name = "basket_2"
                else:
                    basket_name = "basket_3"

                if basket_name not in inspectH:
                    inspectH[basket_name] = [item]
                else:
                    inspectH[basket_name].append(item)

            ***# now check the duplicates for every row***
            if row_name in inspectH:
                if len(inspectH[row_name]) != len(set(inspectH[row_name])):
                    return False
                else:
                    del inspectH[row_name]

            ***# now check the duplicates for the baskets - for every 3 rows***
            if (i+1) % 3 == 0:
                if "basket_1" in inspectH:
                    if len(inspectH["basket_1"]) != len(set(inspectH["basket_1"])):
                        return False
                    else:
                        del inspectH["basket_1"]

                if "basket_2" in inspectH:
                    if len(inspectH["basket_2"]) != len(set(inspectH["basket_2"])):
                        return False
                    else:
                        del inspectH["basket_2"]

                if "basket_3" in inspectH:
                    if len(inspectH["basket_3"]) != len(set(inspectH["basket_3"])):
                        return False
                    else:
                        del inspectH["basket_3"]



        ***# outside the for loops check the duplicates for each colum***
        for k, v in inspectH.iteritems():
            if len(v) != len(set(v)):
                return False

        ***# finally all is well. so return True***      
        return True