10ms Java DFS. (start from the block with the least possibilities)


  • 0
    public class Solution {
        
    	private static int[][] d = {{0,0}, {0,1}, {1,2}, {1,0}, {1,1}, {1,2}, {2,0}, {2,1}, {2,2}};
    
    	private boolean solve(char[][] board, Set<Integer>[][] set) {
    		//find the element which has least possibilities
    		int min = 10, min_x = -1, min_y = -1;
    		for (int i=0; i<9; i++)
    			for (int j=0; j<9; j++)
    				if (board[i][j]=='.' && set[i][j].size()<min) {
    					min = set[i][j].size();
    					min_x = i;
    					min_y = j;
    				}
    		if (min==10) 
    			return true;
    		// try all possibilities.
    		Set<Integer> p = set[min_x][min_y];
    		List<Integer> mx = new ArrayList<Integer>();
    		List<Integer> my = new ArrayList<Integer>();
    		for (int number: p) {
    			//update set and board
    			mx.clear();my.clear();
    			for (int i=0; i<9; i++) {
    				if (i!=min_y && board[min_x][i]=='.' && set[min_x][i].contains(number)) {
    					set[min_x][i].remove(number);
    					mx.add(min_x);my.add(i);
    				}
    				if (i!=min_x && board[i][min_y]=='.' && set[i][min_y].contains(number)) {
    					set[i][min_y].remove(number);
    					mx.add(i);my.add(min_y);
    				}
    				int xx = min_x/3*3+d[i][0], yy = min_y/3*3+d[i][1];
    				if ((xx!=min_x || yy!=min_y) && board[xx][yy]=='.' && set[xx][yy].contains(number)) {
    					set[xx][yy].remove(number);
    					mx.add(xx);my.add(yy);
    				}
    			}
    			board[min_x][min_y] = (char) (number+48);
    			//try next
    			if (solve(board, set)) return true;
    			//recover set
    			for (int i=0; i<mx.size(); i++)
    				set[mx.get(i)][my.get(i)].add(number);
    			board[min_x][min_y] = '.';
    		}
    		return false;
    	}
    	
    
    	public void solveSudoku(char[][] board) {
    		Set<Integer>[][] set = new Set[9][9];
    		for (int i=0; i<9; i++)
    			for (int j=0; j<9; j++) 
    				if (board[i][j]=='.'){
    					set[i][j] = new HashSet<Integer>();
    					set[i][j].addAll(Arrays.asList(1,2,3,4,5,6,7,8,9));
    				}
    		for (int i=0; i<9; i++)
    			for (int j=0; j<9; j++) 
    				if (board[i][j]=='.') {
    					//delete numbers shown in same line
    					for (int k=0; k<9; k++)
    						if (board[i][k]!='.')
    							set[i][j].remove(board[i][k]-48);
    					//delete numbers shown in same column
    					for (int k=0; k<9; k++)
    						if (board[k][j]!='.')
    							set[i][j].remove(board[k][j]-48);
    					//delete numbers shown in same box
    					int ox = i/3*3,
    						oy = j/3*3;
    					for (int k=0; k<9; k++)
    						if (board[ox+d[k][0]][oy+d[k][1]]!='.')
    							set[i][j].remove(board[ox+d[k][0]][oy+d[k][1]]-48);
    				}
    		solve(board, set);
    	}
    }

Log in to reply
 

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