Рекурсия не возвращаясь в поисках другого пути

Я пытаюсь написать алгоритм возврата для гармоничной раскраски графа (никакие смежные цвета не могут быть одинаковыми, а каждая пара цветов может появляться только один раз).
Это функция возврата:

void Graph::colorBacktrack(int a, int b) {

print();
for (int i = 1; i <= colors; i++) //assigning colors until match
{
elems[a][b] = i; //color
if (check(a, b)) break; //if it's alright break
if (i == colors) // if all the colors have been used -
return;      //return one stack back and look again

}

int nextA;
int nextB = b;
if (a < size - 1 ) nextA = a + 1;
else {
nextA = 0;
nextB = b + 1;
}

if (a == size && b == size - 1) //when array is complete - cout finished
{
cout << endl << endl << "Finished" << endl << endl;
}

colorBacktrack(nextA, nextB); //go to next node when everything is fine

}

проверка работает правильно и все остальное. Проблема в том, что вывод неправильный — в конце он показывает что-то вроде этого:

1 4 2 6

2 5 7 8

3 6 4 8
<— это не верно

1 7 3 0
<— это тоже неправильно

Поэтому, когда он не может найти решение в текущем дереве, он просто завершает все, а не идет вверх. Почему это происходит?