Leetcode: Sudoku Solver

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.

## Blog link: 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
            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

Share It, If You Like It.

Leave a Reply

Your email address will not be published.