bool check(std::vector<std::vector<int>>& a, int x, int y) {
    int n = a.size(), m = a[0].size();
    for(int i = 0; i < n; ++i) {
        if(i != x && a[i][y] == a[x][y]) return false;
    }
    for(int j = 0; j < m; ++j) {
        if(j != y && a[x][j] == a[x][y]) return false;
    }
    int x2 = x - x % 3;
    int y2 = y - y % 3;
    for(int i = 0; i < 3; ++i) {
        for(int j = 0; j < 3; ++j) {
            int x1 = x2 + i;
            int y1 = y2 + j;
            if((x1 != x || y1 != y) && a[x][y] == a[x1][y1]) return false;
        }
    }
    return true;
}


bool go(std::vector<std::vector<int>>& a, int x, int y) {
    int n = a.size(), m = a[0].size();
    if(x == n) {
        return true;
    }
    if(y == m) {
        return go(a, x + 1, 0);
    }
    if(a[x][y] != 0) {
        return go(a, x, y + 1);
    }

    for(int c = 1; c <= 9; ++c) {
        a[x][y] = c;
        if(check(a, x, y) && go(a, x, y + 1)) {
            return true;
        }
    }
    a[x][y] = 0;

    return false;
}


std::vector<std::vector<int>> Solution::solve(std::vector<std::vector<int>>& matrix) {
    go(matrix, 0, 0);
    return matrix;
};