C/C++ - [C]rompicapo delle 8 regine

sto scrivendo il codice per avere una soluzione al problema delle 8 regine
it.wikipedia.org/wiki/…


per dimensione uguale a 5 il codice funziona bene perchè non è necessario eliminare ricorsivamente le regine poste male per avanzare la cella in cui posizionarla bene.
Potete aiutarmi a scrivere questa parte e capire come ragionare?? non riesco a capire come impostare l'algoritmo

#include <stdio.h>
#include <stdbool.h>

#define N 8

bool riga[N];			//true= attaccata, false= non attaccata
bool diag1[2*N-1];
bool diag2[2*N-1];
int colonna[N];			//colonna[j]=i    posizione(i,j)


void verifica(int j)
{	int i=0;
	for (; i<N; i++) {			//per ogni cella della colonna
		if ( (riga[i]==false) && (diag1[i+j]==false) && (diag2[i-j+N-1]==false) ){		//Se la cella non è attaccata
			colonna[j] = i;   	//metti regina nella cella(i,j)  
			
			riga[i] = true;		// riga i-ma attaccata
			diag1[i+j] = true;
			diag2[i-j+N-1] = true;
			
			if (j < N-1) verifica(j+1);
			else return;			
		}
		
	}
	//elimina ultima regina piazzata e avanza cella
	riga[i] = false;	diag1[i+j] = false; diag2[i+j+N-1] = false;	
	
		
}

void visualizza(void)
{
	char scacc[N][N];
		
	//inizializza la scacchiera a 0
	for (int i = 0; i<N; i++)
		for(int j = 0; j<N; j++)
			scacc[i][j] = '-';
			
	//inserisci regine
	for (int  i = 0; i<N; i++){
		int l = colonna[i];
		scacc[i][l] = '#';
	}
	
	//stampa scacchiera
	for (int i = 0; i<N; i++){
		for (int j = 0; j<N; j++)
			printf("%3c", scacc[i][j]);	
		printf("\n");
	} 
	
	return;
}
 
int main()
{	
	/*inizializza i vettori*/
	for(int i=0; i<N; riga[i++]=false);
	for(int i=0; i<2*N-1; diag1[i++]=false);
	for(int i=0; i<2*N-1; diag2[i++]=false);
	for(int i=0; i<N; colonna[i++]=-1);
	
	verifica(0);		//verifica colonna a partire dalla colonna 0
	visualizza();		// visualizza configurazione scacchiera
	
	return 0;
}

Il metodo più facile per risolvere questo problema è il backtracking. Purtroppo + un metodo abbastanza lento ma finchè la scacchiera è di solo 8x8 va benissimo.
Secondo me ti conviene rifare il codice perchè se l'ho capito bene non hai usato il backtracking

In pratica ognuna delle otto regine del gioco degli scacchi dovranno essere posizionate nella scacchiera 8*8 in modo tale che nessuna delle 8 possa
trovarsi con una delle altre regine, nella stessa riga o stessa colonna o stessa
diagonale.

Si è proprio questo quello che ho cercato di scrivere...e questo è implementato nell'if. il problema èfare il percorso all'indietro...cioè se arrivo in una posizione di stallo devo eliminare la regina e ricominciare da una cella più avanti nella colonna in cui ho eliminato la regina

funzione ricorsiva: se la regina corrente è a posto richiama se stessa per mettere la prossima regina, altrimenti ritorna. Se la pensi ricorsivamente il backtracking si implementa praticamente da solo :p

Esattamente.
Il problema va risolto nel passo generico. Non pensare il programma come le mosse totali da fare ma cosa bisogna fare al passo generico

ho scritto completamente un nuovo codice che funziona ed è pure più semplice da interpretare
posto il codice

#include <stdio.h>
#include <stdbool.h>

#define DIM 8
bool grid[DIM][DIM]={false};

/* Inserisce una regina a partire dalla riga 						*/
/* restiruisce true se l'iserimento è stato fatto, altrimenti false */
bool insert_queen ( int riga );
/* verifica se la cella è sotto attacco	*/
bool sotto_attacco ( int riga, int colonna );
/* visualizza la configurazione delle regine sulla scacchiera */
void visualizza ();


int main()
{ 
	if ( insert_queen(0)) visualizza();
	else printf("\nNessuna configurazione trovata");
	
	return 0;
}


bool insert_queen ( int riga )
{	
	bool inserimento = false;
	
	for ( int colonna = 0; colonna < DIM  && !inserimento; ++colonna ){
		if ( !sotto_attacco(riga, colonna) ) {			//se la cella non è sotto attacco posiziona la regina
		grid[riga][colonna] = true;
		if ( riga == DIM-1 )	inserimento = true;			// (si giunge a questo passo se) regina all'ultima riga è  stata piazzata con successo
		else inserimento = insert_queen ( riga + 1);		//iazzata una regina in una riga cerchiamo di piazzarne altre alle righe successive ricorsivamente
		if ( !inserimento )  grid[riga][colonna] = false;	// se non c'è stato inserimento corretto porta la cella a false 
		}	
	}

	return inserimento;
}

bool sotto_attacco ( int riga, int colonna )
{
	bool attacco = false;
	for ( int dx = -1; dx <= 1 && !attacco; ++dx  ) {		//dx = spostamento su riga. sono possibili 3 spostamenti  -1=su 0=stessa 1=giù
		for(int dy = -1; dy <= 1 && !attacco; ++dy ) {
			if (dx!=0 || dy!=0) {		//considera tutte le celle adiacenti alla cella considerata
				int x = riga + dx; int y = colonna + dy;					//definisce la situazione di tutte le celle 
				while ( x>=0 && x < DIM && y>=0 && y < DIM && !attacco) {
					attacco = grid[x][y];  
					x+=dx;  y+=dy;
				}
			}
		}
	}
	
	return attacco;		
}

void visualizza ()
{
	int scacc[DIM][DIM];
	//inizializza la scacchiera come vuota
	for (int i=0; i<DIM; i++)
		for(int j = 0; j<DIM; j++)
				scacc[i][j] = '-';	
	
	//inserisci regine
	for (int  i = 0; i<DIM; i++){
		for (int j=0; j<DIM; j++)
			if( grid[i][j] ) scacc[i][j] = '#';
	}

	//stampa scacchiera
	for (int i = 0; i<DIM; i++){
		for (int j = 0; j<DIM; j++)
			printf("%3c", scacc[i][j]);	
		printf("\n");
	} 
	
	return;
}

Avete accorgimenti da fare??
domanda: e se volessi tutte le possibili configurazioni come dovrei fare?

Hai tenuto conto anche delle diagonali ?