Ciao! Sono nuovo nel sito, vorrei chiedere se qualcuno può aiutarmi a capire dov'è l'errore nel seguente programma. Esso implementa la risoluzione del problema di inserimento di n regine in una scacchiera di n lati attraverso l'utilizzo di stack e la tecnica del backtracking. Grazie
file.h
#ifndef LAB8_H_
#define LAB8_H_
struct queen {
int riga;
int colonna;
};
template <class Item>
class Stack
{
public:
Stack(int);
~Stack() {delete [] stackPtr;}
bool push(Item &);
bool pop(Item &);
bool conflict(Stack<Item>&, queen &);
void print(Stack<Item>,int);
bool empty() const {return top == -1;}
bool full() const {return top == size - 1;}
Item TOP();
private:
int top;
Item *stackPtr;
int size;
};
#endif /* LAB8_H_ */
file.cpp
#include <iostream>
#include "LAB8.h"
using namespace std;
template <class Item>
Stack<Item>::Stack(int numero)
{
size = numero;
top = -1;
stackPtr = new Item[size];
}
template <class Item>
bool Stack<Item>::push(Item &r)
{
if(!full())
{
stackPtr [++top] = r;
return true;
}
return false;
}
template <class Item>
bool Stack<Item>::pop(Item &r)
{
if(!empty())
{
r=stackPtr[top--];
return true;
}
return false;
}
template <class Item>
Item Stack<Item>::TOP()
{
return stackPtr[top];
}
template <class Item>
bool conflict(Stack<Item> &S,queen &Q)
{
while(!S.empty())
{
Stack<Item> scopia(24);
scopia = S;
for(int j=0;j<S.TOP().riga;j++)
{
if(Q.riga==S.TOP().riga)
return true;
if(Q.colonna==S.TOP().colonna)
return true;
//diagonale principale basso-alto'/'
if(S.TOP().riga - Q.riga == S.TOP().colonna - Q.colonna)
return true;
//diagonale secondaria alto-basso'\'
if(Q.colonna - S.TOP().colonna == S.TOP().riga - Q.riga)
return true;
S.pop(Q);
}
S = scopia;
}
return false;
}
template <class Item>
void print(Stack<Item> S,int numero)
{
for(int i=0;i<numero;i++)
{
queen Q;
cout << "Regina numero " << numero - i << "\n";
cout << "riga: " << S.TOP().riga << "\n";
cout << "colonna: " << S.TOP().colonna << "\n";
S.pop(Q);
}
}
int main()
{
int numeroregine = 1;
cout << "Inserire il numero n di righe/colonne: ";
cin >> numeroregine;
queen q;
q.riga=1;
q.colonna=1;
Stack<queen> s(numeroregine);
bool successo = false;
s.push(q);
while(!successo && !s.empty())
{
if(conflict(s,q))
{
while(!s.empty() || s.TOP().colonna != numeroregine)
s.pop(q);
if(!s.empty())
{
q.colonna=s.TOP().colonna + 1;
s.push(q);
}
}
else if(!conflict(s,q) && s.TOP().riga==numeroregine)
successo = true;
else
{
q.riga=s.TOP().riga+1;
q.colonna=1;
s.push(q);
}
}
if(successo)
{
cout << "\nRegine inserite:\n\n";
print(s,numeroregine);
}
return 0;
}