private static boolean dfs(char[][] board, int x, int y) {
    	if (x == 9 || y == 9) return true;
    	
    	if (board[x][y] == '.') {
    		for (int k = 1; k <= 9; ++k) {
    			if (isValid(board, x, y, (char)('0'+k))) {
    				board[x][y] = (char)('0'+k);
    				int nextx = x;
    				int nexty = y+1;
    				if (nexty == 9) {
    					nexty = 0; 
    					nextx++;
    				}
    				if (dfs(board, x, y)) return true;
    			}
    			board[x][y] = '.';
    		}
    		return false;
    	}
    	else {
    		int nextx = x;
			int nexty = y+1;
			if (nexty == 9) {
				nexty = 0; 
				nextx++;
			}
			return dfs(board, nextx, nexty);
    	}
    }