Алгоритм отката судоку

Прежде всего, я скажу, что это университетское задание, поэтому я не прошу кого-то написать код за меня, мне просто нужно, чтобы меня направили в правильном направлении. :)

Итак, мне нужно написать алгоритм для решения любой (решаемой) доски судоку произвольного размера. Я написал рекурсивную функцию, которая может решить любую доску 9x9 быстро (~1мс), но когда я делаю большие доски (16x16), которые трудно решить... Один тест длится уже 20 минут, но он никак не может его решить. Он может решить легкие головоломки 16x16 или даже пустую доску 16x16, поэтому я не думаю, что проблема в размерах... скорее всего, проблема в алгоритме, я думаю.

В любом случае, вот основная логика моей программы...

• У меня есть 3D вектор, который хранит возможные значения каждого моего квадрата
• Когда значение помещается в квадрат, оно удаляется из возможных значений окружающего квадрата, строки и столбца, в котором оно находится

Тогда моя функция решения в основном:

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while (there are empty squares that have choices left) {

        find the square with the least number of choices

        if (the square with the least number of choices has 0 choices)
            return false; //not solvable.

        remove that choice from the 3D vector (vector that has the choices for each square)
        make a copy of the board and the 3D choices vector

        fill the square with the choice

        if (solve())
            return true; //we're done

        restore the board and choices vector 
        //the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.

    }

    return false; //can't go any further
}

Есть ли в этом что-то неэффективное? Есть ли способ заставить ее работать лучше? Я предполагаю, что доска 16x16 занимает так много времени, потому что дерево решений для нее очень большое для доски, которая не очень сильно заполнена. Это странно, потому что доска 9x9 решается очень быстро.

Любые идеи или предложения были бы просто замечательными. Если есть какая-то информация, которую я упустил, дайте мне знать!