NoPaste Service
DOWNLOAD
Language: C
Author: Matrix86
Description: Risolutore Problema 8 Regine
Date: 23/09/08 11:50
  1. #include <stdio.h>
  2. #define N 8
  3. /*Questo programma cerca tramite la tecnica di backtracking la soluzione
  4.  * al problema delle 8 regine (Inserire in una scacchiera 8x8, 8 regine
  5.  * senza che si mangino tra loro. Le regine possono muoversi in diagonale,
  6.  * lungo la verticale e l'orizzontale di n caselle).
  7.  * Written By Matrix86
  8.  */
  9.  
  10. void stampa(int mat[N][N]){
  11. //Funzione che stampa a video la matrice
  12.         int i,j;
  13.         for(i=0;i < N;i++){
  14.                 for(j=0;j < N;j++){
  15.                         if(mat[i][j] == 1) printf("R ");
  16.                         else if (mat[i][j] == 0) printf(". ");
  17.                 }
  18.         printf("\n");
  19.         }
  20. }
  21.  
  22. int prova (int mat[N][N], int queen){
  23. /*Backtracking*/
  24.         int i;
  25.         if (queen >= N) return 1;
  26.         for (i = 0; i < N; i++){
  27.                 if (verificaMat(mat,queen,i)) mat[queen][i]=1;
  28.                 else continue;
  29.                 if (prova(mat,queen+1)) return 1;
  30.                 mat[queen][i]=0;
  31.         }
  32.         return 0;
  33. }
  34.  
  35. int verificaMat(int mat[N][N],int riga,int colonna){
  36. //Funzione che testa se la combinazione č giusta
  37.         int i;
  38. //Testo se ci sono pių regine sulla stessa riga
  39.         for (i = 0; i < N; i++) if (mat[riga][i] && i != colonna) return 0;
  40. //Testo se ci sono pių regine sulla stessa colonna
  41.         for (i = 0; i < N; i++) if (mat[i][colonna] && i != riga) return 0;
  42. //Testo la diagonale destra
  43.         if(!controllaDiagNumDx(mat,riga,colonna)) return 0;
  44. //Cerco una regina e vedo lungo la diagonale sinistra
  45.         if(!controllaDiagNumSx(mat,riga,colonna)) return 0;
  46.  
  47.         return 1;
  48. }
  49.  
  50. int controllaDiagNumDx(int matrix[N][N],int x,int y){
  51. //Controlla la diagonale che parte da SX e scende a DX
  52.         int i = x,j = y;
  53.         while((i > 0) && (j > 0)){
  54.                 i--;
  55.                 j--;
  56.                 if(matrix[i][j] == 1) return 0;
  57.         }
  58.        
  59.         i = x;
  60.         j = y;
  61.        
  62.         while((i < N) && (j < N)){
  63.                 i++;
  64.                 j++;
  65.                 if(matrix[i][j] == 1) return 0;
  66.         }
  67. //Controllo passato!
  68.         return 1;
  69. }
  70.  
  71. int controllaDiagNumSx(int matrix[N][N],int x,int y){
  72. //Controlla la diagonale che parte da DX e scende a SX
  73.         int i = x,j = y;
  74.         while((i > 0) && (j < N)){
  75.                 i--;
  76.                 j++;
  77.                 if(matrix[i][j] == 1) return 0;
  78.         }
  79.        
  80.         i = x;
  81.         j = y;
  82.        
  83.         while((i < N) && (j > 0)){
  84.                 i++;
  85.                 j--;
  86.                 if(matrix[i][j] == 1) return 0;
  87.         }
  88.         //Controllo passato!
  89.         return 1;
  90. }
  91.  
  92. int main(int argc,char *argv[]){
  93. //Creo una matrice vuota...
  94.         int mat[N][N] = { 0,0,0,0,0,0,0,0,
  95.                           0,0,0,0,0,0,0,0,
  96.                           0,0,0,0,0,0,0,0,
  97.                           0,0,0,0,0,0,0,0,
  98.                           0,0,0,0,0,0,0,0,
  99.                           0,0,0,0,0,0,0,0,
  100.                           0,0,0,0,0,0,0,0,
  101.                           0,0,0,0,0,0,0,0 };
  102.         fprintf(stdout,"Soluzione del problema delle 8 regine:\n");
  103.         //Se esiste la soluzione stampamela a video...
  104.         if(prova(mat,0)) stampa(mat);
  105.         exit(0);
  106. }
  107.