What is the problem with my code [JAVA] ?


  • 0
    A

    I use a 3D array to store the candidates in every empty cell. And a list is used to store the position of the empty cells. Function isValidSudoku() is used to check if the current position is suitable for a particular character. I tend to use backtracking to solve this problem in helper() function. But it does not work. I cannot figure out what's wrong in my solution. Can anyone help address this problem?
    When I input a board like this :

    . . . . . 7 . . 9 
    . 4 . . 8 1 2 . . 
    . . . 9 . . 1 . . 
    . . 5 3 . . . 7 2 
    2 9 3 . . . . . 5 
    . . . . . 5 3 . . 
    8 . . . 2 3 . . . 
    7 . . . 5 . . 4 . 
    5 3 1 . 7 . . . .
    

    Then I got a output only solve part of the problem:

     1 2 6 4 3 7 5 8 9 
    9 4 7 5 8 1 2 6 . 
    . 5 8 9 6 2 1 3 7 
    4 1 5 3 9 6 8 7 2 
    2 9 3 1 4 8 6 . 5 
    6 8 . 7 . 5 3 9 4 
    8 6 9 . 2 3 7 5 1 
    7 . 2 6 5 9 . 4 8 
    5 3 1 8 7 4 9 2 6 
    

    Code:

    public class Solution {
    static Character[] Nums = {'1','2','3','4','5','6','7','8','9'};
    public static Character[][][] candidates= new Character[9][9][9]; 
    public static List<int[]> list = new ArrayList<int[]>();
    public static void solveSudoku(char[][] board) {
        for(int i=0; i<9; i++)
        	for(int j=0; j<9; j++){
        		if(board[i][j]=='.'){
        			list.add(new int[]{i,j});
        			for(int k=0;k<9;k++){
        				if(isValidSudoku(board,i,j,Nums[k]))
        					candidates[i][j][k] = Nums[k];
        			}
        		}
        }
        helper(board,0);
    }
    public static void helper(char[][] board, int index) {
    	for(int i=index; i<list.size();i++){
    		int[] cur = list.get(i);
    		for(int k=0;k<9;k++){
    			if(candidates[cur[0]][cur[1]][k]!=null&&isValidSudoku(board,cur[0],cur[1],candidates[cur[0]][cur[1]][k])){
    				board[cur[0]][cur[1]] = candidates[cur[0]][cur[1]][k];
    				if(i==list.size()-1) return;
    				else
    					helper(board,i+1);
    			}
    		}
    	}
    }
    public static boolean isValidSudoku(char[][] board, int row, int column, char target) {
        for(int i=0;i<9;i++){
        	if(board[row][i]==target) return false;
        	if(board[i][column]==target) return false;
        	if(board[(row/3)*3+i/3][(column/3)*3+i%3]==target) return false;
        }
        return true;
    }
    

    }


Log in to reply
 

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