Poi mi sono deciso ad elaborare un algoritmo migliore.
L'ipotesi di base è che ogni regina sarà su una colonna diversa (e anche riga).
Per ogni colonna, a partire dalla prima, il programma trova una posizione casuale libera con la funzione membro getCasualFreePos():
codice:
    int getCasualFreePos(unsigned int column)
    {
        unsigned int a[8];
        int c=0;
        for(int i=0; i<8; i++)
        {
            if(m[column][i] == libero)
            // Viva il c++! :)
            	a[c++] = i;	
        }
        if(!c) return -1;
        return a[rand() % c];
    }
che restituisce la riga libera oppure -1 se non esiste.
Il ciclo continua finchè non riesce a posizionare 8 regine.

Il nuovo main() è questo:
codice:
int main()
{
    // Randomizza per avere un po' di suspence
    srand(time(NULL));
    scacchiera a;
    int c=0; int x,y;
    do {
        // Evviva ancora il c++! :D
        c++;
        a.init();
        for(x=0; x<8; x++)
        {
            y = a.getCasualFreePos(x);
            if(y>=0)
            	a.imposta_regina(x,y);
           	else
           		break;
  		}
  		// Ogni 10 volte scrive qualcosa per dire che sta lavorando
  		if(c%10 == 0) cout << '.';
    } while(x<8); 
    cout << endl << "Al tentativo n. " << c << " ho risolto!" << endl;
    cout << "Ecco la soluzione:" << endl;
    cout << a;
    system("pause");
    return 0;
}
ed ho modificato per un miglior output l'operatore <<:
codice:
ostream &operator<<(ostream &stream, scacchiera s)
{
    for(int i=0; i<8; i++)
    {
        for(int j=0; j<8; j++)
        {
            switch(s.m[i][j]) {
            case libero:
                cout << ' '; break;
            case occupato:
            	cout << '-'; break;
           	case regina:
           	    cout << 'Q'; break;
           	}
            cout << ' ';    
        }
        cout << endl;
    }
}
aggiungendo e sostituendo questo codice a quello postato prima, compilando ed eseguendo potrete avere la soluzione in poco tempo.
Io ho avuto un massimo di 183 e un minimo di 3 tentativi con semi diversi.
Ecco una delle soluzioni possibili:
codice:
- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q
P.S. Tra l'altro una soluzione l'avevo già trovata cazzeggiando in spiaggia