Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - [C]rompicapo delle 8 regine
Forum - C/C++ - [C]rompicapo delle 8 regine

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 21:23
Martedì, 24/05/2011
sto scrivendo il codice per avere una soluzione al problema delle 8 regine
http://it.wikipedia.org/wiki/Rompicapo_delle_otto_regine


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
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. #define N 8
  5.  
  6. bool riga[N];                   //true= attaccata, false= non attaccata
  7. bool diag1[2*N-1];
  8. bool diag2[2*N-1];
  9. int colonna[N];                 //colonna[j]=i    posizione(i,j)
  10.  
  11.  
  12. void verifica(int j)
  13. {       int i=0;
  14.         for (; i<N; i++) {                      //per ogni cella della colonna
  15.                 if ( (riga[i]==false) && (diag1[i+j]==false) && (diag2[i-j+N-1]==false) ){              //Se la cella non è attaccata
  16.                         colonna[j] = i;         //metti regina nella cella(i,j)  
  17.                        
  18.                         riga[i] = true;         // riga i-ma attaccata
  19.                         diag1[i+j] = true;
  20.                         diag2[i-j+N-1] = true;
  21.                        
  22.                         if (j < N-1) verifica(j+1);
  23.                         else return;                   
  24.                 }
  25.                
  26.         }
  27.         //elimina ultima regina piazzata e avanza cella
  28.         riga[i] = false;        diag1[i+j] = false; diag2[i+j+N-1] = false;    
  29.        
  30.                
  31. }
  32.  
  33. void visualizza(void)
  34. {
  35.         char scacc[N][N];
  36.                
  37.         //inizializza la scacchiera a 0
  38.         for (int i = 0; i<N; i++)
  39.                 for(int j = 0; j<N; j++)
  40.                         scacc[i][j] = '-';
  41.                        
  42.         //inserisci regine
  43.         for (int  i = 0; i<N; i++){
  44.                 int l = colonna[i];
  45.                 scacc[i][l] = '#';
  46.         }
  47.        
  48.         //stampa scacchiera
  49.         for (int i = 0; i<N; i++){
  50.                 for (int j = 0; j<N; j++)
  51.                         printf("%3c", scacc[i][j]);    
  52.                 printf("\n");
  53.         }
  54.        
  55.         return;
  56. }
  57.  
  58. int main()
  59. {      
  60.         /*inizializza i vettori*/
  61.         for(int i=0; i<N; riga[i++]=false);
  62.         for(int i=0; i<2*N-1; diag1[i++]=false);
  63.         for(int i=0; i<2*N-1; diag2[i++]=false);
  64.         for(int i=0; i<N; colonna[i++]=-1);
  65.        
  66.         verifica(0);            //verifica colonna a partire dalla colonna 0
  67.         visualizza();           // visualizza configurazione scacchiera
  68.        
  69.         return 0;
  70. }




PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 21:57
Martedì, 24/05/2011
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


The old lie: Dulce et decorum est pro patria mori
PM Quote
Avatar
Ultimo (Member)
Expert


Messaggi: 513
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 23:11
Martedì, 24/05/2011

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.


Ultimo (Hai voluto la bicicletta ? ....)

Studiare LINQ, WPF, ASP.NET MVC, Entity Framwork, C#, Blend, XAML, Javascript, HTML5, CSS .....(tanta roba)

https://www.dropbox.com/s/c2aots5x4urgbhf/setup_game_sudoku ...
PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 14:58
Mercoledì, 25/05/2011
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

PM Quote
Avatar
TheKaneB (Member)
Guru^2


Messaggi: 1787
Iscritto: 26/06/2009

Segnala al moderatore
Postato alle 16:01
Mercoledì, 25/05/2011
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


Software Failure: Guru Meditation
Forum su Informatica, Elettronica, Robotica e Tecnologia: http://www.nonsoloamiga.com
PM Quote
Avatar
XBarboX (Member)
Guru


Messaggi: 945
Iscritto: 31/12/2008

Segnala al moderatore
Postato alle 17:38
Mercoledì, 25/05/2011
Testo quotato

Postato originariamente da TheKaneB:

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


The old lie: Dulce et decorum est pro patria mori
PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 18:16
Mercoledì, 25/05/2011
ho scritto completamente un nuovo codice che funziona ed è pure più semplice da interpretare
posto il codice
Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdbool.h>
  3.  
  4. #define DIM 8
  5. bool grid[DIM][DIM]={false};
  6.  
  7. /* Inserisce una regina a partire dalla riga                                            */
  8. /* restiruisce true se l'iserimento è stato fatto, altrimenti false */
  9. bool insert_queen ( int riga );
  10. /* verifica se la cella è sotto attacco */
  11. bool sotto_attacco ( int riga, int colonna );
  12. /* visualizza la configurazione delle regine sulla scacchiera */
  13. void visualizza ();
  14.  
  15.  
  16. int main()
  17. {
  18.         if ( insert_queen(0)) visualizza();
  19.         else printf("\nNessuna configurazione trovata");
  20.        
  21.         return 0;
  22. }
  23.  
  24.  
  25. bool insert_queen ( int riga )
  26. {      
  27.         bool inserimento = false;
  28.        
  29.         for ( int colonna = 0; colonna < DIM  && !inserimento; ++colonna ){
  30.                 if ( !sotto_attacco(riga, colonna) ) {                  //se la cella non è sotto attacco posiziona la regina
  31.                 grid[riga][colonna] = true;
  32.                 if ( riga == DIM-1 )    inserimento = true;                     // (si giunge a questo passo se) regina all'ultima riga è  stata piazzata con successo
  33.                 else inserimento = insert_queen ( riga + 1);            //iazzata una regina in una riga cerchiamo di piazzarne altre alle righe successive ricorsivamente
  34.                 if ( !inserimento )  grid[riga][colonna] = false;       // se non c'è stato inserimento corretto porta la cella a false
  35.                 }      
  36.         }
  37.  
  38.         return inserimento;
  39. }
  40.  
  41. bool sotto_attacco ( int riga, int colonna )
  42. {
  43.         bool attacco = false;
  44.         for ( int dx = -1; dx <= 1 && !attacco; ++dx  ) {               //dx = spostamento su riga. sono possibili 3 spostamenti  -1=su 0=stessa 1=giù
  45.                 for(int dy = -1; dy <= 1 && !attacco; ++dy ) {
  46.                         if (dx!=0 || dy!=0) {           //considera tutte le celle adiacenti alla cella considerata
  47.                                 int x = riga + dx; int y = colonna + dy;                                        //definisce la situazione di tutte le celle
  48.                                 while ( x>=0 && x < DIM && y>=0 && y < DIM && !attacco) {
  49.                                         attacco = grid[x][y];  
  50.                                         x+=dx;  y+=dy;
  51.                                 }
  52.                         }
  53.                 }
  54.         }
  55.        
  56.         return attacco;        
  57. }
  58.  
  59. void visualizza ()
  60. {
  61.         int scacc[DIM][DIM];
  62.         //inizializza la scacchiera come vuota
  63.         for (int i=0; i<DIM; i++)
  64.                 for(int j = 0; j<DIM; j++)
  65.                                 scacc[i][j] = '-';     
  66.        
  67.         //inserisci regine
  68.         for (int  i = 0; i<DIM; i++){
  69.                 for (int j=0; j<DIM; j++)
  70.                         if( grid[i][j] ) scacc[i][j] = '#';
  71.         }
  72.  
  73.         //stampa scacchiera
  74.         for (int i = 0; i<DIM; i++){
  75.                 for (int j = 0; j<DIM; j++)
  76.                         printf("%3c", scacc[i][j]);    
  77.                 printf("\n");
  78.         }
  79.        
  80.         return;
  81. }





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

Ultima modifica effettuata da belledetta il 25/05/2011 alle 21:38
PM Quote
Avatar
Ultimo (Member)
Expert


Messaggi: 513
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 16:53
Giovedì, 26/05/2011

Hai tenuto conto anche delle diagonali ?


Ultimo (Hai voluto la bicicletta ? ....)

Studiare LINQ, WPF, ASP.NET MVC, Entity Framwork, C#, Blend, XAML, Javascript, HTML5, CSS .....(tanta roba)

https://www.dropbox.com/s/c2aots5x4urgbhf/setup_game_sudoku ...
PM Quote
Avatar
belledetta (Normal User)
Rookie


Messaggi: 25
Iscritto: 07/09/2010

Segnala al moderatore
Postato alle 19:39
Giovedì, 26/05/2011
esplicitamente no ma è un algoritmo ricorsivo ad albero che implicitam controlla le diagonali rispetto a ogni regina piazzata

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo