[C++] Creare array dinamico

[Super Squirrel]

Il fatto è che il programma sul sudoku si basa tutto su una serie di funzioni in cui l'argomento è un array tridimensionale di dimensioni note v[9][9][11]. Il problema è che la funzione che necessita dell'allocazione dinamica per risolvere il sudoku per tentativi sfrutta molte delle suddette funzioni. Quindi per me sarebbe molto comodo trovare un modo per utilizzare le stesse funzioni anche per gli array dinamici tridimensionali.
Interessante cmq quest'ultima soluzione. Il typedef immagino definisca un nuovo tipo, giusto?
Adattando questo metodo alle mie matrici tridimensionali posso continuare ad usare le stesse funzioni? (per esempio nome_funzione(v) ) ?
In caso contrario qualche idea?

EDIT:
purtroppo la classe vector non la so utilizzare e lo stack non so cosa sia.
Per quanto riguarda i dati delle varie mosse, almeno per come funziona il mio programma credo che servano tutti.

[Super Squirrel]

Ho modificato il programma sul sudoku adottando il metodo suggerito da apatriarca e funziona perfettamente.

Il seguente programmino mostra l'utilizzo che ne faccio supponendo di avere funzioni che lavorano su array di dimensioni [2][2][3]. Va bene o potrebbe generare errori?

Codice:

#include <iostream>

void riempi_array(int v[2][2][3])
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                std::cin >> v[i][j][k];
            }
        }
    }
}

void mostra_array(int v[2][2][3])
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                std::cout << v[i][j][k] << " ";
            }
        }
    }
}

typedef int v[2][3];

int main()
{
    v* p[5];
    for(int i = 0; i < 5; i++)
    {
        p[i] = new v[2];
    }
    riempi_array(p[0]);
    mostra_array(p[0]);
    std::cout <<  std::endl << p[0][1][0][2];
    for(int i = 0; i < 5; i++)
    {
        delete [] p[i];
    }
}

Non capisco però perchè se faccio

typedef int v[2][2][3];
v* p;
p = new v; (o p = new v[1])
riempi_matrice(v);

non compila...

[apatriarca]

Se quello è il codice allora hai scritto v al posto di p come argomento di riempi_matrice (che poi si chiama riempi_array nel tuo codice mi sembra).

[Super Squirrel]

quello alla fine del precedente post non era il codice, l'ho scritto così al momento.

per esempio il seguente codice non me lo compila, come mai? credo ci sia qualcosa che mi sfugga su come funzionino i puntatori.

Codice:

#include <iostream>

void riempi_array(int w[2][2][3])
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                std::cin >> w[i][j][k];
            }
        }
    }
}

void mostra_array(int w[2][2][3])
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                std::cout << w[i][j][k] << " ";
            }
        }
    }
}

typedef int v[2][2][3];

int main()
{
    v* p = new v;
    riempi_array(p);
    mostra_array(p);
    std::cout <<  std::endl << p[1][0][2];
    delete [] p;
}


[apatriarca]

Anche se complicato dal fatto di star lavorando con degli array, un primo problema è semplicemente che riempi_array e mostra_array vogliono in input qualcosa di tipo v, ma tu hai un puntatore a v.. C'è poi il problema del new e di come viene realmente interpretato il tuo tipo v. Inoltre delete [] p va usato solo se p è stato costruito con new []..

La soluzione più semplice è quella di usare una struttura/classe:

Codice:

#include <iostream>

struct Esempio {
    int v[2][2][3];
};

void riempi_array(Esempio *e)
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                std::cin >> e->v[i][j][k];
            }
        }
    }
}

void mostra_array(Esempio *e)
{
    for(int i = 0; i < 2; i++)
    {
        for(int j = 0; j < 2; j++)
        {
            for(int k = 0; k < 3; k++)
            {
                std::cout << e->v[i][j][k] << " ";
            }
        }
    }
}

int main()
{
    Esempio *p = new Esempio;
    riempi_array(p);
    mostra_array(p);
    std::cout <<  std::endl << p->v[1][0][2];
    delete p;
}


[Super Squirrel]

purtroppo se non si studia e comprende per bene un argomento non se ne conoscono i limiti e le potenzialità.

quindi onde evitare di commettere con le classi lo stesso errore fatto con gli array dinamici, preferisco lasciar perdere per il momento. La struttura logica del programma sul sudoku è completa, non resta che scrivere il tutto in una forma più elegante ed efficiente. Quando avrò un po' di tempo mi studierò per bene l'allocazione dinamica ,la classe vector e le struct...quindi potrò scegliere la soluzione che meglio si adatta al mio caso.

Grazie cmq a tutti per l'aiuto.

[vict85]

EDIT:
purtroppo la classe vector non la so utilizzare e lo stack non so cosa sia.
Per quanto riguarda i dati delle varie mosse, almeno per come funziona il mio programma credo che servano tutti.

Un std::stack è l'implementazione nella libreria standard di uno stack, che in italiano viene chiamato pila. In sostanza è una struttura dati che implementa una struttura dati di tipo LIFO (last in, first out). Intuitivamente l'idea è che metti degli oggetti uno sull'altro e puoi eliminare solo l'elemento in cima. Internamente non è altro che un std::vector.

Questo è un codice che ti mostra quello che intendevo. Il mettere l'array in un struttura serve per renderlo copiabile. Il codice fa delle modifiche ad una matrice 4x4 e le annulla. Sarebbe ovviamente stato possibile salvare dentro lo stack gli stati intermedi invece che la struttura Command.

Codice:

#include <iostream>
#include <stack>

struct State {
    int dato[4][4];
};

struct Command {
    int i, j, oldVal, newVal;
};

void printMat(State S);

void Esegui(Command &C, State &S, std::stack<Command> &SC);
void Annulla(State &S, std::stack<Command> &SC);

int main()
{
    auto stato = State{ { 0 } }; // inizializza tutta la matrice a 0
    auto SC = std::stack<Command>{};
   
    // alcuni esempi di operazioni.
    std::cout << "Lo stato iniziale e':" << std::endl;
    printMat(stato);
    std::cout << std::endl;
   
    std::cout << "Cambio il valore in (0,0) in 4..." << std::endl;
    Command C = { 0, 0, 0, 4 };
    Esegui( C, stato, SC );
    printMat(stato);
    std::cout << std::endl;
   
    std::cout << "Cambio il valore in (1,0) in -15..." << std::endl;
    C.i = 1;
    C.j = 0;
    C.newVal = -15;
    Esegui( C, stato, SC );
    printMat(stato);
    std::cout << std::endl;
   
    std::cout << "Annullo l'ultima modifica..." << std::endl;
    Annulla(stato, SC );
    printMat(stato);
    std::cout << std::endl;
   
    std::cout << "Cambio il valore in (1,1) in 2..." << std::endl;
    C.i = 1;
    C.j = 1;
    C.newVal = 2;
    Esegui( C, stato, SC );
    printMat(stato);
    std::cout << std::endl;
   
    std::cout << "Annullo le ultime due modifiche..." << std::endl;
    Annulla(stato, SC );
    Annulla(stato, SC );
    printMat(stato);
    std::cout << std::endl;
   
    std::cout << "Cambio il valore in (2,3) in 200..." << std::endl;
    C.i = 2;
    C.j = 3;
    C.newVal = 200;
    Esegui( C, stato, SC );
    printMat(stato);
    std::cout << std::endl;
}


void printMat(State const S)
{
    for(int i = 0; i != 4; ++i)
    {
        for(int j = 0; j != 4; ++j)
        {
            std::cout << S.dato[i][j] << " ";
        }
        std::cout << std::endl;
    }
}


void Esegui(Command &C, State &S, std::stack<Command> &SC)
{
    if( (C.i > 3) || (C.i < 0) || (C.j > 3) || (C.j < 0) )
        return;
   
    C.oldVal = S.dato[C.i][C.j];
    S.dato[C.i][C.j] = C.newVal;
    SC.push(C);
}

void Annulla(State &S, std::stack<Command> &SC)
{
    if(SC.empty())
        return;
   
    auto const C = SC.top();
   
    S.dato[C.i][C.j] = C.oldVal;
    SC.pop();
}

[Super Squirrel]

Dato un'occhiata al codice, ovviamente non ho capito tutto, ma mi sembra che anche lo stack sia uno strumento molto potente. Lo aggiungo alla lista degli argomenti da approfondire in futuro.

Alla fine cmq ho risolto utilizzando gli array statici.
Ho creato un array w[81][9][9][11] dove 81 sono il numero massimo di tentativi da considerare contemporaneamente (in realtà credo siano molti meno, è cmq un punto su cui dovrò ragionare meglio).
quindi data la generica funzione void mostra_griglia(int v[9][9][11]) e detto int b un contatore faccio mostra_griglia(w[b]).

[vict85]

Che metodo stai usando per risolvere il sudoku? Mi sembra fin troppa memoria per il problema.

Riguardo all'81 direi che può essere ridotto in maniera abbastanza ovvia. Infatti gli elementi del sudoku fissati sin dall'inizio non sono da ritenersi tentativi e l'ultimo elemento non richiede necessariamente di essere scritto. Insomma a quel punto sai che è la vittoria o devi eliminare l'ultima mossa.

Si congettura che il numero minimo di indizi per avere un sudoku con soluzione minima sia \(\displaystyle 17 \), pertanto potresti sostituire \(\displaystyle 81 \) con \(\displaystyle 81-1-17+1 = 64 \) o con \(\displaystyle 65 \) se vuoi avere spazio anche per l'ultima mossa. Con \(\displaystyle 70 \) puoi anche considerare sudoku con più soluzioni. Usando la memoria dinamica potresti calcolare il numero in base al numero di indizi iniziali.

Non ho capito invece perché hai bisogno di \(\displaystyle 9\times 9\times 11 \) interi per rappresentare lo stato attuale.





P.S.: Riguardo alla pila nota che di fatto tu ne hai implementata una (usando al di sotto un array statico).

[Super Squirrel]

Fissata la base 9x9 della griglia, per ogni casella al primo "piano" ci sono i numeri dello schema (0 per le caselle vuote), dal secondo al decimo vanno in ordine tutti i possibili candidati e all'undicesimo il numero di candidati( quest'ultimo dato ovviamente può essere ricavato dal precedente, ma ritengo che sia meglio occupare poca memoria in più che calcolarlo volta per volta).

Per quanto riguarda il programma esso applica varie strategie per risolvere il sudoku e se alla fine non ci riesce avvisa e lo risolve per tentativi. Per ora ho implementato strategie standard che permettono di inserire un numero (tipo una casella in cui può andare un solo numero (chiamiamo tale strategia casella_1) o un numero che può andare in una sola casella di una riga/colonna/riquadro) o di ridurre i candidati (tipo n caselle di una riga/colonna/riquadro in cui possono andare solo n numeri, o n numeri che possono andare solo in n caselle di una riga/colonna/riquadro). Già ora molti sudoku li risolve senza tentativi, ma ho intenzione in futuro di implementare anche strategie più avanzate per i sudoku più complessi.

Per quanto riguarda il numero di tentativi credo siano molto meno di 81 perchè nella risoluzione per tentativi sfrutto anche la funzione casella_1. Cmq facendo mostrare il valore massimo assunto dal contatore di tentativi viene che per uno schema vuoto (che dovrebbe essere la situazione più svantaggiosa?) esso è pari a 45 mentre immettendo il sudoku più difficile del mondo (e disattivando tutte le strategie) è pari solo a 10.