Java solution with explanation


  • 0
    L

    There may be better ways of solving this problem but I think it follows a pattern of backtracking where you try a certain number and back off if it doesn't work out. The challenge is that the stack growth is enormous and it may be difficult to perceive how to handle a backtrack to earlier stacks if the last solution doesn't work out. Here is my recipe for this problem before the code:

    1. Start with 0,0 and let the recursive function make it move to the last cell by increasing it by 1 everytime
    2. Following is the structure of a backtrack function:
      a. Exit conditions
      a.1 true when we have visited all rows and cols so return true.
      a.2 false when the value given is not acceptable.
      b. backtracking logic
      b.1 check a '.' and then use '1' to '9' for replacing it and invoking the function for that value. If the next stack returns false, you got to try the next value. Remember to reset the value to '.' everytime you fail. Also, if none of the tries pass, just return false to avoid any infinite loop.
      c. Manage the counter by checking for rows and cols
      d. Call the function for regular case.

    Here is the code :

    int size = 9;
    int subsize = 3;
    
    public boolean solveSukodu(char[][] board) {
        return helper(board, 0, 0);
    }
    
    
    
    private boolean helper(char[][] board, int row, int col) {
        if (row >= size) {
            return true;
        }
        if (!isNumberValid(board, row, col)) {
            return false;
        }
        if (board[row][col] == '.') {
            char c = '1';
            for (; c <= '9'; c++) {
                board[row][col] = c;
                if (!helper(board, row, col)) {
                    board[row][col] = '.';
                } else {
                    break;
                }
            }
            if (c > '9') {
                return false;
            }
        } else {
            col++;
            if (col >= size) {
                row++;
                col = 0;
            }
        }
        return helper(board, row, col);
    }
    
    
    
    private boolean isNumberValid(char[][] board, int row, int col) {
        char c = board[row][col];
        for (int i = 0; i < size; i++) {
            if (board[i][col] != '.' && i != row &&
                board[i][col] == c) {
                return false;
            }
        }
        for (int i = 0; i < size; i++) {
            if (board[row][i] != '.' && i != col &&
                board[row][i] == c) {
                return false;
            }
        }
        int m = row / subsize * subsize;
        int n = col / subsize * subsize;
        for (int i = 0; i < subsize; i++) {
            for (int j = 0; j < subsize; j++) {
                if (board[i + m][j + n] != '.' &&
                    ((i + m) != row && (j + n) != col) &&
                    board[i + m][j + n] == c) {
                    return false;
                }
            }
        }
        return true;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.