**Solution Notes:** This problem has a dynamic programming
solution: we scan the input row by row, keeping track of the running
parity of each column and the running parity of each 3x3 subgrid that
is currently "active" (intersecting the current row). More formally,
we define the subproblem A[r][c][s] telling us the minimum number of
toggles necessary to reach a state where all rows down to row r = 1..9
have been modified to have even parity, where c = 0..2^9-1 describes
the running parity of each column and s = 0..2^3-1 describes the
running parity of each active 3x3 subgrid (intersecting row r). There
are only 9 x 2^12 such total subproblems, and each one takes at worst
2^9 steps to solve by trying all possible choices for the toggles in
row r.

```
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
#define INF 100
bool A[9][9]; /* The original sudoku board. */
int memo[9][9][1<<9][1<<3][2]; /* Cache of already computed values. */
int solve(int r, int c, int mc, int mb, bool p) {
if(r == 9) {
/* If we finished the last row make sure the columns have even parity and
* we're done. */
return mc ? INF : 0;
}
if(c == 9) {
/* If we finished a column make sure the row has even parity. */
if(p) return INF;
/* Additionally if we finished a third row make sure the boxes have even
* parity. */
if(r % 3 == 2 && mb) return INF;
/* Otherwise move to the beginning of the next row. */
return solve(r + 1, 0, mc, mb, 0);
}
/* Check if we already figured out this state. */
int& ref = memo[r][c][mc][mb][p];
if(ref != -1) return ref;
/* Try setting the cell to 1. */
ref = !A[r][c] + solve(r, c + 1, mc ^ 1 << c, mb ^ 1 << c / 3, !p);
/* Try setting the cell to 0. */
ref = min(ref, A[r][c] + solve(r, c + 1, mc, mb, p));
return ref;
}
int main() {
freopen("bsudoku.in", "r", stdin);
freopen("bsudoku.out", "w", stdout);
/* Read in the input into A. */
for(int i = 0; i < 9; i++) {
string S; cin >> S;
for(int j = 0; j < 9; j++) A[i][j] = S[j] == '1';
}
memset(memo, -1, sizeof(memo));
cout << solve(0, 0, 0, 0, 0) << endl;
}
```