Accedi per seguire   
Seguaci 0
dj GCE

[C] Algoritmo Delle 4 Regine, Mi Serve Un Aiuto

5 messaggi in questa discussione

Ciao ragazzi, mi serve una mano in un algoritmo sulla risoluzione del problema delle 4 regine (conosciuto anche come problema delle 8 regine) per n>=4.

Praticamente ho sviluppato un algoritmo strutturale basato su un array per la risoluzione di detto problema, ma non mi rendo minimamente conto perché non funzioni, e vorrei mi spiegaste come fare per farlo funzionare.

Il codice è:

#include<stdio.h>
#include<stdlib.h>

int main()
{
int i;
printf("Algoritmo delle 4 regine\n");
printf("\nTi risolvo il problema con n>4\n");
int numregine;
printf("\nInserire numero regine: ");

scanf("%d",&numregine);
if(numregine<4)
{
printf("numero regine insufficiente\n");
return -1;
}
int scacchiera[numregine];
scacchiera[0]=1;
int regineposizionate=1;
int k=1;
scacchiera[k]=1;
while(regineposizionate<numregine)
{
i=0;
while(i<k)
{
if(scacchiera[i]==scacchiera[k])
scacchiera[k]++;
else if(scacchiera[k] - scacchiera[i]==k-i)
scacchiera[k]++;
else if(scacchiera[k] + scacchiera[i]==k+i)
scacchiera[k]++;
else
i++;
} 
if(scacchiera[k]>numregine)
{
scacchiera[k]=0;
scacchiera[k--]++;
}
else
regineposizionate++;
k++;

}
int j;
for(j=0;j<numregine;j++)
printf("%d ",scacchiera[j]);
system("pause");
return 0;
}

Per n=4 mi restituisce4 come risultato 1 3 2 4 invece di 2 4 1 3, per n=5 va in loop.

Come debbo fare per raddrizzarlo? :confused2:

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Io non ci capisco una mazza.

Però è un piacere leggerti.

Un caro saluto e ... a presto.

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Passando dall'assunto che non ci capisco una beneamata pizza di C...

Io ho googlato e ho visto che un metodo di soluzion parla di Backtracking. E' quello che hai provato di fare tu?

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Passando dall'assunto che non ci capisco una beneamata pizza di C...

Io ho googlato e ho visto che un metodo di soluzion parla di Backtracking. E' quello che hai provato di fare tu?

Assolutamente sì, anche perché è l'unica via percorribile.

In pratica il backtracking dovrebbe permettermi di sistemare le regine precedentementi allocate se vi sono conflitti tali da farmi uscire le regine dalla scacchiera, ma credo sia proprio il backtracking a non funzionare, oltre al controllo della diagonale :think1:

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

In un altro sito mi hanno suggerito un modo per risolverlo e funziona.

Grazie a tutti comunque :)

Condividi questo messaggio


Link di questo messaggio
Condividi su altri siti

Crea un account o accedi per lasciare un commento

Devi essere un utente registrato per partecipare

Crea un account

Iscriviti per un nuovo account nella nostra community. È facile!


Registra un nuovo account

Accedi

Sei già registrato? Accedi qui.


Accedi Ora
Accedi per seguire   
Seguaci 0