CSP - backtracking

Problem ośmiu hetmanów.

#include <iostream>
#include <vector>
#include <set>
using namespace std;
 
// szachownica NxN
const int N = 8; 
 
// pos[i] = j oznacza, ze na polu (i,j) stoi hetman
vector<int> pos;
 
// globalny licznik
int c = 0;
void count()
{
	++c;
}
 
void print()
{
	vector<vector<int>> board(N, vector<int>(N));
	for(int i=0; i<pos.size(); ++i)
		board[i][pos[i]] = 1;
	for(int i=0; i<N; ++i)
	{
		for(int j=0; j<N; ++j)
			if(board[i][j])
				cout << 'H';
			else
				cout << '.';
		cout << '\n';
	}
	cout << endl;
	count();
}
 
void backtrack()
{
	// drukuj/zliczaj rozwiazanie
	if(pos.size()==N) count();
	
	// stawiamy nastepnego hetmana we wierszu numer k
	int k = pos.size();
	
	// pozycje na ktorych mozemy go postawic tak,
	// aby nie bylo konfliktu z wczesniej postawionymi
	set<int> s;
	
	// zaczynamy od wszystkich pozycji
	for(int i=0; i<N; ++i) s.insert(i);
	
	// teraz usuwamy te ktore sa szachowane przez 
	// wczesniej postawione hetmany
	for(int i=0; i<k; ++i)
	{
		// kolumna
		s.erase(pos[i]);
		// przekatne
		s.erase(pos[i]+(k-i));
		s.erase(pos[i]-(k-i));
	}
	// zbior kandydatow jest juz gotowy
	// jesli jest pusty, to nawrót
	if(s.empty()) return;
	// jesli nie, iterujemy po nim
	for(int p : s)
	{
		// stawiamy hetmana
		pos.push_back(p);
		// rekurencja
		backtrack();
		// zdejmujemy hetmana
		pos.pop_back();
	}
}
 
int main()
{
	backtrack();
	cout << c << endl;
}
 

Zadanie
Rozwiąż za pomocą backtrackingu sudoku. Przykładowe sudoki do rozwiązania:

	string test0 = "..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..";
	string test1 = ".....6....59.....82....8....45........3........6..3.54...325..6..................";	
	string test2 = "4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......";
	string test3 = "..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9";
	string test4 = "9..8...........5............2..1...3.1.....6....4...7.7.86.........3.1..4.....2..";