Проблемы с пониманием рекурсии в этом приложении

Я пишу рекурсивный решатель для головоломки Судоку. Я храню пустые места с нулями, чтобы моя программа могла их легче читать. У меня есть оригинальная головоломка, начиная с нижнего индекса, чтобы лучше визуализировать сетку. Я не уверен, что у меня есть полное представление о рекурсии, и в этом проблема. Я получаю вывод, который, кажется, на пути к разгадке головоломки, но он оставляет там нули, которых не должно быть. Я думаю, что это как-то связано с размещением моего unsetSquare или с операторами return.

Вот пример вывода …

**************************************************
7  4  3 | 8  2  1 | 5  6  8
2  6  8 | 0  9  0 | 0  1  0
0  0  0 | 0  0  6 | 0  0  4
---------|---------|---------
0  0  0 | 0  0  0 | 2  3  9
0  0  0 | 0  0  0 | 0  0  0
4  1  5 | 0  0  0 | 0  0  0
---------|---------|---------
9  0  0 | 5  0  0 | 0  0  0
0  2  0 | 0  1  0 | 7  4  0
0  0  0 | 2  0  0 | 9  0  5
**************************************************
**************************************************
7  4  3 | 8  2  1 | 5  6  9
2  6  8 | 0  9  0 | 0  1  0
0  0  0 | 0  0  6 | 0  0  4
---------|---------|---------
0  0  0 | 0  0  0 | 2  3  9
0  0  0 | 0  0  0 | 0  0  0
4  1  5 | 0  0  0 | 0  0  0
---------|---------|---------
9  0  0 | 5  0  0 | 0  0  0
0  2  0 | 0  1  0 | 7  4  0
0  0  0 | 2  0  0 | 9  0  5
**************************************************
**************************************************
7  4  3 | 8  2  1 | 5  6  0
2  6  8 | 1  9  0 | 0  1  0
0  0  0 | 0  0  6 | 0  0  4
---------|---------|---------
0  0  0 | 0  0  0 | 2  3  9
0  0  0 | 0  0  0 | 0  0  0
4  1  5 | 0  0  0 | 0  0  0
---------|---------|---------
9  0  0 | 5  0  0 | 0  0  0
0  2  0 | 0  1  0 | 7  4  0
0  0  0 | 2  0  0 | 9  0  5
**************************************************
**************************************************
7  4  3 | 8  2  1 | 5  6  0
2  6  8 | 2  9  0 | 0  1  0
0  0  0 | 0  0  6 | 0  0  4
---------|---------|---------
0  0  0 | 0  0  0 | 2  3  9
0  0  0 | 0  0  0 | 0  0  0
4  1  5 | 0  0  0 | 0  0  0
---------|---------|---------
9  0  0 | 5  0  0 | 0  0  0
0  2  0 | 0  1  0 | 7  4  0
0  0  0 | 2  0  0 | 9  0  5
**************************************************
**************************************************
7  4  3 | 8  2  1 | 5  6  0
2  6  8 | 3  9  0 | 0  1  0
0  0  0 | 0  0  6 | 0  0  4
---------|---------|---------
0  0  0 | 0  0  0 | 2  3  9
0  0  0 | 0  0  0 | 0  0  0
4  1  5 | 0  0  0 | 0  0  0
---------|---------|---------
9  0  0 | 5  0  0 | 0  0  0
0  2  0 | 0  1  0 | 7  4  0
0  0  0 | 2  0  0 | 9  0  5
**************************************************

Обратите внимание, что в конце первой строки, он переходит к 8 в поисках решения, затем к 9, 9 не является допустимым, и он достиг конца цикла for, поэтому он заменяет его на ноль и продолжает. Как я могу заставить его вернуться к другим цифрам в первом ряду, чтобы получить более полное решение?

Вот моя функция рекурсии …

bool DoTheWork::addSquare(int& depth, ostream& outStream){
for(int i = ONE; i <= NINE; ++i){
for(int j = ONE; j <= NINE; ++j){
if(i == NINE && j == NINE && board.getSquare(NINE, NINE) != ZERO){
cout << i << "     " << j << endl;
return true;
}
//cout << "original" << board.getSquare(i, j) << "coord: " << i << ", " << j << endl;
if(board.getSquare(i, j) == ZERO){
//cout << "original: " << board.getSquare(i, j) << "coord: " << i << ", " << j << endl;
for(int k = ONE; k <= NINE; ++k){
board.setSquare(i, j, k);
board.display(outStream);
if(board.isLegal()){
return addSquare(depth, outStream);
}
else{
board.unsetSquare(i, j);

}
}
}

}
}
board.display(outStream);
return false;
}