C# solution with recursion and backtracking


  • 0
    C
    public void SolveSudoku(char[,] board) {
            if(board.Length==0)
                return;
            Solve(board);
        }
        
        private bool Solve(char[,] board){
            int row=0,col=0;
            
            if(!findunAssignedSpot(board, ref row, ref col))
                return true;
            
            for(char i='1';i<='9';i++){
                if(isSafe(board, row, col, i)){
                    board[row,col]=i;
                    if(Solve(board))
                        return true;
                    board[row,col] = '.';
                }
            }
            return false;
        }
        
        private bool findunAssignedSpot(char[,] board, ref int row, ref int col){
            for(row=0;row<9;row++)
                for(col=0;col<9;col++)
                    if(board[row,col]=='.')
                        return true;
            return false;
        }
        
        private bool isSafe(char[,] board, int row, int col, char  num){
            return !UsedInRow(board,row,num) && !UsedInColumn(board,col,num) && !UsedInBox(board,row,col,num);
        }
        
        private bool UsedInRow(char[,] board, int row, char num){
            for(int i=0;i<9;i++){
                if(board[row,i] == num && board[row,i]!='.')
                    return true;
            }
            return false;
        } 
        
        private bool UsedInColumn(char[,] board, int col, char num){
            for(int i=0;i<9;i++){
                if(board[i,col] == num && board[i,col]!='.')
                    return true;
            }
            return false;
        }
        
        private bool UsedInBox(char[,] board, int row, int col, char num){
            for(int i=0;i<9;i++){
                if(board[(row/3)*3 + i/3, (col/3)*3 + i%3] == num && board[(row/3)*3 +  i/3, (col/3)*3+i%3] != '.')
                    return true;
            }
            return false;
    
    

Log in to reply
 

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