Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- void dibuixa_sudoku(const vector<vector<int> > &sudoku)
- {
- cout << endl;
- for (int i = 0; i < 9; i++) {
- cout << sudoku[i][0];
- for (int j = 1; j < 9; j++) {
- cout << " " << sudoku[i][j];
- }
- cout << endl;
- }
- }
- bool legal(const vector<vector<int> > &sudoku, int f, int c, int n)
- {
- //Mirem la fila
- for (int i = 0; i < 9; i++) {
- if (sudoku[i][c] == n) return false;
- }
- //Mirem la columna
- for (int i = 0; i < 9; i++) {
- if (sudoku[f][i] == n) return false;
- }
- //3x3
- int f0 = (f/3)*3, c0 = (c/3)*3;
- for (int i = f0; i < f0 + 3; i++) {
- for (int j = c0; j < c0 + 3; j++) {
- if (sudoku[i][j] == n) return false;
- }
- }
- return true;
- }
- bool resol_sudoku(vector<vector<int> > &sudoku, int f, int c)
- {
- if (f == 9 and c == 0) {
- dibuixa_sudoku(sudoku);
- return true;
- } else {
- if (sudoku[f][c] == 0) {
- for (int i = 1; i <= 9; i++) {
- if (legal(sudoku, f, c, i)) {
- sudoku[f][c] = i;
- if (c == 9-1) {
- if (resol_sudoku(sudoku, f+1, 0)) {
- return true;
- }
- } else {
- if (resol_sudoku(sudoku, f, c+1)) {
- return true;
- }
- }
- sudoku[f][c] = 0;
- }
- }
- } else {
- if (c == 9-1) {
- if (resol_sudoku(sudoku, f+1, 0)) {
- return true;
- }
- } else {
- if (resol_sudoku(sudoku, f, c+1)) {
- return true;
- }
- }
- }
- }
- return false;
- }
- int main()
- {
- int n;
- cin >> n;
- cout << n << endl;
- for (int i = 0; i < n; i++) {
- //Llegir sudoku
- vector<vector<int> > sudoku(9, vector<int>(9, 0));
- for (int j = 0; j < 9; j++) {
- for (int k = 0; k < 9; k++) {
- char c;
- cin >> c;
- if (c != '.') sudoku[j][k] = int(c - '0');
- }
- }
- resol_sudoku(sudoku, 0, 0);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement