Java solution with List and Set


  • 0
    H

    public class Solution {
    List<Set<Character>> row = new ArrayList<Set<Character>>();
    List<Set<Character>> col = new ArrayList<Set<Character>>();
    List<Integer[]> blank = new ArrayList<Integer[]>();
    Set<Character>[][] sub = new HashSet[3][3];

    public boolean backCheck(int ind, char[][] board) {
        if(ind == blank.size()) return true;
        
        Integer[] target = blank.get(ind);
        boolean finished = false;
    
        for(char i='1'; i<='9'; i++)
            if(!row.get(target[0]).contains(i) && !col.get(target[1]).contains(i) && !sub[target[0]/3][target[1]/3].contains(i)) {
                board[target[0]][target[1]] = i;
                row.get(target[0]).add(i);
                col.get(target[1]).add(i);
                sub[target[0]/3][target[1]/3].add(i);
                if(backCheck(ind+1, board)) {
                    finished = true;
                    break;
                }
                row.get(target[0]).remove(i);
                col.get(target[1]).remove(i);
                sub[target[0]/3][target[1]/3].remove(i);
            }
        
        return finished?true:false;
    }
    
    public void solveSudoku(char[][] board) {
        if(board == null) return;
        
        for(int i=0; i<board.length; i++) {
            Set<Character> r = new HashSet<Character>();
            Set<Character> c = new HashSet<Character>();
            row.add(r);
            col.add(c);
        }
        for(int i=0; i<board.length/3; i++)
            for(int j=0; j<board.length/3; j++) {
                Set<Character> s = new HashSet<Character>();
                sub[i][j] = s;            
            }
        
        for(int i=0; i<board.length; i++)
            for(int j=0; j<board[i].length; j++) 
                if(board[i][j] != '.') {
                    row.get(i).add(board[i][j]);
                    col.get(j).add(board[i][j]);
                    sub[i/3][j/3].add(board[i][j]);
                } else {
                    Integer[] b = new Integer[2];
                    b[0] = i;
                    b[1] = j;
                    blank.add(b);
                }
        backCheck(0, board);        
    }
    

    }


Log in to reply
 

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