Clean Java Solution 90 %+ Runtime


  • 0
    A

    My solution uses three arrays to keep track of which numbers had been taken and so are available for use:

    public class Solution {
    
    	public void solveSudoku(char[][] board) {
    		final int n = board.length;
    		List<Point> emptyCells = new ArrayList<>();
    		boolean[][] row = new boolean[n][n];
    		boolean[][] col = new boolean[n][n];
    		boolean[][][] box = new boolean[n / 3][n / 3][n];
    
    		for (int i = 0; i < n; i++) {
    			for (int j = 0; j < n; j++) {
    				char c = board[i][j];
    				if (c == '.') {
    					emptyCells.add(new Point(i, j));
    				} else {
    					int num = Character.getNumericValue(c) - 1;
    					row[i][num] = true;
    					col[j][num] = true;
    					box[i / 3][j / 3][num] = true;
    				}
    			}
    		}
    		
    		fillEmptyCells(board, emptyCells, 0, row, col, box);
    	}
    	
    	private boolean fillEmptyCells(char[][] board, List<Point> emptyCells, int current,
    			boolean[][] row, boolean[][] col, boolean[][][] box) {
    		if (current == emptyCells.size()) {
    			return true;
    		}
    		
    		Point p = emptyCells.get(current);
    		for (int i = 0; i < 9; i++) {
    			if (!row[p.x][i] && !col[p.y][i] && !box[p.x / 3][p.y / 3][i]) {
    				board[p.x][p.y] = Character.forDigit(i + 1, 10);
    				row[p.x][i] = true;
    				col[p.y][i] = true;
    				box[p.x / 3][p.y / 3][i] = true;
    				if (fillEmptyCells(board, emptyCells, current + 1, row, col, box)) {
    					return true;
    				}
    				board[p.x][p.y] = '.';
    				row[p.x][i] = false;
    				col[p.y][i] = false;
    				box[p.x / 3][p.y / 3][i] = false;
    			}
    		}
    		
    		return false;
    	}
    	
    }
    

Log in to reply
 

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