[C++] Algoritmo enumerativo delle N regine

[Neptune]

Salve a tutti,
ho il "noto" problema delle n-regine da risolvere in maniera enumerativa, ovvero:

Data una scacchiera di grandezza N (la grandezza è variabile quindi) come piazzare esattamente N regine sulla scacchiera facendo in modo che non si minaccino a vicenda (ovvero che nessuna possa mangiare l'altra).

Ho il seguente programma che dovrebbe risolvere il problema, con una funzione che reputa l'ammisibilità (ovvero se va bene oppure no) della configurazione e una funzione di scambio, entrambe che funzionano correttamente (le uso per risolvere lo stesso problema con mediante backtraking) ma con la funzione "enumerativa" che non fa il suo lavoro ovvero "mi azzera la scacchiera".

#include <iostream>
#include <cmath>
using namespace std;

/*Funzione che controlla l'ammissibilità di una configurazione*/
inline bool ammissibile(int *V, int n)
{
	/*Scorri tutte le posizioni della scacchiera NxN*/
	for (int i=0; i<n; i++)
		for (int j=0; j<n; j++)
		{
			if (i!=j)
			{
				/*Se ci sono due regine sulla stessa diagonale ritorna false*/
				if (abs(V[i] - V[j]) == abs(i-j))
				{
					return false;
				}
				/*Se ci sono due regine sulla stessa colonna ritorna false*/
				if ((V[i] == V[j]))
				{
					return false;
				}
			}
		}

	return true;
}




inline void stampavettore(int *V, int n)
{
	/*Stampa la schacchiera*/
	for (int i=0; i<n; i++)
		cout << " " << V[i] << " ";
}


inline void scambia(int* V,int i,int j)
{
	/*Esegue lo scambio tra due posizione del vettore scacchiera*/
	int temp = V[i];
	V[i] = V[j];
	V[j] = temp;
}
inline bool enumerativa(int *V,int i ,int n)
{
	stampavettore(V,n);

	if(i==n)
	{
		if (ammissibile(V,n))
		{
			stampavettore(V,n);
			return true;
		}
	}
	else
	{
		bool soluzionetrovata = false;

		for(int j = i; j<n && !soluzionetrovata; j++)
		{
			scambia(V,i,j);

			if (enumerativa(V,i+1,n))
				return true;
			scambia(V,i,j);
		}
	}

	return false;
}
// Problema delle N REGINE

inline void nregine()
{
	int n = 6;

	int scacchiera[n];

	/*Posizioniamo prima le N regine in una posizione iniziale sulla scacchiera*/
	for(int i=0; i<n; i++)
		scacchiera[i] = i;
	//	TECNICA DI BACKTRACKING
	//backtracking(scacchiera,n);
	//	TECNICA ENUMERATIVA
	//	Vengono generate tutte le permutazioni degli elementi del vettore,
	//	lo spazio di ricerca sarÃ_ formato da tali permutazioni

	enumerativa(scacchiera,0,n);
	stampavettore(scacchiera,n);
}
int main (int argc, char * const argv[]) {
	nregine();
    return 0;
}

Purtroppo con la ricorsione non sono una cima e non riesco a capire dove sia il misfatto.

Continuo a lavorarci, se scoprite qualcosa prima di me fate un fischio

Vi ringrazio in anticipo,
Neptune.

[Neptune]

Stavo pensando anche a come progettarlo ex novo, ma non mi viene nulla in mente.

Sostanzialmente il problema da risolvere è come generare la disposizione con ripetizione di n numeri, ovvero:

Se ho un vettore 2x2 mi deve generare 2^2 disposizioni ovvero

00 10 01 11

Se però il vettore è 3x3 me ne deve generare 3^3 e via discorrendo.

Poi la funzione per controllare "se la disposizione è giusta" gia la ho, inoltre se sapessi a priori che ho una scacchiera 5x5 semplicemente metterei 5 for annidati e "risolverei il problema" (contate che sto cercando di fare un algoritmi enumerativo quindi è ovvio che sia poco efficente perchè mi deve generare tutte le possibilità).

Il problema è che io non so a priori quanto sarà grande la scacchiera, la grandezza è sarà un parametro in entrata della mia funzione, quindi non saprei come fare. Probabilmente la cosa si affronta con un algoritmo ricorsivo simile a quello che ho postato ma non mi viene in mente come e non riesco a fixare quello postato.