[C++]Gestire le diagonali di qualsiasi elemento della matrice

[Iena87]

Aiutooo sto impazzendo....
Sto scrivendo un programma che riesca a risolvere il gioco delle 8 regine, quello dove su una scacchiera si devono posizionare otto regina in modo tale che nessuna mangi le altre...e visto che scervellandomi su carta nn ci riuscivo, sono passato al programma
Ma sono arrivato ad un inceppo: praticamente io per mettere una regina (che indico con un valore pari a 10) vedo se sulla riga, la colonna e le diagonali sulle quali essa si trova c'è già un'altra regina, e ogni controllo lo esprimo tramite una funzione che richiamo in una condizione, ma nn riesco proprio a capire come gestire le diagonali di qualsiasi elemento della matrice...ho notato però che se gli indici sono per esempio, 5 e 4, dove 5 è l'indice delle righe e 4 delle colonne, la diagonale "principale" dell'elemento parte dalla riga 5-4 cioè 1...ma poi nada de nada...questo è il mio prog:

#include <stdio.h>
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.c>

//dichiaro la matrice 8X8 per la scacchiera
const int n=8;
int sc[n][n];

void generazione_scacchiera (void);
void regina(void);
int criga(int);
int ccolonna(int);
int cdp(int,int);
int cds(int,int);
void visualizzazione(void);

int main(){
  generazione_scacchiera();
  regina();
  visualizzazione();
  return 0;
}

void generazione_scacchiera(void){
       int i, j;
       for(i=0;i<=n-1;i++)
          for(j=0;j<=n-1;j++)
              if((i%2)==0){
                  if((j%2)==0)
                     sc[i][j]=0;
                  else
                     sc[i][j]=1;
              }
              else{
                  if((j%2)==0)
                     sc[i][j]=1;
                  else
                     sc[i][j]=0;
              }
}

void regina(void){
       int i, j;
       i=(rand()%8);
       j=(rand()%8);
       if( (criga(i)!=1) && (ccolonna(j)!=1) && (cdp()!=1) && (cds()!=1) )
           sc[i][j]=10;
       else
           regina();
}

int criga(int x){
       int i;
       for(i=0;i<=n-1;i++)
            if(sc[x][j]==10)
               return 2;
       if(i==8)
          return 1;
}

int ccolonna(int x){
       int i;
       for(i=0;i<=n-1;i++)
            if(sc[i][x]==10)
               return 2;
       if(i==8)
          return 1;
}

int cdp(int x,int y){
  ????????
}

int cds(int x,int y){
  ????????
}

void visualizzazione (void){
    int i, j;
    for(i=0;i<=7;i++){
        gotoxy(17,1+(i*3));
        cout<<"_______________________________________________";
        gotoxy(16,2+(i*3));
        cout<<"|     |     |     |     |     |     |     |     |";
        gotoxy(16,3+(i*3));
        cout<<"|     |     |     |     |     |     |     |     |";
        gotoxy(17,4+(i*3));
        cout<<"-----------------------------------------------";
    }

    for(i=0;i<=n-1;i++){

     for(j=0;j<=n-1;j++){
         if(sc[i][j]==1)
             cout<<"N ";
         if(sc[i][j]==0)
             cout<<"- ";
         if(sc[i][j]==10)
             cout<<"R ";
     }
   }
   getch();
}

dove ci sono i punti interrogativi è dove nn so che scrivere....

[Iena87]

nessuno sa come fare????

[edriv]

Non ho visto il tuo codice (magari quando avrò + tempo) ma questo anche se e complicato può esserti utile per fare un bel programma:
http://www.redangel.it/articoli/arti...at=0&pag=1&l=1

[Iena87]

Grazie ma al link datomi si fa un discorso più complicato...io vorrei solo sapere come gestire le diagonali di un qualsiasi elemento della matrice...

[edriv]

Cosa devono fare le funzioni cds e cdp?

[Iena87]

cdp deve controllare la diagonale "principale" di un qualsiasi elemento per controllare se su di essa c'è già una regina....cds la diagonale "secondaria"....questo è il mio problema...nn so0 come gestire le diagonali di un elemento generico di una matrice....sarà semplice ma mi sono impappinato

[edriv]

Ho sviluppato una classe che esegue quello cha dovrebbe fare il tuo programma (forse è un po' + chiara) e dovrebbe funzionare.

Il problema è che andando avanti casualmente le probabilità di azzeccarla diventano minime!

#include <iostream>
#include <cstdlib>

using namespace std;

enum stato
{
    libero = 0,
    occupato = 1,
    regina = 2
};

class scacchiera
{
    // Matrice della scacchiera
    stato m[8][8];
    void occupa(int x, int y)
    {
        unsigned int i,j;
        // Occupa la riga
        for(i=0; i<8; i++)
        	m[i][y] = occupato;
        // Occupa la colonna
        for(j=0; j<8; j++)
        	m[x][j] = occupato;
       	// Occupa la diagonale SO - NE
       	if(x+y < 8) {
       	    i = 0; 
       	    j = x+y;
       	} else {
            i = x+y-7;
            j = 7;
        }    
       	for(; (i<8) && (j>=0);i++, j--)
       		m[i][j] = occupato;
       	// Occupa la diagonale NO - SE
       	if(x>y)
        {
            i = x-y;
            j = 0;
        } else {
            i = 0;
            j = y-x;
        }
        
       	for(;(i<8) && (j<8);i++, j++)
       		m[i][j] = occupato;		
    }  		
public:
    scacchiera()
    {
        init();
    }    
    void init()
    {
        for(int i=0; i<8; i++) {
        	for(int j=0; j<8; j++)
        		m[i][j] = libero;
  		}  	
    }   
    bool imposta_regina(unsigned int x, unsigned int y)
    {
        if(x>7 || y>7)
        {
            cout << "Errore!!" << endl;
            system("PAUSE");
        	exit(1);
        }   	
        if(m[x][y] == libero)
        {
            occupa(x,y);
            m[x][y] = regina;
            return true;
        }
        // else sottointeso
        return false;    
    }
    friend ostream &operator<<(ostream &stream, scacchiera s);
};

ostream &operator<<(ostream &stream, scacchiera s)
{
    for(int i=0; i<8; i++)
    {
        for(int j=0; j<8; j++)
        {
            stream << s.m[i][j] << ' ';
        }
        cout << endl;
    }
}      
      
int main(int argc, char *argv[])
{
    scacchiera a;
    int c; unsigned int x,y;
    do {
        a.init();
        c=0;
        do {
            x = rand() % 8;
            y = rand() % 8;
            if(a.imposta_regina(x,y))
            	c++;
           	else break;
        } while(1);   	
    } while(c<8); 
    cout << a;	
    return 0;
    system("pause");
}

La funzione + importanta è occupa() e contiene quello che mi chiedi.

Ho incluso un main di prova che per il motivo detto prima non da' risultati.

[edriv]

Poi mi sono deciso ad elaborare un algoritmo migliore.
L'ipotesi di base è che ogni regina sarà su una colonna diversa (e anche riga).
Per ogni colonna, a partire dalla prima, il programma trova una posizione casuale libera con la funzione membro getCasualFreePos():

    int getCasualFreePos(unsigned int column)
    {
        unsigned int a[8];
        int c=0;
        for(int i=0; i<8; i++)
        {
            if(m[column][i] == libero)
            // Viva il c++! :)
            	a[c++] = i;	
        }
        if(!c) return -1;
        return a[rand() % c];
    }

che restituisce la riga libera oppure -1 se non esiste.
Il ciclo continua finchè non riesce a posizionare 8 regine.

Il nuovo main() è questo:

int main()
{
    // Randomizza per avere un po' di suspence
    srand(time(NULL));
    scacchiera a;
    int c=0; int x,y;
    do {
        // Evviva ancora il c++! :D
        c++;
        a.init();
        for(x=0; x<8; x++)
        {
            y = a.getCasualFreePos(x);
            if(y>=0)
            	a.imposta_regina(x,y);
           	else
           		break;
  		}
  		// Ogni 10 volte scrive qualcosa per dire che sta lavorando
  		if(c%10 == 0) cout << '.';
    } while(x<8); 
    cout << endl << "Al tentativo n. " << c << " ho risolto!" << endl;
    cout << "Ecco la soluzione:" << endl;
    cout << a;
    system("pause");
    return 0;
}

ed ho modificato per un miglior output l'operatore <<:

ostream &operator<<(ostream &stream, scacchiera s)
{
    for(int i=0; i<8; i++)
    {
        for(int j=0; j<8; j++)
        {
            switch(s.m[i][j]) {
            case libero:
                cout << ' '; break;
            case occupato:
            	cout << '-'; break;
           	case regina:
           	    cout << 'Q'; break;
           	}
            cout << ' ';    
        }
        cout << endl;
    }
}

aggiungendo e sostituendo questo codice a quello postato prima, compilando ed eseguendo potrete avere la soluzione in poco tempo.
Io ho avuto un massimo di 183 e un minimo di 3 tentativi con semi diversi.
Ecco una delle soluzioni possibili:

- - - Q - - - -
- - - - - - Q -
- - - - Q - - -
- Q - - - - - -
- - - - - Q - -
Q - - - - - - -
- - Q - - - - -
- - - - - - - Q

P.S. Tra l'altro una soluzione l'avevo già trovata cazzeggiando in spiaggia

[Iena87]

Grazie mille
Sei stato gentilisimo

[LeleFT]

Ti dò una pillola che ti può essere utile: esiste un invariante sulle diagonali delle matrici! Percorrendo una qualsiasi diagonale principale rimane invariata (per ciascuna casella) la differenza fra le coordinate (RIGA - COLONNA), mentre percorrendo qualsiasi diagonale secondaria, rimane invariata la somma delle coordinate (RIGA + COLONNA). Esempietto:

     0   1   2   3   4
   |---|---|---|---|---|
 0 | P |   |   | S |   |
   |---|---|---|---|---|
 1 |   | P | S |   |   |
   |---|---|---|---|---|
 2 |   | S | P |   |   |
   |---|---|---|---|---|
 3 | S |   |   | P |   |
   |---|---|---|---|---|
 4 |   |   |   |   | P |
   |---|---|---|---|---|

Con il simbolo P ho evidenziato una diagonale principale (quella più grande, ma vale in generale), mentre con il simbolo S ho evidenziato una diagonale secondaria.

Puoi notare che, se prendi una qualsiasi casella sulla diagonale P la differenza fra le coordinate è sempre 0.
Se prendi una qualsiasi casella sulla diagonale S la somma delle coordinate è sempre 3.
In questo modo puoi indicizzare ciascuna diagonale attraverso il proprio invariante.

Questo invariante l'ho usato 2 anni fa per realizzare un programmino stupidissimo che contava il numero di occorrenze di un carattere...

Ciao.