En primer lugar, afirmaré que esta es una tarea universitaria, así que no estoy pidiendo a alguien que escriba el código para mí, solo necesito que me indiquen en la dirección correcta. :)

Ok, entonces necesito escribir un algoritmo para resolver cualquier tablero de sudoku (solucionable) de tamaño arbitrario. He escrito una función recursiva que puede resolver cualquier tablero de 9x9 rápidamente (~ 1 ms) pero cuando hago tableros más grandes (16x16) que son difíciles de resolver, tiene dificultades ... He tenido una prueba durante 20 minutos y puede ' No parece resolverlo. Puede resolver acertijos sencillos de 16x16 o incluso un tablero de 16x16 en blanco, así que no creo que las dimensiones sean el problema ... es más probable que sea el algoritmo el problema que creo.

e todos modos, esta es la lógica básica de mi programa ...

Tengo un vector 3D que almacena los posibles valores de cada cuadradoCuando se coloca un valor en un cuadrado, se elimina de los posibles valores del cuadrado, fila y columna circundante en el que se encuentra

Entonces mi función de resolución es básicamente:

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
}

¿Hay algo ineficiente en esto? ¿Hay alguna manera de que funcione mejor? Supongo que un tablero de 16x16 lleva tanto tiempo porque el árbol de decisión es tan grande para un tablero que no se llena demasiado. Sin embargo, es extraño, porque una placa de 9x9 se resolverá muy rápido.

Cualquier idea o sugerencia sería absolutamente increíble. Si hay alguna información que me haya perdido, ¡hágamelo saber también!