piffy

Sudoku

Jan 5th, 2020
161
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <chrono>
  3. using namespace std;
  4.  
  5. #define LIBERA 0
  6. #define N 9
  7.  
  8. bool trova_casella_vuota(int griglia[N][N], int &riga, int &colonna);
  9.  
  10. bool va_bene(int griglia[N][N], int riga,int colonna, int num);
  11.  
  12. bool risolvi(int griglia[N][N]);
  13.  
  14. //Cuore del programma. Prende una griglia parzialmente riempita e
  15. //prova a completarla ricorsivamente
  16.  
  17. bool risolvi(int griglia[N][N])
  18. {
  19.     int riga, colonna;
  20.  
  21.     if (!trova_casella_vuota(griglia, riga, colonna))
  22.         return true; // siamo a posto!
  23.  
  24.     for (int num = 1; num <= 9; num++)
  25.     {
  26.         if (va_bene(griglia, riga, colonna, num))
  27.         {
  28.             // prova a vedere se va bene
  29.             griglia[riga][colonna] = num;
  30.             if (risolvi(griglia))
  31.                 return true;
  32.             // Torna indietro
  33.             griglia[riga][colonna] = LIBERA;
  34.         }
  35.     }
  36.     return false; // Forza il backtracking
  37. }
  38.  
  39.  
  40. bool trova_casella_vuota(int griglia[N][N],
  41.                          int &riga, int &colonna)
  42. {
  43.     for (riga = 0; riga < N; riga++)
  44.         for (colonna = 0; colonna < N; colonna++)
  45.             if (griglia[riga][colonna] == LIBERA)
  46.                 return true;
  47.     return false;
  48. }
  49.  
  50. bool usato_nella_riga(int griglia[N][N], int riga, int num)
  51. {
  52.     for (int colonna = 0; colonna < N; colonna++)
  53.         if (griglia[riga][colonna] == num)
  54.             return true;
  55.     return false;
  56. }
  57.  
  58. bool usato_nella_colonna(int griglia[N][N], int colonna, int num)
  59. {
  60.     for (int riga = 0; riga < N; riga++)
  61.         if (griglia[riga][colonna] == num)
  62.             return true;
  63.     return false;
  64. }
  65.  
  66. bool usato_nella_scatola(int griglia[N][N], int boxStartriga,
  67.                          int boxStartcolonna, int num)
  68. {
  69.     for (int riga = 0; riga < 3; riga++)
  70.         for (int colonna = 0; colonna < 3; colonna++)
  71.             if (griglia[riga + boxStartriga]
  72.                 [colonna + boxStartcolonna] == num)
  73.                 return true;
  74.     return false;
  75. }
  76.  
  77. //Controlla se si può assegnare una cifra alla riga e colonna indicata
  78. bool va_bene(int griglia[N][N], int riga,
  79.              int colonna, int num)
  80. {
  81.     return !usato_nella_riga(griglia, riga, num) &&
  82.            !usato_nella_colonna(griglia, colonna, num) &&
  83.            !usato_nella_scatola(griglia, riga - riga % 3,
  84.                                 colonna - colonna % 3, num) &&
  85.            griglia[riga][colonna] == LIBERA;
  86. }
  87.  
  88. void stampa(int griglia[N][N])
  89. {
  90.     for (int riga = 0; riga < N; riga++)
  91.     {
  92.         for (int colonna = 0; colonna < N; colonna++)
  93.             cout << griglia[riga][colonna] << " ";
  94.         cout << endl;
  95.     }
  96. }
  97.  
  98.  
  99. int main()
  100. {
  101.     int griglia[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
  102.                       {5, 2, 0, 0, 0, 0, 0, 0, 0},
  103.                       {0, 8, 7, 0, 0, 0, 0, 3, 1},
  104.                       {0, 0, 3, 0, 1, 0, 0, 8, 0},
  105.                       {9, 0, 0, 8, 6, 3, 0, 0, 5},
  106.                       {0, 5, 0, 0, 9, 0, 6, 0, 0},
  107.                       {1, 3, 0, 0, 0, 0, 2, 5, 0},
  108.                       {0, 0, 0, 0, 0, 0, 0, 7, 4},
  109.                       {0, 0, 5, 2, 0, 6, 3, 0, 0}};
  110.  
  111.  
  112.  
  113.     chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
  114.     bool risolto=risolvi(griglia);
  115.     chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
  116.     cout << "Durata calcoli = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
  117.  
  118.     if (risolto)
  119.         stampa(griglia);
  120.     else
  121.         cout << "Nessuna soluzione\n";
  122.  
  123.     return 0;
  124. }
  125.  
  126. // Codice originale di rathbhupendra
RAW Paste Data