lgoritmo de retrocesso do Sudoku

Em primeiro lugar, afirmo que essa é uma tarefa da universidade, então não peço que alguém escreva o código para mim, só preciso ser apontado na direção certa. :)

Ok, então eu preciso escrever um algoritmo para resolver qualquer placa sudoku (solucionável) de tamanho arbitrário. Eu escrevi uma função recursiva que pode resolver qualquer placa 9x9 rapidamente (~ 1ms), mas quando eu faço placas maiores (16x16) difíceis de resolver, ela se esforça. Eu fiz um teste por 20 minutos e ele pode ' parece não resolver isso. Ele pode resolver quebra-cabeças simples de 16x16 ou até um quadro de 16x16 em branco, então não acho que sejam as dimensões que são o problema. É mais provável que seja o algoritmo que é o problema que eu ach

e qualquer forma, esta é a lógica básica do meu program

Eu tenho um vetor 3D que armazena os valores possíveis de todos os meus quadradosQuando um valor é colocado em um quadrado, ele é removido dos possíveis valores do quadrado, linha e coluna circundantes em que está

Então minha função de resolução é basicamente:

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 ar,e 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
}

Existe algo ineficiente sobre isso? Existe alguma maneira de fazê-lo funcionar melhor? Suponho que um quadro de 16x16 leva tanto tempo é porque a árvore de decisão é muito grande para um quadro que não é muito preenchido. É estranho, porque uma placa 9x9 resolverá muito rápido.

Todas as idéias ou sugestões seriam absolutamente incríveis. Se houver alguma informação que eu tenha perdido, avise-me também!