#include <iostream>
#include <vector>

using namespace std;

class Solution {
public:
    vector<vector<int>> MeraSudoku;
    bool rowUsed[9][10]{};
    bool colUsed[9][10]{};
    bool boxUsed[9][10]{};

    int getBoxIndex(int row, int col) {
        return (row / 3) * 3 + (col / 3);
    }

    bool solve() {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (MeraSudoku[i][j] == 0) {
                    for (int num = 1; num <= 9; ++num) {
                        int boxIdx = getBoxIndex(i, j);
                        if (!rowUsed[i][num] && !colUsed[j][num] && !boxUsed[boxIdx][num]) {
                            MeraSudoku[i][j] = num;
                            rowUsed[i][num] = colUsed[j][num] = boxUsed[boxIdx][num] = true;

                            if (solve()) return true;

                            MeraSudoku[i][j] = 0;
                            rowUsed[i][num] = colUsed[j][num] = boxUsed[boxIdx][num] = false;
                        }
                    }
                    return false; // dacă niciun număr nu merge
                }
            }
        }
        return true; // complet rezolvat
    }

    void solveSudoku(vector<vector<char>>& board) {
        MeraSudoku.resize(9, vector<int>(9, 0));
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '0';
                    MeraSudoku[i][j] = num;
                    int boxIdx = getBoxIndex(i, j);
                    rowUsed[i][num] = true;
                    colUsed[j][num] = true;
                    boxUsed[boxIdx][num] = true;
                }
            }
        }

        solve();

        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 9; ++j)
                board[i][j] = MeraSudoku[i][j] + '0';
    }
};

// Funcție de afișare
void printBoard(const vector<vector<char>>& board) {
    for (int i = 0; i < 9; ++i) {
        for (int j = 0; j < 9; ++j)
            cout << board[i][j] << ' ';
        cout << '\n';
    }
}

int main() {
    vector<vector<char>> board = {
        {'5','3','.','.','7','.','.','.','.'},
        {'6','.','.','1','9','5','.','.','.'},
        {'.','9','8','.','.','.','.','6','.'},
        {'8','.','.','.','6','.','.','.','3'},
        {'4','.','.','8','.','3','.','.','1'},
        {'7','.','.','.','2','.','.','.','6'},
        {'.','6','.','.','.','.','2','8','.'},
        {'.','.','.','4','1','9','.','.','5'},
        {'.','.','.','.','8','.','.','7','9'}
    };

    cout << "Initial Board:\n";
    printBoard(board);

    Solution solver;
    solver.solveSudoku(board);

    cout << "\nSolved Board:\n";
    printBoard(board);

    return 0;
}