Salve, sto scrivendo un programma che calcola in modo esaustivo tutte le possibili combinazioni di un orario scolastico usando il BackTracking.

Ho 10 classi scolastiche (mi riferisco alle classi degl studenti e non a quelle di java):
codice:
public enum Classe{ IA, IIA, IIIA, IB, IIB, IIIB, IC, IIC, IIIC, IID };
e ho anche 24 Docenti.
Un Docente è un oggetto con: Nome, Materi, Giorno Libero e una Mappa che contiene le coppie <Classe, Ore in questa classe>.

Il mio orario viene rappresentato in questo modo: Immagine2.jpg
Dove G.L. e F.S. rappresentano le ore in cui non possono essere assegnati i docenti.

Uso un BackTracking Iterativo per riempiere l'orario rappresentato da una matrice di costanti Classe (IA, IIA ecc).
Ogni colonna rappresenta la 1, 2, 3, 4 e 5 ora di una giornata. Nelle righe ci sono i docenti.
Il programma riempie una colonna alla volta quando il docente della riga ha ore nella classe attuale e quando il giorno corrispondente a quella colonna, non è il giorno libero.
Quando raggiunge l'ultima ora di sabato, ripete lo stesso procedimento per la classe successiva.
Questo programma prova tutte le combinazioni.

Il problema in questione ha complessità esponenziale, ma esistono altri programmi che risolvono questo problema in tempi ragionevoli. Il mio problema sembra molto simile al calcolo combinatorio dove la dimensione dell'input è abbastanza alto. Se esiste un algoritmo che risolve problemi combinatori in tempi ragionevoli, potrei adattarlo.

Sapete indicarmi una soluzioni più efficiente? Come posso ridurre il tempo di calcolo?

Questo è il codice della parte del BackTracking:

codice:
    public void trovaCombinazioniOrario(){        
int liv = 0;
        boolean rivedi = false;
        ArrayList<Classe> arrayClasse = new ArrayList<>( Arrays.asList( Classe.values() ) );
        int nClasseAttuale = 0;
        if( arrayClasse.isEmpty() ){ System.err.println("Non c'è nessuna classe da assegnare!"); System.exit(-1); }
        Classe classe = arrayClasse.get(nClasseAttuale);        //Prendo la prima classe
        
        if ( !primaScelta( classe, liv) ){    //Innanzitutto faccio una prima scelta
            System.err.println("Non c'è nemmeno la prima scelta per la classe "+classe);
            return;    
        }//if
        //TODO
        while (liv >= -1){ 
//            System.out.println("La classe attuale è "+classe+ " al livello "+liv);
            System.out.println(this);
            if( solCompleta(liv) ){                    //Se il livello è l'ultimo,
                
                /**Ho sistemato una classe e vedo la successiva*/
                if( arrayClasse.size()-1 > nClasseAttuale ){            //C'è una prossima classe
                    nClasseAttuale++;
                    classe = arrayClasse.get( nClasseAttuale );    //prendo la prossima
                    liv = -1;                    //assegno la prossima classe a partire dal liv -1 (dopo fa l'incremento)
                    rivedi = false;                //devo andare avanti e non rivedere
                    
                } else {                            //Non c'è una prossima classe, era l'ultima
                    filtraEStampa();                //filtra l'orario e lo stampa
                    rivedi = true;                    //provo altre combinazioni
                    liv++;
                }//if lit
                
            }else{
                liv++;                                    //Oppure incremento il livello
                if( !primaScelta( classe, liv) )        //e faccio la prima scelta del livello successivo
                    rivedi= true;                        //se non va bene devo rivedere
            }//else
            
            while( rivedi && liv >= 0){                //finché non va bene
                liv--;                                //torno indietro di livello
                if( liv == -1 ){
                    
                    /**Non ho soluzioni andando avanti e provo a modificare una classe precedente*/
                    if( nClasseAttuale > 0 ){    //C'è una classe precendente e devo riprovare
                        nClasseAttuale--;
                        classe = arrayClasse.get(nClasseAttuale);
                        liv = GIORNI_SETTIMANA * ORE_GIORNO -1;    //riprovo a partire dall'ultimo livello della classe precedente
                
                    } else{                         //Non c'è una classe precedente
                        System.out.println("Ho terminato le combinazioni");
                        return;                //Non c'è nessuna scelta possibile
                    }//if lit
                    
                }//if -1
                
                if( successivaScelta(classe, liv) )    //faccio la scelta successiva
                    rivedi= false;                    //se va bene, non devo più rivedere
            }//while
        }//while
        
    }//assegnaClasse