My Clean Java Solution by Pre-filtering the candidates


  • 1
    A
    public class Solution {
    public void solveSudoku(char[][] board) 
    {
        ArrayList<int[]> moves = new ArrayList<int[]>();
        for(int i = 0; i < board.length; i++)
        {
            for(int j = 0; j < board[0].length; j++)
            {
                if(board[i][j] == '.')
                {
                    int[] r = {i,j};
                    moves.add(r);
                }
            }
        }
        finder(moves, board, 0);
    }
    public boolean finder(ArrayList<int[]> moves, char[][] board, int length)
    {
        if(length >= moves.size())
        {
            return true;
        }
        int[] pos = moves.get(length);
        boolean[] filles = new boolean[9];
        for(int i = 0; i < filles.length; i++)
        {
            filles[i] = true;
        }
        //find possible moves
        for(int i = 0; i < board.length; i++)
        {
            if(board[i][pos[1]] != '.')
            {
                int v = board[i][pos[1]] - '0';
                filles[v-1] = false;
            }
        }
        for(int i = 0; i < board[pos[0]].length; i++)
        {
            if(board[pos[0]][i] != '.')
            {
                int v = board[pos[0]][i] - '0';
                filles[v-1] = false;
            }
        }
        for(int i = 0 + (pos[0]/3) *3; i <= 2 + (pos[0]/3) *3; i++)
        {
             for(int j = 0 + (pos[1]/3) *3; j <= 2 + (pos[1]/3) *3; j++)
             {
                 if(board[i][j] != '.')
                 {
                     int v = board[i][j] - '0';
                     filles[v-1] = false;
                 }
             }
        }
        for(int i = 0; i < filles.length; i++)
        {
            if(filles[i])
            {
               board[pos[0]][pos[1]] = (char)((i+1)+'0');
               boolean res = finder(moves, board,length+1);
               if(res)
                return true;
               board[pos[0]][pos[1]] = '.';
            }
        }
        return false;
    }
    

    }


Log in to reply
 

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