Problema delle "otto regine" e metodo euristico

**f@nt@m@n** · 23-09-2006, 23:28

Ciao a tutti,
sto cercando di risolvere il problema delle otto regine abbinando alla scacchiera classica un'altra scacchiera che riporta l'accessibilità delle caselle. Il problema non è ancora completo. Sono giunto a piazzare una regina in una delle caselle meno accessibili ed ora devo adeguare i valori di accessibilità della scacchiera sottraendovi le caselle già eliminate dalla prima regina (spero di essere stato chiaro). Per ora l'ho risolto in questo modo:

codice:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define FALSE 0
#define TRUE 1
#define QUEEN 2

void clearBoard (int[][8]);
void printBoard( int [][8]);
int minAccessBoard (int[][8]);
void takenBoard (int[][8], int, int);
int invalid (int[][8], int , int);

int main(){
    int board[8][8],
    access[8][8] = {22, 22, 22, 22, 22, 22, 22, 22,
                    22, 24, 24, 24, 24, 24, 24, 22,
                    22, 24, 26, 26, 26, 26, 24, 22,
                    22, 24, 26, 28, 28, 26, 24, 22,
                    22, 24, 26, 28, 28, 26, 24, 22,
                    22, 24, 26, 26, 26, 26, 24, 22,
                    22, 24, 24, 24, 24, 24, 24, 22,
                    22, 22, 22, 22, 22, 22, 22, 22},
    currentRow, currentColumn, accessNumber, invalidSquare,
    z, w;
    
    srand(time (NULL));
    clearBoard (board);    

    accessNumber = minAccessBoard (access);
      
    do{
       currentRow = rand() % 8;
       currentColumn = rand() % 8;                
    }while (access[currentRow][currentColumn] > accessNumber);
    
    takenBoard (board, currentRow, currentColumn);
    board[currentRow][currentColumn] = QUEEN;
    
    for (z = 0; z < 8; z++){
        for (w = 0; w < 8; w++){
            invalidSquare = invalid (board, w, z);
            if (board[z][w] == 0){
               access[z][w] -= invalidSquare;
            }
        }
    }
    
    
    printBoard (board);
    
    printBoard (access);
    
    system ("pause");
    
    return 0;
}
void clearBoard (int b[][8])
{
     int k, j;
     
     for (k = 0; k < 8; k++){         
         for (j = 0; j < 8; j++){             
             b[k][j] = FALSE;
         }
     }
}
void printBoard( int workBoard[][ 8 ] )
{ 
   int row, col;

   printf( "   0  1  2  3  4  5  6  7\n" );

   for ( row = 0; row < 8; row++ )
   { 
      printf( "%d", row );

      for ( col = 0; col < 8; col++ )
         printf( "%3d", workBoard[ row ][ col ] );

      printf( "\n" );
    }

   printf( "\n" );
}
int minAccessBoard (int aB[][8])
{
    int k, j, min = 29;
    
    for (k = 0; k < 8; k++){        
        for (j = 0; j < 8; j++){
            if (aB[k][j] < min)
               min = aB[k][j];
        }
    }
    return min;
}
void takenBoard (int tB[][8], int row, int col)
{    
    int i, x, y;
    
    for (i = 0; i < 8; i++){
        x = row;
        y = col;
        
        while (x >= 0 && x < 8 && y >= 0 && y < 8){
              switch (i){
                     case 0:                          
                          tB[x][y++] = TRUE;
                          break;
                     case 1:
                          tB[x++][y++] = TRUE;
                          break;
                     case 2:
                          tB[x++][y] = TRUE;
                          break;
                     case 3:
                          tB[x++][y--] = TRUE;
                          break;
                     case 4:
                          tB[x][y--] = TRUE;
                          break;
                     case 5:
                          tB[x--][y--] = TRUE;
                          break;
                     case 6:
                          tB[x--][y] = TRUE;
                          break;
                     case 7:
                          tB[x--][y++] = TRUE;
                          break;
              }
        }
    }
}
int invalid (int board[][8], int a, int b)
{
     int i, x, y, sum = 0;
     
     for (i = 0; i < 8; i++){
         x = a;
         y = b;
         while (x >= 0 && x < 8 && y >= 0 && y < 8){
               switch (i){
                      case 0:                          
                           sum += board[x][y++];
                           break;
                      case 1:
                           sum += board[x++][y++];
                           break;
                      case 2:
                           sum += board[x++][y];
                           break;
                      case 3:
                           sum += board[x++][y--];
                           break;
                      case 4:
                           sum += board[x][y--];
                           break;
                      case 5:
                           sum += board[x--][y--];
                           break;
                      case 6:
                           sum += board[x--][y];
                           break;
                      case 7:
                           sum += board[x--][y++];
                           break;
               }
         }
     }
     return sum;
}

per quanto riguarda il piazzamento della regina tutto bene. Però non riesco a capire perchè alcuni valori di accessibilità siano sballati.
Sono tre giorni che ci perdo la testa.
Mi sapete consigliare??
p.s. Non sono ho ancora studiato i puntatori

**oregon** · 23-09-2006, 23:29

Chiarisci meglio il problema (valori sballati ...) e indica la zona (piu' o meno) del codice interessata ...

**f@nt@m@n** · 23-09-2006, 23:35

La funzione invalid dovrebbe adeguare i valori che trovi nella definizione di access.
Se per esempio la regina è piazzata in questo modo
00000001
11111112
00000011
00000101
00001001
00010001
00100001
01000001

la access[0][0] che ha valore 22 dovrebbe essere diminuito per i valori che interseca in orizzontale, verticale ed obliquo e come lui tutti gli altri dovrebbero essere adeguati allo stesso modo. In questo caso dovrebbe diventare 22-1(oriz)-1-1-1(obl)-1(vert) = 17.
Ebbene, alcuni valori mi tornano, altri no.

**f@nt@m@n** · 24-09-2006, 14:43

Per favore qualcuno mi può aiutare?
Ho perfezionato il codice e ora mi dovrebbe mancare solo una piccola modifica. La matrice access, nella riga in cui ho messo il commento, dovrebbe tornare sempre ai suoi valori iniziali. Non c'è bisogno di guardare tutto il codive (se volete darmi qualche consiglio per migliorarlo sarà ben accetto)

codice:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define FALSE 0
#define TRUE 1
#define QUEEN 2

void clearBoard (int[][8]);
void printBoard( int [][8]);
int minAccessBoard (int[][8]);
void takenBoard (int[][8], int, int);
int invalid (int[][8], int , int);

int main(){
    int board[8][8],
    access[8][8] = {22, 22, 22, 22, 22, 22, 22, 22,
                    22, 24, 24, 24, 24, 24, 24, 22,
                    22, 24, 26, 26, 26, 26, 24, 22,
                    22, 24, 26, 28, 28, 26, 24, 22,
                    22, 24, 26, 28, 28, 26, 24, 22,
                    22, 24, 26, 26, 26, 26, 24, 22,
                    22, 24, 24, 24, 24, 24, 24, 22,
                    22, 22, 22, 22, 22, 22, 22, 22},
    currentRow, currentColumn, accessNumber, invalidSquare,
    z, w, done = FALSE, h;
    
    srand(time (NULL));
    clearBoard (board);
      
    for (h = 1; h <= 8 ; h++){
        accessNumber = minAccessBoard (access);
          
        do{
           currentRow = rand() % 8;
           currentColumn = rand() % 8;                
        }while (access[currentRow][currentColumn] > accessNumber);
        
        takenBoard (board, currentRow, currentColumn);
        board[currentRow][currentColumn] = QUEEN;
        
        /*DEVO FARE IN MODO CHE QUI LA MATRICE 
          ACCESS ABBIA NUOVAMENTE I VALORI INIZIALI*/ 
        
        for (z = 0; z < 8; z++){
            for (w = 0; w < 8; w++){
                invalidSquare = invalid (board, z, w);
                if (board[z][w] == 0){
                   access[z][w] -= invalidSquare;
                }
            }
        }
    }
    
    
    printBoard (board);
    
    printBoard (access);
    
    system ("pause");
    
    return 0;
}
void clearBoard (int b[][8])
{
     int k, j;
     
     for (k = 0; k < 8; k++){         
         for (j = 0; j < 8; j++){             
             b[k][j] = FALSE;
         }
     }
}
void printBoard( int workBoard[][ 8 ] )
{ 
   int row, col;

   printf( "   0  1  2  3  4  5  6  7\n" );

   for ( row = 0; row < 8; row++ )
   { 
      printf( "%d", row );

      for ( col = 0; col < 8; col++ )
         printf( "%3d", workBoard[ row ][ col ] );

      printf( "\n" );
    }

   printf( "\n" );
}
int minAccessBoard (int aB[][8])
{
    int k, j, min = 29;
    
    for (k = 0; k < 8; k++){        
        for (j = 0; j < 8; j++){
            if (aB[k][j] < min)
               min = aB[k][j];
        }
    }
    return min;
}
void takenBoard (int tB[][8], int row, int col)
{    
    int i, x, y;
    
    for (i = 0; i < 8; i++){
        x = row;
        y = col;
        
        while (x >= 0 && x < 8 && y >= 0 && y < 8){
              switch (i){
                     case 0:                          
                          tB[x][y++] = TRUE;
                          break;
                     case 1:
                          tB[x++][y++] = TRUE;
                          break;
                     case 2:
                          tB[x++][y] = TRUE;
                          break;
                     case 3:
                          tB[x++][y--] = TRUE;
                          break;
                     case 4:
                          tB[x][y--] = TRUE;
                          break;
                     case 5:
                          tB[x--][y--] = TRUE;
                          break;
                     case 6:
                          tB[x--][y] = TRUE;
                          break;
                     case 7:
                          tB[x--][y++] = TRUE;
                          break;
              }
        }
    }
}
int invalid (int board[][8], int a, int b)
{
     int i, x, y, sum = 0;
     
     for (i = 0; i < 8; i++){
         x = a;
         y = b;
         while (x >= 0 && x < 8 && y >= 0 && y < 8){
               switch (i){
                      case 0:                          
                           sum += board[x][y++];
                           break;
                      case 1:
                           sum += board[x++][y++];
                           break;
                      case 2:
                           sum += board[x++][y];
                           break;
                      case 3:
                           sum += board[x++][y--];
                           break;
                      case 4:
                           sum += board[x][y--];
                           break;
                      case 5:
                           sum += board[x--][y--];
                           break;
                      case 6:
                           sum += board[x--][y];
                           break;
                      case 7:
                           sum += board[x--][y++];
                           break;
               }
         }
     }
     return sum;
}

**king64** · 24-09-2006, 20:44

Potresti crearti una matrice di appoggio uguale alla access in modo da re-inizializzare quest'ultima quando ti serve farlo

. Saluti

**f@nt@m@n** · 25-09-2006, 00:58

Originariamente inviato da king64
Potresti crearti una matrice di appoggio uguale alla access in modo da re-inizializzare quest'ultima quando ti serve farlo

. Saluti

Grazie per la risposta. Non so se intendi la stessa cosa, io ho provato con una funzione per inizializzare nuovamente la matrice

codice:

void initAccess (int[][8]);
int main()
{...
     initAccess (access);
...}
void initAccess (int a[][8])
{
     a[8][8] = {22, 22, 22, 22, 22, 22, 22, 22,
                22, 24, 24, 24, 24, 24, 24, 22,
                22, 24, 26, 26, 26, 26, 24, 22,
                22, 24, 26, 28, 28, 26, 24, 22,
                22, 24, 26, 28, 28, 26, 24, 22,
                22, 24, 26, 26, 26, 26, 24, 22,
                22, 24, 24, 24, 24, 24, 24, 22,
                22, 22, 22, 22, 22, 22, 22, 22};
}

ma mi dice che c'è un errore prima della {.
Perchè?

Discussione: Problema delle "otto regine" e metodo euristico

Strumenti discussione

Ricerca discussione

Visualizza

problema con metodo euristico

Permessi di invio