37. Sudoku Solver

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

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character '.'.

Note:

• The given board contain only digits 1-9 and the character '.' .
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9

Solution

(1) Java

class Solution {
    public void solveSudoku(char[][] board) {
        if (board == null || board.length != 9 || board[0].length != 9) {
            return;
        }
        helper(board);
    }

    private boolean helper(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c == '.') {
                    for (char k = '1'; k <= '9'; k++) {
                        board[i][j] = k;
                        if (validate(board, i, j) && helper(board)) {
                            return true;
                        } else {
                            board[i][j] = '.';
                        }
                    }
                    if (board[i][j] == '.') {
                        return false;
                    }
                }            
            }
        }
        return true;
    }

    private boolean validate(char[][] board, int i, int j) {
        char c = board[i][j];
        for (int k = 0; k < 9; k++) {
            if ((k != i && c == board[k][j]) || (k != j && c == board[i][k]) || ( i != 3*(i/3)+k/3 && j != 3*(j/3)+k%3  && c == board[3*(i/3)+k/3][3*(j/3)+k%3])) {
                return false;
            }
        }       
        return true;
    }
}

(2) Python

class Solution:
    def isValid(self, board, i, j):
        c = board[i][j]
        for k in range(9):
            if (k!=i and c==board[k][j]) or \
               (k!=j and c==board[i][k]) or (i!=3*int(i/3)+int(k/3) and j!=3*int(j/3)+k%3 and c==board[3*int(i/3)+int(k/3)][3*int(j/3)+k%3]):
                return False
        return True

    def helper(self, board):
        for i in range(9):
            for j in range(9):
                c = board[i][j]
                if c == '.':
                    for k in range(9):
                        board[i][j] = str(k+1)
                        if self.isValid(board, i, j) and self.helper(board):
                            return True
                        else:
                            board[i][j] = '.'
                    if board[i][j] == '.':
                        return False
        return True

    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: void Do not return anything, modify board in-place instead.
        """
        if not board or len(board) != 9 or len(board[0]) != 9:
            return
        self.helper(board)

(3) Scala