Răspuns :
#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].
Vă mulțumim că ați vizitat site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Dacă aveți întrebări sau nevoie de asistență suplimentară, nu ezitați să ne contactați. Ne vedem curând și nu uitați să ne adăugați la marcaje!