Sudoku Solver

Question Description

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.

Solution

First, scan the matrix to build the hashmap for rows, columns and cubes and to locate the positions which need to be filled.

Second, do DFS search using the matrix of positions to check availability of different numbers for unfilled positions. If we found the solution, just quit the recursion.

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        row, col, cube = [[False] * 9 for x in range(9)], [[False] * 9 for x in range(9)], [[False] * 9 for x in range(9)]
        pos = []
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    row[i][int(board[i][j]) - 1] = True
                    col[j][int(board[i][j]) - 1] = True
                    cube[(i // 3) * 3 + j // 3][int(board[i][j]) - 1] = True
                else:
                    pos.append(9 * i + j)
        self.backtrack(board, row, col, cube, pos)

    def backtrack(self, board, row, col, cube, pos):
        if len(pos) == 0:
            return True
        x, y = pos[-1] / 9, pos[-1] % 9
        pos.pop()
        for i in range(9):
            if not row[x][i] and not col[y][i] and not cube[(x // 3) * 3 + y // 3][i]:
                row[x][i] = col[y][i] = cube[(x // 3) * 3 + y // 3][i] = True
                board[x][y] = str(i + 1)
                if self.backtrack(board, row, col, cube, pos):
                    return True
                row[x][i] = col[y][i] = cube[(x // 3) * 3 + y // 3][i] = False
                board[x][y] = '.'
        pos.append(x * 9 + y)
        return False