Esercizio Backtracking[Algoritmi ricorsivi]

[GabrSatu]

Salve , ho dei problemi con un esercizio sul backtracking. Il testo è il seguente:
Dare lo pseudocodice di un algoritmo che preso in input un intero n , stampa tutte le matrici n x n con valori in {a,b} t.c in ogni riga e in ogni colonna le a precedono le b che precedono le c. Ecco un esempio:

aa aa aa ab ab bb aa aa ac cc bb bb bc bc ab ab ac
aa ab bb ab bb bb ac cc ac cc bc cc bc cc bc cc bc

Il tempo d'esecuzione deve essere O(n^2 * S(n)).

public class EsercizioNovBT {
    public static void main(String[] args) {
        int n=2 , i , j;
        char[][] m = new char [n][n];
        /* array di booleani che indicano se esiste una b o una c nella riga/colonna i/j ad esempio:
        isBR[i] è true se è stata messa una b nella riga i , isBC[j] è true se è stata messa una b nella colonna j ,stesso    discorso per gli altri array*/
        boolean[] isBR = new boolean [n];
        boolean[] isBC = new boolean [n];
        boolean[] isCR = new boolean [n];
        boolean[] isCC = new boolean [n];
       /* inizializzazione dei vettori e della matrice */
        for(i=0;i<n;i++)
            isBR[i]=false;
        for(i=0;i<n;i++)
            isBC[i]=false;
        for(i=0;i<n;i++)
            isCR[i]=false;
        for(i=0;i<n;i++)
            isCC[i]=false;
        for (i=0 ; i<n ; i++)
            for(j=0 ; j<n ;j++)
                m[i][j]='d';
        i=0;j=0;
        scriviSuM(m,isBR,isBC,isCR,isCR,i,j,n);



    }



    static void scriviSuM(char[][]M , boolean[] isRB,boolean[] isCB,boolean[] isRC,boolean[] isCC,int i, int j , int n)
    {
        if(i==n)
        {
            for (int r=0 ; r<n ; r++)
            {
                for(int c=0 ; c<n ;c++)
                {
                    System.out.print(M[r][c]);
                }
                System.out.print("\n");
            }
            System.out.println();
        }
        else
        {
            if(j==n)
            {
                j=0;
                scriviSuM(M,isRB,isCB,isRC,isCC,i+1,j,n);
            }
            else
            {

                    if (! (isRC[i]) && !(isCC[j])) // se non ci sono delle c
                    {
                        if( ! (isRB[i]) && !(isCB[j]) )  // se non ci sono già delle b e delle c allora puoi prendere a
                        {
                            M[i][j]='a';
                            scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
                        }

                        isRB[i]=isCB[j]=true;
                        M[i][j]='b'; // se non ci sono  c posso comunque prendere delle b
                        scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);
                        isRB[i]=isCB[j]=false;
                    }
                    isRC[i]=isCC[j]=true;
                    M[i][j]='c'; // posso sempre prendere c
                    scriviSuM(M,isRB,isCB,isRC,isCC,i,j+1,n);

            }


        }
    }
}

l'output del mio algoritmo è :
aa
aa

aa
ab

aa
ac

aa
bc

aa
cc

ab
cc

ac
cc

bc
cc

cc
cc

Il problema è che non stampa tutte le matrici , sto tagliando troppo lo spazio di ricerca...qualcuno può aiutarmi ?? grazie.

[GabrSatu]

up

[Gogi22]

Cosa stai usando per sviluppare? Un IDE? Comunque se sei agli inizi ti consiglio di fare queste operazioni a mano, lasciando perdere gli IDE, in modo da aver idea di cosa l'IDE faccia al posto tuo e prendere maggiore confdenza con gli strumenti base




_________________
Prep4sure ITIL Foundation