Domanda Programma che risolve sudoku

[alessina02]

Salve, avrei bisogno di aiuto con questo esercizio in C o C++
Un sottoquadrato di un quadrato latino L `e una sottomatrice di L (che non necessariamente consiste di entrate
adiacenti) che `e essa stessa un quadrato latino.
Scrivere un programma che riceva in input un quadrato latino L come nell’Esercizio 1 (ammettendo che la sequenza
introdotta sia corretta) ed un intero k fra 0 e n^2 −1, e restituisca la sequenza dei sottoquadrati che hanno in comune
solo l’entrata k-ma del quadrato (ottenta contando le entrate riga per riga). I sottoquadrati trovati devono essere
propri, vale a dire diversi da L, e minimali, cio`e non devono contenere altri sottoquadrati nella lista.

ESEMPIO:
0123
3210
2301
1032
è un quadrato latino. Ammesso di inserire k=10 (quindi lo 0 della terza riga) il programma dovrebbe ritornare
0 2 8 10 - 6 7 10 11 - 9 10 13 14 (che sono le coordinate per riga)


Adesso io ho la prima parte di programma in cui inserisco il quadrato, il problema è che vorrei un modo per individuare k nella matrice. Ho provato con le classi di equivalenza, ma non veniva, quindi avevo pensato di caricare tutta la matrice in un vettore ak e il numero che mi serve sarà ak[k]. Il problema è che a me servono sia la riga sia la colonna di k perchè ovviamente il quadrato parte praticamente da lì.

#include <stdio.h>
#include <stdlib.h>

int main () {
    int n, i, j, h=0, k;
    scanf ("%d", &n);
    if (n<3) printf ("NO");
    int a[n][n];
    for (i=0; i<n; i++) {for (j=0; j<n; j++) {scanf ("%d", &a[i][j]);
    if (a[i][j]<0||a[i][j]>20) {printf ("NO"); return 0;}}}

        
    scanf("%d", &k);
    if (k<0||k>(n*n)-1) {printf ("NO"); return 0;}
        int ak[n*n];
        for (i=0; i<n; i++) {for (j=0; j<n; j++){
            ak[h]=a[i][j]; h++;}}
        return 0;}

 

[Super Squirrel]

Ciao, gli indici relativi a riga e colonna dell'elemento scelto possono essere rispettivamente ricavati come k/n e k%n.

Qualche osservazione:
- un quadrato latino non è propriamente un sudoku, e soprattutto più che "risolvere" qui si tratta di "ricercare" delle sottomatrici;
- indenta il codice al fine di renderlo più leggibile;
- inizialmente lascia stare l'input e definisci n, k e la matrice direttamente nel codice, così potrai soffermarti sull'algoritmo risolutivo;
- andando al cuore del programma, come avresti intenzione di implementare l'algoritmo di ricerca dei "sottoquadrati latini minimali"?

 

[alessina02]

Ciao, gli indici relativi a riga e colonna dell'elemento scelto possono essere rispettivamente ricavati come k/n e k%n.

Qualche osservazione:
- un quadrato latino non è propriamente un sudoku, e soprattutto più che "risolvere" qui si tratta di "ricercare" delle sottomatrici;
- indenta il codice al fine di renderlo più leggibile;
- inizialmente lascia stare l'input e definisci n, k e la matrice direttamente nel codice, così potrai soffermarti sull'algoritmo risolutivo;
- andando al cuore del programma, come avresti intenzione di implementare l'algoritmo di ricerca dei "sottoquadrati latini minimali

I minimali sono da 2*2 quindi pensavo di individuare k nel quadrato, prendere un altro numero (h1) dalla riga di k, trovare h1 nella colonna di k (h2) e poi trovare il numero uguale a k che abbia in comune la colonna di h1 e la riga di h2.
Non ho ancora bene idea di come salvarli in ordine, ma il piano generale è più o meno questo

Messaggio unito automaticamente: 4 Dicembre 2023

Adesso ho il problema di come ordinarli. Avevo pensato di caricare gli indici riga trovati in una matrice b di 4 colonne. Poi, ordinare il vettore di dim 4 in ordine crescente e successivamente confrontare i b[][0] in modo da scambiare le righe per ordinarle. infine stampare la matrice b per righe. Sto avendo però qualche problema di implementazione:

 int   n=4, p, q=0;
    int a[4][4]={0,1,2,3,3,2,1,0,2,3,0,1,1,0,3,2};
    k=10;
    
    int K=a[k/n][k%n];
    int b[q][p]; //q e p sono inizializzati nella parte iniziale del programma
    i=k/n;
    for (j=0; j<n; j++)
        {if (j!=(k%n))
            {h1=a[i][j]; h2=i*n+j; m1=trova(K,j,n, a); m2= m1*n+j; l1=trova(h1,k%n, n, a); l2=n*l1+(k%n);
                b[q][4]=ordina(h2,m2,l2,k); q++; }}

la funzione "ordina" mi sta dando parecchi problemi, volevo strutturarla come una specie di selection sort ma non funziona e non saprei come mettere in ordine 4 numeri che non sono inseriti in un vettore.
Inoltre, avrei dei problemi con l'inizializzazione di b. Perchè il mio q iniziale è 0, quindi b ha una sola riga, ma q cresce man mano che trovo altri quadrati, quindi anche la matrice dovrebbe crescere, ma questo ovviamente dà errore.

 

[Super Squirrel]

Sinceramente non ho capito bene l'algoritmo che hai in mente, potresti spiegarti meglio, magari con un esempio?

Poi ragionando si ricava che un quadrato latino di ordine n non può contenere sottoquadrati latini di ordine superiore a n\2 (dove \ indica la divisione intera). Quindi la ricerca dei sottoquadrati latini si riduce all'intervallo [2;n\2].

Infine per una questione di leggibilità ti consiglio di indentare il codice e di inserire una sola istruzione per riga.

Messaggio unito automaticamente: 5 Dicembre 2023

In ogni caso non mi sembra proprio semplicissimo come esercizio... tieni conto che che per n grandi dovrai anche ricercare sottoquadrati latini di ordine 3,4,5,... e così via.
Ora non so se mi sfugge qualcosa dal punto di vista "logico-matematico", ma penso che non ci si possa sottrarre dall'andare a controllare le varie sottomatrici costituite dalle diverse combinazioni di righe e colonne.

 

[alessina02]

In ogni caso non mi sembra proprio semplicissimo come esercizio... tieni conto che che per n grandi dovrai anche ricercare sottoquadrati latini di ordine 3,4,5,... e così via.

No i sottoquadrati devono essere minimali quindi non devono contenere altri sottoquadrati. Dunque possono essere solo 2x2 perchè un sottoquadrato 3x3 avrebbe in sè anche un sottoquadrato 2x2.

Sinceramente non ho capito bene l'algoritmo che hai in mente, potresti spiegarti meglio, magari con un esempio?

immagina di avere un quadrato latino così strutturato
0123
3210
2301
1032
e k=10 (quindi lo 0 della terza riga)
i sottoquadrati latini che contengono lo 0 della terza riga sono
0123
3210
2301
1032

immagina che lo 0 grigio sia di tutti e tre i colori. Quindi il punto è che un sottoquarato latino in questo caso deve essere formato da due zeri e due numeri uguali tra 1,2 e 3 che siano uno sulla stessa riga e uno sulla stessa colonna dello zero iniziale. Per cui il mio programma inizia trovando la riga e la colonna di 0 (K), poi cerca h (in questo caso 2) che è il primo numero della riga di 0 che non sia zero. A questo punto, cerca lo 0 nella colonna di h e h nella colonna dello 0. E ha trovato il primo sottoquadrato latino. Poi trasforma le coordinate di matrice in coordinate di riga. Fa questa operazione per ogni colonna e trova quindi tre sottoquadrati. Il mio problema è mettere prima questi 4 numeri in ordine crescente e poi le stringhe di 4 numeri in ordine crescente in base al primo numero

 

[Super Squirrel]

No i sottoquadrati devono essere minimali quindi non devono contenere altri sottoquadrati. Dunque possono essere solo 2x2 perchè un sottoquadrato 3x3 avrebbe in sè anche un sottoquadrato 2x2.

Il seguente schema non smentisce la tua affermazione?

0 1 2 3 4 5 6
2 0 1 4 5 6 3
1 2 0 5 6 3 4
3 6 4 0 1 2 5
6 5 3 1 2 4 0
5 4 6 2 3 0 1
4 3 5 6 0 1 2


O ancora, supponendo di avere il seguente quadrato latino 2x2

0 1
1 0

come fai, aggiungendo anche il numero "2", a trasformalo in un quadrato latino 3x3?

 

[alessina02]

0 1 2 3 4 5 6
2 0 1 4 5 6 3
1 2 0 5 6 3 4
3 6 4 0 1 2 5
6 5 3 1 2 4 0
5 4 6 2 3 0 1
4 3 5 6 0 1 2

io credo che la roba in verde sia comunque un sottoquadrato

 

[Super Squirrel]

io credo che la roba in verde sia comunque un sottoquadrato

Se hai la possibilità chiedi a qualcuno, ma io direi proprio di no
Comunque, se ho ragione io, valgono le osservazioni fatte in precedenza.

Inoltre, dal momento che mi sembrava interessante come esercizio, l'ho provato a svolgere, e il programma sembra funzionare; quindi se incontri qualche difficoltà con l'ideazione dell'algoritmo o con l'implementazione del codice posso provare ad aiutarti.

 

[alessina02]

Se hai la possibilità chiedi a qualcuno, ma io direi proprio di no
Comunque, se ho ragione io, valgono le osservazioni fatte in precedenza.

Inoltre, dal momento che mi sembrava interessante come esercizio, l'ho provato a svolgere, e il programma sembra funzionare; quindi se incontri qualche difficoltà con l'ideazione dell'algoritmo o con l'implementazione del codice posso provare ad aiutarti.

Sono bloccata al punto in cui ordino i quattro numeri trovati in ordine crescente. Non riesco a implementare niente che ritorni un vettore ordinato. Tutti gli algoritmi a cui ho pensato richiedono un vettore di partenza, non quattro interi "casuali", se hai un hint da darmi sono tutt'orecchie

 

[Super Squirrel]

io credo che la roba in verde sia comunque un sottoquadrato

Se hai la possibilità chiedi a qualcuno, ma io direi proprio di no

Qual è il verdetto su questa questione?

In ogni caso, partendo dal presupposto che un sottoquadrato latino minimale possa avere anche dimensioni maggiori di 2x2, imposterei l'algoritmo nel seguente modo:
- individuato l'elemento k-esimo nella matrice completa di ordine N, prendo nota del valore in esso contenuto (chiamiamolo X);
- dal momento che gli eventuali sottoquadrati latini nxn conterranno sicuramente n volte il valore X, per l'individuazione delle sottomatrici da testare vado ad individuare tutte le N occorrenze di X nella matrice (infatti n occorrenze di X nella matrice completa individuano una sottomatrice nxn e quindi un potenziale sottoquadrato latino);
- a questo punto vado a testare tutte le sottomatrici nxn individuate dalle varie combinazioni delle occorrenze di X (per la precisione si tratta di combinazioni semplici di N elementi presi n alla volta). Ovviamente dalla traccia dell'esercizio risulta ovvio che ogni combinazione dovrà contenere l'occorrenza di X costituita dall'elemento k-esimo;
- n, come detto in un precedente post, varierà tra 2 (che è la dimensione minima di una sottomatrice) a N\2 (con la logica si deduce che un quadrato latino non può contenere sottoquadrati latini di ordine superiore a N\2). Per esempio per una matrice 9x9 si testeranno nell'ordine tutte le sottomatrici 2x2, 3x3 e 4x4 (dal momento che 9\2=4).

Se qualcosa non ti convince dell'algoritmo o hai dubbi sull'implementazione, fammi sapere.

 

[alessina02]

Qual è il verdetto su questa questione?

In ogni caso, partendo dal presupposto che un sottoquadrato latino minimale possa avere anche dimensioni maggiori di 2x2, imposterei l'algoritmo nel seguente modo:
- individuato l'elemento k-esimo nella matrice completa di ordine N, prendo nota del valore in esso contenuto (chiamiamolo X);
- dal momento che gli eventuali sottoquadrati latini nxn conterranno sicuramente n volte il valore X, per l'individuazione delle sottomatrici da testare vado ad individuare tutte le N occorrenze di X nella matrice (infatti n occorrenze di X nella matrice completa individuano una sottomatrice nxn e quindi un potenziale sottoquadrato latino);
- a questo punto vado a testare tutte le sottomatrici nxn individuate dalle varie combinazioni delle occorrenze di X (per la precisione si tratta di combinazioni semplici di N elementi presi n alla volta). Ovviamente dalla traccia dell'esercizio risulta ovvio che ogni combinazione dovrà contenere l'occorrenza di X costituita dall'elemento k-esimo;
- n, come detto in un precedente post, varierà tra 2 (che è la dimensione minima di una sottomatrice) a N\2 (con la logica si deduce che un quadrato latino non può contenere sottoquadrati latini di ordine superiore a N\2). Per esempio per una matrice 9x9 si testeranno nell'ordine tutte le sottomatrici 2x2, 3x3 e 4x4 (dal momento che 9\2=4).

Se qualcosa non ti convince dell'algoritmo o hai dubbi sull'implementazione, fammi sapere.

Credo che l'algoritmo fili ma comunque non è utile ai fini dell'ordinamento

 

[Super Squirrel]

L'ordinamento a cosa ti serve di preciso? Solo per ordinare le soluzioni?
In ogni caso se non posti il codice completo che hai scritto finora, diventa difficile aiutarti.

Infine non ho capito come intendi cercare gli eventuali sottoquadrati 3x3, 4x4, 5x5, ...
Come ti ho mostrato qui, non è detto che i sottoqudrati latini minimali debbano essere per forza 2x2.

 

[alessina02]

Allora ho riscritto tutto per adattarlo anche a sottoquadrati più grandi. Solo che per comodità ho implementato il codice come se k fosse sempre 0 e adesso che sto cercando di cambiare k non funziona

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <math.h>

#define NMAX 100

void cercaSottoquadrati(int n, int A[NMAX][NMAX], int k);
bool isLatin(int n, int A[NMAX][NMAX]);

int main() {
   int n;
    printf("inserisci n: ");
    scanf("%d", &n);

    int A[NMAX][NMAX];
    printf("inserisci elementi matrice:\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &A[i][j]);
        }
    }
    
       int k;
    printf("inserisci k: ");
    scanf("%d", &k);


    cercaSottoquadrati(n, A, k);

    return 0;
}

bool isLatin(int n, int A[NMAX][NMAX]) {
    for (int i = 0; i < n; i++) {
        for (int j = 1; j < n; j++) {
            for (int h = 0; h <= n - j - 1; h++) {
                if (A[i][j - 1] == A[i][j + h]) {
                    return false;
                }
            }
        }
    }

    for (int j = 0; j < n; j++) {
        for (int i = 1; i < n; i++) {
            for (int h = 0; h <= n - i - 1; h++) {
                if (A[i - 1][j] == A[i + h][j]) {
                    return false;
                }
            }
        }
    }

    return true;
}




void cercaSottoquadrati(int n, int A[NMAX][NMAX], int k) {
    int Markers[NMAX][NMAX];
    int mark = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            Markers[i][j] = mark;
        }
    }

    int trovato = 0;
    int size = 2;
    int sizeMax = n / 2;

    while (size <= sizeMax) {
        int colonnaCurr = 1;

        while (colonnaCurr < n) {
            mark++;
            Markers[k/2][k%n] = mark;
            

            int rigaCurr = 0;
            Markers[rigaCurr][colonnaCurr] = mark;

            while (A[rigaCurr][colonnaCurr] != A[k/2][k%n]) {
                rigaCurr++;
            }

            Markers[rigaCurr][colonnaCurr] = mark;
            Markers[rigaCurr][k%n] = mark;

            int S[NMAX][NMAX];
            int rigaS = 0;

            for (int i = 0; i < n; i++) {
                int colonnaS =0;

                for (int j = 0; j < n; j++) {
                    if (Markers[i][j] == mark) {
                        S[rigaS][colonnaS] = A[i][j];
                        colonnaS++;
                    }
                }

                if (colonnaS > 0) {
                    rigaS++;
                }
            }

            if (isLatin(size, S)) {
                for (int i = 0; i < n; i++) {
                    for (int j = 0; j < n; j++) {
                        if (Markers[i][j] == mark) {
                            printf("%d ", n * i + j);
                        }
                    }
                }

                trovato = 1;
            }

            colonnaCurr++;

            if (colonnaCurr < n) {
                printf("- ");
            }
        }

        size++;
    }

    if (trovato == 0) {
        printf("NO");
    }
}

Il codice "funzionante" che però non fa quello che mi serve ha semplicemente degli zeri dove c'è k/2 o k%n

 

[Super Squirrel]

La funzione isLatin() è sicuramente sbagliata, basta infatti osservare il seguente output:

inserisci n: 4
inserisci elementi matrice:
0
1
2
3
1
2
3
0
2
3
0
1
3
0
1
2
inserisci k: 0
0 1 12 13 - 0 2 8 10 - 0 3 4 7
Process returned 0 (0x0)   execution time : 20.568 s
Press any key to continue.

Se invece utilizzo la seguente versione (dove praticamente, assumendo che la matrice iniziale sia un quadrato latino e contenga valori compresi nell'intervallo [0;NMAX*NMAX-1], e utilizzando una sorta di tabella hash, vado a verificare che A non contenga più di n valori diversi):

bool isLatin(int n, int A[NMAX][NMAX])
{
    int cont = 0;
    int v[NMAX * NMAX] = {0};
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(v[A[i][j]]++ == 0 && ++cont > n)
            {
                return false;
            }
        }
    }
    return true;
}

ottengo l'output corretto:

inserisci n: 4
inserisci elementi matrice:
0
1
2
3
1
2
3
0
2
3
0
1
3
0
1
2
inserisci k: 0
- 0 2 8 10 -
Process returned 0 (0x0)   execution time : 21.123 s
Press any key to continue.

Allora ho riscritto tutto per adattarlo anche a sottoquadrati più grandi.

Direi proprio di no, infatti nella funzione cercaSottoquadrati() ad ogni iterazione vengono modificati solo 4 elementi della matrice Markers, il che significa che le variabili rigaS e colonnaS non assumeranno mai valori superiori a 2. In pratica a prescindere dal valore assunto dalla variabile size, gli unici elementi della matrice S ad essere modificati saranno quelli di indici (0,0), (0,1), (1,0) e (1,1).

Detto ciò, ribadisco quanto detto nei precedenti post, se poi riesci a trovare una soluzione diversa fammi sapere.
In ogni caso prima di buttarti a capofitto sul codice ti consiglio di riflettere bene sull'algoritmo complessivo che ti stai accingendo ad implementare, altrimenti perdi tempo per poi ritrovarti in un vicolo cieco.