Te joci Sudoku împreună cu sora ta, iar acela dintre voi care termină primul de completat propriul joc câștigă.
Totuși, ai început să observi că ea termină jocurile prea repede, a reușit să te bată 9/10 ture! E a 11a tură și pare că vei pierde și de data asta. Trebuie să îți dai seama cumva dacă trișează...
Ți se dă o matrice reprezentând configurația finală a tablei sale de Sudoku. Verifică dacă aceasta e o configurație validă, conform regulilor jocului.
Date de intrare
Se citește configurația unui joc de sudoku, format din 9 linii care conțin câte 9 numere întregi fiecare, cu valori între 1 și 9.
Date de ieșire
Afișează mesajul corect dacă matricea citită formează o configurație validă de Sudoku sau incorect, în caz contrar.
Date de intrare
3 6 9 1 2 4 5 8 7
7 2 8 6 5 9 3 1 4
1 4 5 7 3 8 2 6 9
2 9 7 3 6 1 8 4 5
5 8 3 9 4 2 6 7 1
6 1 4 5 8 7 9 2 3
9 7 2 8 1 5 4 3 6
4 5 6 2 7 3 1 9 8
8 3 1 4 9 6 7 5 2
Date de iesire
Corect
Răspunsuri la întrebare
#include <iostream>
#include <unordered_set>
using namespace std;
//Functie care verifica daca linia este valida
bool check_line(unsigned int board[9][9], unsigned line) {
//Multime de numere gasite pe linie
std::unordered_set<unsigned> numbers;
//Pentru fiecare coloana, introdu numerele gasite in multime
for (int c = 0; c < 9; c++) {
numbers.insert(board[line][c]);
}
//Daca exista 9 numere unice in multime atunci linia e valida
if (numbers.size() == 9) return true;
return false;
}
//Functie care verifica daca coloana este valida
bool check_column(unsigned int board[9][9], unsigned col) {
//Multime de numere gasite pe coloana
std::unordered_set<unsigned> numbers;
//Pentru fiecare linie
for (int l = 0; l < 9; l++) {
//Daca numarul curent e mai mic decat 1 sau mai mare decat 9 coloana nu e valida ==> Solutia nu e valida
if (board[l][col] < 1 || board[l][col] >9) return false;
numbers.insert(board[l][col]);
}
//Daca exista 9 numere unice in multime atunci coloana e valida
if (numbers.size() == 9) return true;
return false;
}
//Functie care verifica daca patratul de 3x3 e valid
bool check_big_grid(unsigned int board[9][9], int bg_lin, int bg_col) {
//Multime de numere gasite in patrat
std::unordered_set<unsigned> numbers;
//Introdu fiecare numar din patrat in multime
for (int i = bg_lin * 3; i < bg_lin * 3 + 3; i++) {
for (int j = bg_col * 3; j < bg_col * 3 + 3; j++)
numbers.insert(board[i][j]);
}
//Daca exista 9 numere unice in multime atunci patratul e valid
if (numbers.size() == 9) return true;
return false;
}
bool validSolution(unsigned int board[9][9]) {
//Verifica liniile si coloanele. Daca una din linii sau coloane nu e valida intreaga solitie e nevalida
for (int i = 0; i < 9; i++) {
if (!check_column(board, i)) return false;
if (!check_line(board, i)) return false;
}
//Verifica patratele 3x3. Daca unul din ele nu e valid atunci solutia nu e valida
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (!check_big_grid(board, i, j)) return false;
}
}
//Daca totul e ok atunci solutia e valida
return true;
}
int main() {
//Declara tabela sudoku
unsigned sudoku[9][9];
//Citeste tabela
for (int lin = 0; lin < 9; lin++) {
for (int col = 0; col < 9; col++) {
cin >> sudoku[lin][col];
}
}
//Afiseaza rezultat
if (validSolution(sudoku)) cout << "Corect";
else cout << "Incorect";
}
► Explicatie :
Aceasta nu e solutie recomandata pentru incepatori, am facut programul pentru " Sudoku Solution Validator " pe codewars acum ceva timp, nu am timp sa fac unul fara unordered_set, scuze.
Stim regulile pentru sudoku, pe fiecare linie/coloana/patrat 3x3 trebuie sa exista toate cifrele de la 1 la 9. Daca una din conditii nu e indeplinita atunci solutia nu e corecta.
Am folosit unordered_set din STL care reprezinta o structura de date predefinita care retine o multime de elemente. De retinut ca intr-un set se poate insera o valoare o singura data. Daca incercam sa introducem acelasi element de mai multe ori se va retine o singura data (daca bagam 7 de 3 ori in structura va aparea 7 o singura data). Acest lucru poate fi facut cu un vector caracteristic, dar unordered_set ne ofera cateva avantaje si e varianta recomandata in mediu ceva mai profesionist.
unordered_set si set sunt generalizari ale vectorului caracteristic cu care ai rezolva problema in mod normal ca incepator.
Functiile membre ale unordered_set importante folosite in program sunt:
- insert(valoarea) → insereaza valoarea in structura daca NU exista. In caz ca deja exista nu se vor face modificari.
- size() → returneaza numarul de elemente unice din structura. In cazul validarii sudoku acesta trebuie sa fie 9 daca coloana/linia/patratul e valid (daca apare un numar de mai multe ori atunci nu se va insera decat odata, size ar fi mai mic decat 9).
Iti sugerez sa cauti pe internet informatii referitoare la structurile de date din STL, in particular unordered_set pentru mai multe informatii si metode de a simplifica si eficientiza programele.
In verificarea coloanelor se verifica si ca numerele sa fie in interval [1,9].
