Skip to content

Prepare For Coder Interview – Denny

  • Basic
  • Medium
  • Hard
  • Architect
  • Life

LeetCode: Sudoku Solver

Posted on January 18, 2018July 26, 2020 by braindenny

Sudoku Solver



Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character ‘.’.

You may assume that there will be only one unique solution.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## https://code.dennyzhang.com/sudoku-solver
## Basic Ideas: backtracking
##             For each '.', try with 0-9.
##                 If test has passed, keep moving forward
##                 Otherwise stop current thread
##
## Complexity: Time O(k), k is the count of '.', Space ?
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if len(board) != 9 or len(board[0]) != 9:
            return 0
        _can_solve = self.mySolveSudoku(board, 0, 0)
        # print("can_solve: %d" % (can_solve))

    def mySolveSudoku(self, board, irow, icol):
        # if irow > 6:
        #    print("irow: %d, icol: %d" % (irow, icol))
        # print board
        if irow == 9:
            return True

        irow2, icol2 = None, None
        if icol == 8:
            irow2, icol2 = irow+1, 0
        else:
            irow2, icol2 = irow, icol + 1

        if board[irow][icol] != '.':
            return self.mySolveSudoku(board, irow2, icol2)

        # try with all possibilities
        for i in xrange(9):
            value = chr(ord('1')+i)
            # Change contenxt: go further
            board[irow][icol] = value
            if self.isSudoku(board, irow, icol, value):
                if self.mySolveSudoku(board, irow2, icol2):
                    return True

        # Restore context: only the outer-layer
        board[irow][icol] = '.'
        return False

    def isSudoku(self, board, irow, icol, value):
        # If we set board[irow][icol] to value, is it still a valid sudoku.
        for index in xrange(9):
            # check row
            if index == icol: continue
            if board[irow][index] == value:
                return False

        for index in xrange(9):
            # check col
            if index == irow: continue
            if board[index][icol] == value:
                return False

        # check section
        istart, jstart = (irow/3)*3, (icol/3)*3
        for i in range(0, 3):
            for j in range(0, 3):
                if istart+i == irow and jstart+j == icol: continue
                if board[istart+i][jstart+j] == value:
                    return False
        return True
linkedin
github
slack

Post Views: 6
Posted in HardTagged #backtracking, #codetemplate

Post navigation

LeetCode: Super Pow
LeetCode: N-Queens

Leave a Reply Cancel reply

Your email address will not be published.

Tags

#array #backtracking #bfs #binarytree #bitmanipulation #blog #classic #codetemplate #combination #dfs #dynamicprogramming #game #graph #greedy #heap #inspiring #interval #linkedlist #manydetails #math #palindrome #recursive #slidingwindow #stack #string #subarray #trie #twopointer #twosum binarysearch editdistance hashmap intervaldp knapsack monotone oodesign presum rectangle redo review rotatelist series sql treetraversal unionfind

Recent Posts

  • a
  • a
  • a
  • a
  • a

Recent Comments

    Archives

    Categories

    • Amusing
    • Basic
    • Easy
    • Hard
    • Life
    • Medium
    • Resource
    • Review
    • Series
    • Uncategorized
    Proudly powered by WordPress | Theme: petals by Aurorum.