Simple Java bactracing solution


  • 0
    Z
    public class Solution {
        public void solveSudoku(char[][] board) {
            boolean[][] row = new boolean[9][9];
            boolean[][] col = new boolean[9][9];
            boolean[][] block = new boolean[9][9];
            for(int i =0;i<9;i++){
                for(int j=0;j<9;j++){
                    char c = board[i][j];
                    if( c== '.') continue;
                    int t = c-'1';
                    row[i][t]=true;
                    col[j][t]=true;
                    block[(i/3)*3+j/3][t] = true;
                }
            }
            solve(board,row,col,block,0);
        }
        public boolean solve(char[][] board,boolean[][] row,boolean[][] col,boolean[][] block,int v) {
            if(v == board.length*board[0].length) return true;
            int i = v/board[0].length;
            int j = v%board[0].length;
            if( board[i][j] != '.') return solve(board,row,col,block,v+1);
            for(int num=0;num<9;num++){
                if(row[i][num]||col[j][num]||block[(i/3)*3+j/3][num]) continue;
                board[i][j] = (char) ('1'+num);
                row[i][num]=true;
                col[j][num]=true;
                block[(i/3)*3+j/3][num] = true;
                if(solve(board,row,col,block,v+1)) return true;
                board[i][j] = '.';
                row[i][num]=false;
                col[j][num]=false;
                block[(i/3)*3+j/3][num] = false;
            }
            
            return false;
        }
    }
    

Log in to reply
 

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