My JAVA solution only 232 ms!


  • -1
    Q
     public class Solution {
    	private static final int[] mask = new int[]{0,1,2,4,8,16,32,64,128,256};
    	public void solveSudoku(char[][] board) {
    		List<byte[]> avPoints = new ArrayList<byte[]>();
    		for (byte i=0;i<board.length;i++){
    			for (byte j=0;j<board.length;j++){				
    				if (board[i][j] == '.'){
    					avPoints.add(new byte[]{i,j});
    				}
    			}
    		}
    		solve(board, avPoints);
        }
    	private boolean solve(char[][] board, List<byte[]> points){
    		if (points.isEmpty()){
    			return true;
    		}
    		byte[] point = points.remove(points.size()-1); //remove at the end for speed
    		int notAvailable = getNotAvailable(point, board);
    		for (int i=1;i<=9;i++){
    			if ((notAvailable&mask[i]) == 0){//number is available
    				board[point[0]][point[1]] = (char)('0' + i);
    				if (solve(board, points)){
    					return true; //unwind
    				}
    				board[point[0]][point[1]] = '.'; //backtrack
    			}
    		}
    		points.add(point); //backtrack
    		return false;
    	} 
    	private int getNotAvailable(byte[] point, char[][] board){
    		int result = 0;
    		int x1 = 3*(point[0]/3);
    		int y1 = 3*(point[1]/3);
    		for (int m=0;m<9;m++){
    			if (board[point[0]][m]!='.'){
    				result|=mask[board[point[0]][m]-'0'];
    			}
    			if (board[m][point[1]]!='.'){
    				result|=mask[board[m][point[1]]-'0'];
    			}
    			int xBox=x1 + m/3;
    			int yBox=y1 + m%3;
    			if(board[xBox][yBox]!='.'){
    				result|=mask[board[xBox][yBox]-'0'];
    			}
    		}
    		return result;
    	}

Log in to reply
 

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