8 Queens Problema C ++

C ++ può essere usato per risolvere a livello di programmazione molto complessi ma interessanti. Uno di questi problemi cruciali in C ++ è il problema di N-Ceens, in cui "N" rappresenta il numero totale di regine sulla scacchiera. Ora, potresti chiederti quale sia realmente questo problema e come puoi risolverlo con C++. Sarai in grado di scoprire le risposte a queste domande dopo aver esaminato questo articolo.

Qual è il problema delle 8 regine in c++?

Il problema N-Ceens 'o 8 regine si riferisce alla situazione in cui si desidera posizionare il numero dato di regine su una scacchiera in modo che nessuna regina possa essere attaccata da un'altra verticale, orizzontalmente o in diagonale.e., Tutte le regine dovrebbero essere posizionate in modo così intelligente che nessuno di loro può essere attaccato dall'altro in alcun modo.

Come risolvere il problema delle 8 regine in C ++ in Ubuntu 20.04?

In questo segmento, condivideremo con te la procedura di risolvere il problema delle 8 regine in C++. Per raggiungere questo obiettivo, abbiamo progettato un codice C ++ mostrato nell'immagine seguente. Tuttavia, prima di continuare a spiegare questo codice, vorremmo condividere con te che abbiamo suddiviso questo codice in piccoli frammenti per la tua facile comprensione. Abbiamo diviso all'incirca questo programma C ++ in una funzione per la stampa di tutti i diversi stati della scacchiera che soddisfano la soluzione del problema delle 8 regine, una funzione per verificare se una particolare posizione è sicura per posizionare la regina o meno, una funzione per Risolvere il problema delle 8 regine usando l'algoritmo di backtracking e, infine, la funzione del driver principale. Discuteremo tutti questi frammenti uno per uno.

Nel primo snippet del nostro codice, dopo aver incluso la libreria e lo spazio dei nomi, abbiamo definito una scacchiera di dimensioni 10 x 10 sotto forma di un array 2D. Significa che il nostro programma sarà in grado di prendere 10 regine "al massimo per risolvere il problema di N-Queens in C++. Tuttavia, in questo articolo, siamo principalmente interessati al problema delle 8 regine. Dopo aver definito la scacchiera, abbiamo la nostra funzione "stampa" che prende un numero intero come input che si riferisce al numero di regine, i.e., 8 In questo caso particolare. All'interno di questa funzione, abbiamo un ciclo "per" nidificato per stampare semplicemente la scacchiera sul terminale ogni volta che questa funzione viene chiamata. Quindi, abbiamo alcune dichiarazioni "cout" per la stampa di spazi adeguati tra i diversi stati della scacchiera risolta.

Nel secondo frammento del nostro codice C ++, abbiamo la funzione "Issafe" che è lì per verificare se sarà sicuro posizionare una regina in una posizione particolare o no. Per "sicuro" intendiamo che nessun'altra regina può attaccare una particolare regina in verticale, orizzontale o in diagonale. Quindi, abbiamo tre loop "per" indipendenti all'interno di questa funzione che sono lì per verificare separatamente tutte e tre le condizioni. Se una di queste condizioni diventa vera, allora la funzione "Issafe" restituirà "false" perché in questi casi ci sarà sempre una possibilità di attaccare, a causa della quale non saremo in grado di posizionare una regina nella posizione particolare. Tuttavia, se tutte queste condizioni diventano false, io.e., Non vi è alcuna possibilità di attaccare in quella posizione in verticale, orizzontale o in diagonale, solo allora la funzione "Issafe" restituirà "vero" i.e., Sarà sicuro posizionare una regina nella posizione particolare.

Nel terzo snippet del nostro codice C ++, abbiamo la funzione "Soluzione" che escogiterà la soluzione del problema di N-Queens utilizzando l'algoritmo di backtracking. All'interno di questa funzione, la prima dichiarazione "if" viene utilizzata per verificare se il numero della regina è uguale al numero totale di regine o no. Se questa affermazione valuta essere vera, la funzione "Printboard" verrà immediatamente chiamata. Altrimenti, verrà definito un "risultato" variabile booleano il cui stato iniziale è mantenuto "falso". Quindi, abbiamo un altro ciclo "per" all'interno del quale chiamiamo iterativamente la funzione "Issafe" per ciascuna delle regine per scoprire se la posizione data è sicura per posizionarlo o no. In questa condizione, abbiamo usato la ricorsione per eseguire il backtracking per posizionare le regine nelle posizioni più sicure in modo che non possano essere attaccati da nessun'altra regina. Qui, "1" rappresenterà che una regina è posizionata in una posizione particolare, mentre "0" rappresenterà tutte le posizioni vuote della scacchiera. Infine, abbiamo restituito la variabile "risultato" per avvisare se la soluzione al numero dato di regine è possibile o no.

Nell'ultimo frammento del nostro codice C ++, abbiamo la funzione principale del driver. Il motivo alla base dell'utilizzo delle prime due dichiarazioni all'interno della nostra funzione "Main ()" è l'ottimizzazione delle prestazioni perché, per un numero maggiore di regine, il programma potrebbe eseguire irragionevolmente più lento. Tuttavia, puoi saltarli se lo desideri. Quindi, abbiamo definito un numero intero "n" che corrisponde al numero di regine. Successivamente, abbiamo visualizzato un messaggio sul terminale per spingere l'utente a inserire il numero di regine per le quali desidera risolvere il problema di N-Ceens. Quindi, abbiamo semplicemente acquisito questo come input dall'utente. Dopodiché, abbiamo un ciclo "per" nidificato in cui abbiamo chiamato la funzione "scacchiera". Quindi, abbiamo chiamato la funzione "soluzione" e memorizzato il suo output nella variabile "risultato". Se il valore della variabile "risultato" sarà "falso", ciò significherà che non esiste alcuna soluzione per il numero di regine. Finalmente, abbiamo la dichiarazione "return 0" per concludere il nostro codice.

Per compilare questo codice, abbiamo usato il seguente comando:

$ g ++ 8queens.CPP -O 8queens

Per eseguire questo codice, abbiamo usato il comando aggiunto di seguito:

$ ./8queens

Per prima cosa ci è stato chiesto di inserire il numero di regine come mostrato nella seguente immagine:

Abbiamo inserito "8" per il nostro caso particolare, come mostrato nell'immagine seguente:

Non appena si fornisce il numero di regine, tutte le possibili soluzioni al problema delle 8 regine appariranno sul terminale come mostrato nella seguente immagine:

Per testare questo codice per l'altro caso, io.e., La soluzione non esiste, abbiamo fornito "3" come numero di regine. Questo è mostrato nell'immagine qui sotto:

Comprendiamo che per una scacchiera da 3 x 3, non esiste alcuna soluzione; Ecco perché abbiamo ricevuto il seguente output:

Conclusione

Questo articolo riguardava il problema delle 8 regine in C ++ in Ubuntu 20.04. Ti abbiamo spiegato brevemente questo problema e tutte le condizioni che devono essere soddisfatte per risolvere questo problema. Successivamente, abbiamo condiviso con te un programma C ++ a tutti gli effetti che risolverà questo problema per te per 8 regine o a Max 10 Queens. Inoltre, abbiamo anche testato questo codice per un caso in cui la soluzione a questo problema è impossibile. Speriamo che, dopo aver letto questa guida, avrai una buona comprensione del famoso problema delle 8 regine in C++.