Why do we assume the solution to Sudoku is unique?


  • 0
    L

    I'm confused by the assumption that the solution to Sudoku will always be unique in the problem.

    I wrote some code to compute seemingly correct Sudoku but because it's not the same answer that grader provides it's treated as false.

    For example: for the example in the problem statement:

    my answer is:

    5 3 1 2 7 6 4 9 8

    6 2 3 1 9 5 8 4 7

    1 9 8 3 4 7 5 6 2

    8 1 2 7 6 4 9 5 3

    4 7 9 8 5 3 6 2 1

    7 4 5 9 2 8 3 1 6

    9 6 7 5 3 1 2 8 4

    2 8 6 4 1 9 7 3 5

    3 5 4 6 8 2 1 7 9

    instead of the one the problem is showing.

    I am wondering the rationale behind limiting to just one possible solution.

    Any thoughts?

    My solution goes like this:

        
    	public char[][] board = new char[9][9];		
    	public boolean isSolved = false;
        
        public void solveSudoku(char[][] b) {
            board = b;
            solve(0, 0);
        }
        
    	LinkedList<Character> getPossibilities(int x, int y) {
    		HashSet<Character> set = new HashSet<Character>();
    		for (int i = 0; i < 9; i++) {
    			if (board[i][y] != '.') {
    				set.add(board[i][y]);
    			}
    		}
    		
    		for (int i = 0; i < 9; i++) {
    			if (board[x][i] != '.') {
    				set.add(board[x][i]);
    			}
    		}
    		
    		LinkedList<Character> possibilities = new LinkedList<Character>();
    		
    		for (int i = 1; i <= 9; i++) {
    			if (!set.contains((char)('0' + i))) {
    				possibilities.add((char)('0' + i));
    			}
    		}
    				
    		return possibilities;
    	}
    	
    	public void solve(int x, int y) {
    		if (board[x][y] != '.') {
    			if (x == board.length - 1 && y == board[0].length - 1) {
    				isSolved = true;
    				return;
    			} else {
    				if (x == board.length - 1) {
    					solve(0, y + 1); 
    				} else {
    					solve(x + 1, y);
    				}				
    			}
    		} else {
    						
    			LinkedList<Character> p = getPossibilities(x, y);
    			if (p.size() == 0) {
    				return;
    			} else {			
    				if (x == board.length - 1 && y == board[0].length - 1) {																					
    					board[x][y] = p.poll();					
    					isSolved = true;
    					return;
    				} else {				
    					for (char i : p) {																
    						board[x][y] = i;
    						
    						if (x == board.length - 1) {
    							solve(0, y + 1); 
    						} else {
    							solve(x + 1, y);
    						}												
    						
    						if (isSolved) {
    							return;
    						}
    						
    						board[x][y] = '.';						
    					}				
    				}			
    			}	
    		} 							
    	}
    }```

  • 2

    my answer is:

    5 3 1 2 7 6 4 9 8

    6 2 3 1 9 5 8 4 7

    1 9 8 3 4 7 5 6 2

    8 1 2 7 6 4 9 5 3

    4 7 9 8 5 3 6 2 1

    7 4 5 9 2 8 3 1 6

    9 6 7 5 3 1 2 8 4

    2 8 6 4 1 9 7 3 5

    3 5 4 6 8 2 1 7 9

    That's obviously wrong. For example, the top left block has 1 twice.


Log in to reply
 

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