Sudoku Solver

Problem: Sudoku Solver

We can maintain hash table for row, column and block elements and fill the Sudoku based on these 3 hash tables.

Code in Python:

class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        row_dict = [[False] * 9 for _ in xrange(9)]
        col_dict = [[False] * 9 for _ in xrange(9)]
        blk_dict = [[[False] * 9 for _ in xrange(3)] for _ in xrange(3)]
        todo = []

        for i in xrange(9):
            for j in xrange(9):
                if board[i][j] != '.':
                    num = int(board[i][j])-1
                    row_dict[i][num] = True
                    col_dict[j][num] = True
                    blk_dict[i/3][j/3][num] = True
                else:
                    todo.append((i,j))
        self.n = len(todo)

        def helper(position):
            if position == self.n: return True
            r, c = todo[position]
            for x in xrange(9):
                if not row_dict[r][x] and not col_dict[c][x] and not blk_dict[r/3][c/3][x]:
                    board[r][c] = str(x+1)
                    row_dict[r][x], col_dict[c][x], blk_dict[r/3][c/3][x] = True, True, True
                    if helper(position+1): return True
                    board[r][c] = '.'
                    row_dict[r][x], col_dict[c][x], blk_dict[r/3][c/3][x] = False, False, False
            return False

        helper(0)

Code in Java:

public class Solution {
    public void solveSudoku(char[][] board) {
        boolean[][] rows = new boolean[9][9];
        boolean[][] cols = new boolean[9][9];
        boolean[][] blocks = new boolean[9][9];
        ArrayList<ArrayList<Integer>> toFill = new ArrayList<ArrayList<Integer>>();

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int number = board[i][j] - '1';
                    rows[i][number] = true;
                    cols[j][number] = true;
                    blocks[i/3*3+j/3][number] = true;
                } else {
                    ArrayList<Integer> blank = new ArrayList<Integer>();
                    blank.add(i);
                    blank.add(j);
                    toFill.add(blank);
                }
            }
        }

        solve(board, rows, cols, blocks, toFill, 0);
    }

    public boolean solve(char[][] board, boolean[][] rows, boolean[][] cols, boolean[][] blocks, List<ArrayList<Integer>> toFill, int location) {
        if (location == toFill.size()) return true;
        int i = toFill.get(location).get(0), j = toFill.get(location).get(1);
        for (int x = 0; x < 9; x++) {
            if (rows[i][x] == true ||
                cols[j][x] == true ||
                blocks[i/3*3+j/3][x] == true)
                continue;
            else {
                board[i][j] = Character.forDigit(x+1, 10);
                rows[i][x] = true;
                cols[j][x] = true;
                blocks[i/3*3+j/3][x] = true;
                if (solve(board, rows, cols, blocks, toFill, location+1)) return true;
                else {
                    board[i][j] = '.';
                    rows[i][x] = false;
                    cols[j][x] = false;
                    blocks[i/3*3+j/3][x] = false;
                }
            }
        }
        return false;
    }
}