[LeetCode 37] Sudoku Solver

Question

link

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.

A sudoku puzzle...

...and its solution numbers marked in red.

Stats

Frequency	2
Difficulty	4
Adjusted Difficulty	5
Time to use	----------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Solution

This is a very classic DFS search problem, and it is not easy.

The solution simply brute force DFS. Read more at this blog.

My code

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

    private char[][] helper(char[][] board, int N, int x, int y) {
        if (x == N) {
            return board;
        } else if (y == N) {
            return helper(board, N, x + 1, 0);
        } else if (board[x][y] != '.') {
            // made a mistake here with (y+1) instead of (x+1)
            return helper(board, N, x, y + 1);
        } else {
            // put in from 1 to 9, and then check validation
            for (int i = 1; i <= 9; i++) {
                board[x][y] = (char) ('0' + i);
                if (isValid(board, x, y)) {
                    // if the number we just put in is valid inside the board
                    char[][] ans = helper(board, N, x, y + 1);
                    if (ans != null) {
                        return ans;
                    } else {
                        // putting in this number (i) will not work, so...
                        // put in next number and try, until 9
                    }
                }
                // this is important for backtarcking - set the char back to its original value!!!
                board[x][y] = '.';
            }
        }
        // in fact, we can just return true/false for this question.
        return null;
    }

    // this validation method we borrowed from my old code
    private boolean isValid(char[][] board, int i, int j) {
        boolean[] map = new boolean[9];
        for (int k = 0; k < 9; k++)
            if (k != j && board[i][k] == board[i][j])
                return false;
        for (int k = 0; k < 9; k++)
            if (k != i && board[k][j] == board[i][j])
                return false;
        for (int row = i / 3 * 3; row < i / 3 * 3 + 3; row++)
            for (int col = j / 3 * 3; col < j / 3 * 3 + 3; col++)
                if ((row != i || col != j) && board[row][col] == board[i][j])
                    return false;
        return true;
    }
}