Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #include <chrono>
- using namespace std;
- #define LIBERA 0
- #define N 9
- bool trova_casella_vuota(int griglia[N][N], int &riga, int &colonna);
- bool va_bene(int griglia[N][N], int riga,int colonna, int num);
- bool risolvi(int griglia[N][N]);
- //Cuore del programma. Prende una griglia parzialmente riempita e
- //prova a completarla ricorsivamente
- bool risolvi(int griglia[N][N])
- {
- int riga, colonna;
- if (!trova_casella_vuota(griglia, riga, colonna))
- return true; // siamo a posto!
- for (int num = 1; num <= 9; num++)
- {
- if (va_bene(griglia, riga, colonna, num))
- {
- // prova a vedere se va bene
- griglia[riga][colonna] = num;
- if (risolvi(griglia))
- return true;
- // Torna indietro
- griglia[riga][colonna] = LIBERA;
- }
- }
- return false; // Forza il backtracking
- }
- bool trova_casella_vuota(int griglia[N][N],
- int &riga, int &colonna)
- {
- for (riga = 0; riga < N; riga++)
- for (colonna = 0; colonna < N; colonna++)
- if (griglia[riga][colonna] == LIBERA)
- return true;
- return false;
- }
- bool usato_nella_riga(int griglia[N][N], int riga, int num)
- {
- for (int colonna = 0; colonna < N; colonna++)
- if (griglia[riga][colonna] == num)
- return true;
- return false;
- }
- bool usato_nella_colonna(int griglia[N][N], int colonna, int num)
- {
- for (int riga = 0; riga < N; riga++)
- if (griglia[riga][colonna] == num)
- return true;
- return false;
- }
- bool usato_nella_scatola(int griglia[N][N], int boxStartriga,
- int boxStartcolonna, int num)
- {
- for (int riga = 0; riga < 3; riga++)
- for (int colonna = 0; colonna < 3; colonna++)
- if (griglia[riga + boxStartriga]
- [colonna + boxStartcolonna] == num)
- return true;
- return false;
- }
- //Controlla se si può assegnare una cifra alla riga e colonna indicata
- bool va_bene(int griglia[N][N], int riga,
- int colonna, int num)
- {
- return !usato_nella_riga(griglia, riga, num) &&
- !usato_nella_colonna(griglia, colonna, num) &&
- !usato_nella_scatola(griglia, riga - riga % 3,
- colonna - colonna % 3, num) &&
- griglia[riga][colonna] == LIBERA;
- }
- void stampa(int griglia[N][N])
- {
- for (int riga = 0; riga < N; riga++)
- {
- for (int colonna = 0; colonna < N; colonna++)
- cout << griglia[riga][colonna] << " ";
- cout << endl;
- }
- }
- int main()
- {
- int griglia[N][N] = {{3, 0, 6, 5, 0, 8, 4, 0, 0},
- {5, 2, 0, 0, 0, 0, 0, 0, 0},
- {0, 8, 7, 0, 0, 0, 0, 3, 1},
- {0, 0, 3, 0, 1, 0, 0, 8, 0},
- {9, 0, 0, 8, 6, 3, 0, 0, 5},
- {0, 5, 0, 0, 9, 0, 6, 0, 0},
- {1, 3, 0, 0, 0, 0, 2, 5, 0},
- {0, 0, 0, 0, 0, 0, 0, 7, 4},
- {0, 0, 5, 2, 0, 6, 3, 0, 0}};
- chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();
- bool risolto=risolvi(griglia);
- chrono::steady_clock::time_point end = std::chrono::steady_clock::now();
- cout << "Durata calcoli = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << "[µs]" << std::endl;
- if (risolto)
- stampa(griglia);
- else
- cout << "Nessuna soluzione\n";
- return 0;
- }
- // Codice originale di rathbhupendra
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement