Una solución posible (hay una manera más eficiente pero no la sé xD) es ésta:
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<int> > VVI;
typedef vector<pair<int, int> > VPII;
bool se_puede (VVI& v, int xx, int y, int numero) {
for (int i = 0; i < 9; ++i) {
if (v[xx][i] == numero) return false;
else if (v[i][y] == numero) return false;
}
int fil = 3*(xx/3);
int col = 3*(y/3);
for (int i = fil; i < fil+3; ++i) {
for (int x = col; x < col+3; ++x) {
if (v[i][x] == numero) return false;
}
}
return true;
}
void backtrack (VVI& sudoku, VPII& pos, int count) {
if (count == pos.size()) {
for (int i = 0; i < 9; ++i) {
for (int x = 0; x < 8; ++x) cout << sudoku[i][x] << " ";
cout << sudoku[i][8];
cout << endl;
}
} else {
pair<int, int> p = pos[count];
int posX = p.first;
int posY = p.second;
for (int i = 0; i < 9; ++i) {
if (se_puede(sudoku, posX, posY, i+1)) {
sudoku[posX][posY] = i+1;
backtrack(sudoku, pos, count+1);
sudoku[posX][posY] = 0;
}
}
}
}
int main () {
VVI sudoku(9, vector<int>(9));
VPII blank;
for (int i = 0; i < 9; ++i) {
for (int x = 0; x < 9; ++x) {
cin>>sudoku[i][x];
if (sudoku[i][x] == 0) blank.push_back(make_pair(i, x));
}
}
backtrack(sudoku, blank, 0);
}
la función se_puede devuelve true sí un número (int numero) se puede poner en una casilla específica para un tablero dado.