Sudoku Solver in C++ using backtracking

input.txt

530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079

sudoku.cc

#include <bits/stdc++.h>

using namespace std;


constexpr int N = 9;
string board[N];
vector<int> board_sets[N][N];

set<int> sets[3*N];

bool valid(int i, int j, char c) {
    for(int is : board_sets[i][j]) {
        if(sets[is].count(c) > 0) {
            return false;
        }
    }
    return true;
}

void place(int i, int j, char c) {
    for(int is : board_sets[i][j]) {
        sets[is].insert(c);
    }
    board[i][j] = c;
}
void remove(int i, int j, char c) {
    for(int is : board_sets[i][j]) {
        sets[is].erase(c);
    }
    board[i][j] = '0';
}

void init() {
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            board_sets[i][j].push_back(i);
            board_sets[i][j].push_back(N+j);
            int g = 2*N + (i/3) + (j/3)*3;
            board_sets[i][j].push_back(g);

            // printf("(%d,%d) => {%d, %d, %d}\n", i, j, i, N+j, g);
        }
    }

    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            if(board[i][j] != '0')
                place(i, j, board[i][j]);
        }
    }
}

bool solve(int i, int j) {
    // printf("solve(%d, %d)\n", i, j);
    if(j==N) {
        return true;
    }
    if(i==N) {
        return solve(0, j+1);
    }

    if(board[i][j] != '0') {
        // cout << "skiping ! 0\n";
        // cout << board[i][j] << '\n';
        return solve(i+1, j);
    }
    else {
        for(char c = '1'; c <= '9'; ++c) {
            // cout << "place(" << i << ","<<j<< ","<<c<<")\n";
            if(!valid(i,j, c)) continue;


            place(i, j, c);
            if (solve(i+1, j)) {
                return true;
            }
            remove(i, j, c);
        }
        // cout << "last fail!\n";
        return false;
    }
    

}


int main() {

    for(int i = 0; i < N; ++i) {
        cin >> board[i];
    }
    init();

    // for(int i= 0; i < N; ++i) {
    //     for(int j = 0; j < N; ++j) {
    //         cout << "{";
    //         for(int s :board_sets[i][j]) {
    //             cout << s << ':';
    //             for(char x : sets[s]) {
    //                 cout << x << ';';
    //             }
    //         }
    //         cout << "}";
    //     }
    //     cout << '\n';
    // }

    if(solve(0, 0)) {
        cout << "solved!\n";
    }
    else {
        cout << "failed!\n";
    }
        for(auto s : board) {
            cout << s << '\n';
        }


}