[Java] One Mistake Made


  • 0
    L

    I make mistakes in this problem. I think it might be meaningful to mark them here.

    1. Backtracking: When I know whether or not one cell is filled with a potential correct character, I should only check repeated characters among those I already filled before or given by problem instead of all characters. Because if I didn't clear the cells after one function call exit, what that function writes in the sudoku matrix is still existing.

    2. Mark given characters: To know what characters are given by problem, it needs to mark those given characters in a matrix. This accelerates the whole process.

    My final accepted code:

    public class Solution {
        int[][] d;
        boolean[][] mark;
        boolean over;
        
        public void solveSudoku(char[][] board) {
            d = new int[9][9];
            mark = new boolean[9][9];
            over = false;
            
            int i,j;
            
            for(i=0;i<9;i++){
                for(j=0;j<9;j++){
                    if(board[i][j]=='.'){
                        d[i][j] = -1;
                    } 
                    else{ 
                        d[i][j] = (int)(board[i][j]) - (int)('0');
                        mark[i][j] = true;
                    }
                }
            }
            
            solve(geti(0,-1), getj(0,-1));
            
            for(i=0;i<9;i++){
                for(j=0;j<9;j++){
                    board[i][j]= (char)((int)'0'+d[i][j]);
                }
            }
        }
        
        public void solve(int i, int j){
            int value;
            if(i==9){
                over = true;
                return;
            }
            
            for(value=1;value<10 && !over;value++){
                d[i][j] = value;
                if(isValid(i,j)){
                    int newi = geti(i,j);
                    int newj = getj(i,j);
                    solve(newi, newj);
                }
            }
        }
        
        public int geti(int i, int j){
            int x=i, y=j;
            y++;
            if(y==9){
                y=0;
                x++;  
            }
            while(x<9 && mark[x][y]){
                y++;
                if(y==9){
                    y=0;
                    x++;  
                } 
            }
            return x;
        }
        
        public int getj(int i, int j){
            int x=i, y=j;
            y++;
            if(y==9){
                y=0;
                x++;  
            }
            while(x<9 && mark[x][y]){
                y++;
                if(y==9){
                    y=0;
                    x++;  
                } 
            }
            return y;
        }
        
        public boolean isValid(int i, int j){
            int row, col;
            for(row=0;row<9;row++){
                if(mark[row][j]){// already filled
                    if(d[row][j]==d[i][j]) return false;
                }
                else{//for user to fill
                    if(row<i && d[row][j]==d[i][j]) return false;
                }
            }
            
            for(col=0;col<9;col++){
                if(mark[i][col] && col!=j){// already filled
                    if(d[i][col]==d[i][j]) return false;
                }
                else{//for user to fill
                    if(col<j && d[i][col]==d[i][j]) return false;
                }
            }
            
            int basei = 3*(int)(i/3), basej = 3*(int)(j/3);
            for(row=basei;row<basei+3;row++){
                for(col=basej;col<basej+3;col++){
                    if(mark[row][col] && row!=i && col!=j){// already filled
                        if(d[row][col]==d[i][j]) return false;
                    }
                    else{//for user to fill
                        if(d[row][col]==d[i][j]) {
                            if(row<i) return false;
                            else if(row==i && col<j) return false;
                        }
                    }
                }
            }
            return true;
        }
    }

Log in to reply
 

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