[c++] tecnica backtrackig da applicare (algoritmi)

[effe_89]

il testo del progetto è questo (link) :
http://uva.onlinejudge.org/index.php...em&problem=323

Questo è quello ke ho fatto io!.. ora mi manca solo la tecnica del backtracking
ke nn so come si faccia..perchè in questo modo appena mi da un pezzo io l ho metto
però se nn li mette bene i pezzi magari da ke nn è soluzione..quindi deve tornare indietro
e mettere i pezzi in modo diverso!...

#include <iostream>
using namespace std;
const int d=5;
int board[d][d]={0};
struct pezzo
{
int r;
int c;
int M[4][4];
};
pezzo p[5];
void inizializzaPezzo(int nPezzo)
{
for(int i=0;i<p[nPezzo].r;i++)
{
for(int j=0;j<p[nPezzo].c;j++)
{
p[nPezzo].M[i][j]=0;
}
}
}
void formaPezzo(int nPezzo)
{
int x,y,n;
cout<<"Inserisci dimensione pezzo:"<<endl;
cin>>x;
cin>>y;
p[nPezzo].r=x;
p[nPezzo].c=y;
for(int i=0;i<p[nPezzo].r;i++)
{
for(int j=0;j<p[nPezzo].c;j++)
{
cin>>n;
p[nPezzo].M[i][j]=n;
}
}
}
void stampaPezzo(int nPezzo)
{
for(int i=0;i<p[nPezzo].r;i++)
{
for(int j=0;j<p[nPezzo].c;j++)
{
cout<<p[nPezzo].M[i][j]<<" ";
}
cout<<endl;
}
}
bool puoEntrare(int x,int y,int nPezzo)
{
for(int i=x;i<x+p[nPezzo].r;i++)
{
for(int j=y;j<y+p[nPezzo].c;j++)
{
if(p[nPezzo].M[i-x][j-y]!=0 && board[i][j]!=0)
{
return false;
}
}
}
return true;
}
void aggiungiPezzo(int x,int y,int nPezzo)
{
for(int i=x;i<x+p[nPezzo].r;i++)
{
for(int j=y;j<y+p[nPezzo].c;j++)
{
if(p[nPezzo].M[i-x][j-y] !=0)
board[i][j]=p[nPezzo].M[i-x][j-y];
}
}
}
void manovraAggiungi(int nPezzo)
{
for(int i=0;i<d;i++)
{
for(int j=0;j<d;j++)
{
if(puoEntrare(i,j,nPezzo))
{
aggiungiPezzo(i,j,nPezzo);
return;
}
}
}
}
void stampaBoard()
{
cout<<endl;
for(int i=0;i<d;i++)
{
for(int j=0;j<d;j++)
{
cout<<board[i][j]<<" ";
}
cout<<endl;
}
}
bool controllaSoluzione()
{
for(int i=0;i<d;i++)
{
for(int j=0;j<d;j++)
{
if(M[i][j]==0)
return false;
}
}
return true;
}
int main()
{
int nPezzo=0;
while(nPezzo <= 4)
{
inizializzaPezzo(nPezzo);
formaPezzo(nPezzo);
stampaPezzo(nPezzo);
nPezzo++;
}
nPezzo=0;
while(nPezzo <= 4)
{
manovraAggiungi(nPezzo);
nPezzo++;
}
if(!controllaSoluzione())
cout<<"non esistono soluzioni possibili"<<endl;
else
cout<<"Soluzione: "<<endl;
stampaBoard();
return 0;
}

[Scara95]

Puoi rispiegare maglio il problema, di che cosa hai bisogno? Magari in italiano e usando la punteggiatura...

[effe_89]

Allora..il programma deve ricevere 5 pezzi rappresentati da 1 e 5 per esempio:
pezzo1:
1 1
1 1
pezzo2:
2 0
2 2
2 0
pezzo3:
3 3
0 3
3 3
pezzo4:
4 4 0
4 4 4
4 4 4
pezzo5:
5 5
5 5
Risultato finale:
1 1 2 3 3
1 1 2 2 3
4 4 2 3 3
4 4 4 5 5
4 4 4 5 5
ora sono incastrati tutti i pezzi perchè io li ho messi in ordine, ma se per esempio mette questi pezzi in modo diverso non mi darà una possibile soluzione mentre invece esiste.
per far ciò dovrei applicare il backtracking.
Ora è più chiaro?

[MItaly]

Originariamente inviato da effe_89
...

Ok, vedo ora che hai chiarificato; in futuro imposta correttamente la discussione fin da subito, per com'era all'inizio te la stavo chiudendo. Magari sistema anche il post di apertura, aggiungendo una descrizione comprensibile (non in SMS-ese) del problema, l'indentazione al codice ed eventualmente qualche commento, così chi apre la discussione vede da subito qualcosa di comprensibile.

[effe_89]

ok..aspetto, grazie!

[Scara95]

Il modo più semplice per risolvere un problema del genere è scrivere una funzione che prova a combinare i pezzi che tu gli dai in ordine, fare una permutazione dei pezzi:

ABCD BACD CABD DABC
ABDC BADC CADB DACB
ACBD BCAD CBAD DBAC
ACDB BCDA CBDA DBCA
ADBC BDAC CDAB DCAB
ADCB BDCA CDBA DCBA

(preso da wikipedia)

e provare passanzo ogni permutazione dei pezzi, se risulta un quadrato hai risolto...

Altrimenti puoi benissimo tenere traccia di ogni passaggio e tornare indietro...

[effe_89]

ma come posso tener traccia?? cioè non so proprio usare la tecnica di backtracking!

[effe_89]

però cosi secondo me non sarebbe molto efficiente!..forse dovrei farla ricorsiva la funzione!..

[Scara95]

Io ti ho presentato la soluzione più semplice non la più efficente...

più efficente forse sarebbe

funzione (risultato, vettore) {
  if(vettore_vuoto)
     if(check(risultato))
       return risultato;
     else
       return NULL;
  foreach x in vettore {
    return_value = funzione(aggiungi_pezzo(x, risultato), rimuovi_elemento(x, vettore))
    if(return_value != NULL)
      return return_value;
  }
  return NULL;
}

E' pseudocodice ovviamente, ma dovrebbe funzionare come principio di logica e calcolare ogni combinazione una sola volta...