Resolviendo acertijos criptoritméticos | Retrocediendo-8 – Part 1

Los periódicos y revistas a menudo tienen acertijos criptoaritméticos de la forma:

  SEND
+ MORE
--------
 MONEY
-------- 

El objetivo aquí es asignar a cada letra un dígito del 0 al 9 para que la aritmética funcione correctamente. Las reglas son que a todas las apariciones de una letra se les debe asignar el mismo dígito, y ningún dígito se puede asignar a más de una letra.

• Primero, cree una lista de todos los caracteres que necesitan asignarse para pasar a Resolver
• Si se asignan todos los caracteres, devuelve verdadero si se resuelve el rompecabezas, falso de lo contrario
• De lo contrario, considere el primer carácter no asignado
• para (todas las opciones posibles entre los dígitos que no están en uso)

haga esa elección y luego intente asignar recursivamente el resto de los caracteres
si la recursión es exitosa, devuelva verdadero
si !exitoso, deshaga la asignación e intente con otro dígito

• Si se probaron todos los dígitos y nada funcionó, devuelva falso para activar el retroceso

/* ExhaustiveSolve
* ---------------
* This is the "not-very-smart" version of cryptarithmetic solver. It takes
* the puzzle itself (with the 3 strings for the two addends and sum) and a
* string of letters as yet unassigned. If no more letters to assign
* then we've hit a base-case, if the current letter-to-digit mapping solves
* the puzzle, we're done, otherwise we return false to trigger backtracking
* If we have letters to assign, we take the first letter from that list, and
* try assigning it the digits from 0 to 9 and then recursively working
* through solving puzzle from here. If we manage to make a good assignment
* that works, we've succeeded, else we need to unassign that choice and try
* another digit. This version is easy to write, since it uses a simple
* approach (quite similar to permutations if you think about it) but it is
* not so smart because it doesn't take into account the structure of the
* puzzle constraints (for example, once the two digits for the addends have
* been assigned, there is no reason to try anything other than the correct
* digit for the sum) yet it tries a lot of useless combos regardless
*/
bool ExhaustiveSolve(puzzleT puzzle, string lettersToAssign)
{
    if (lettersToAssign.empty()) // no more choices to make
        return PuzzleSolved(puzzle); // checks arithmetic to see if works
    for (int digit = 0; digit <= 9; digit++)   // try all digits
    {
        if (AssignLetterToDigit(lettersToAssign[0], digit))
        {
            if (ExhaustiveSolve(puzzle, lettersToAssign.substr(1)))
                return true;
            UnassignLetterFromDigit(lettersToAssign[0], digit);
        }
    }
    return false;  // nothing worked, need to backtrack
}

El algoritmo anterior en realidad tiene mucho en común con el algoritmo de permutaciones, prácticamente solo crea todos los arreglos de la asignación de caracteres a dígitos y prueba cada uno hasta que uno funciona o todos se han probado con éxito. Para un rompecabezas grande, esto podría llevar un tiempo.
Un algoritmo más inteligente podría tener en cuenta la estructura del rompecabezas y evitar caer en caminos sin salida. Por ejemplo, si asignamos los personajes comenzando desde el lugar de uno y moviéndose hacia la izquierda, en cada etapa, podemos verificar la corrección de lo que tenemos hasta ahora antes de continuar. Esto definitivamente complica el código, pero conduce a una gran mejora en la eficiencia, lo que hace que sea mucho más factible resolver acertijos grandes.

Debajo del pseudocódigo, en este caso, tiene más casos especiales, pero el mismo diseño general

• Comience examinando el dígito más a la derecha de la fila superior, con un acarreo de 0
• Si estamos más allá del dígito más a la izquierda del rompecabezas, devuelve verdadero si no hay acarreo, falso de lo contrario
• Si actualmente estamos tratando de asignar un carácter en uno de los sumandos.
  Si el carácter ya está asignado, simplemente recurra en la fila debajo de este, agregando valor a la suma
  . Si no está asignado, entonces
  • para (todas las opciones posibles entre los dígitos que no están en uso)
    haga esa elección y luego en la fila debajo de esta, si tiene éxito, devuelva verdadero
    si tiene éxito, deshaga la asignación e intente con otro dígito
  • devolver falso si ninguna asignación funcionó para activar el retroceso
• De lo contrario, si intenta asignar un carácter en la suma
• Si el carácter asignado y las coincidencias son correctas,
  recurra en la siguiente columna a la izquierda con acarreo, si el éxito devuelve verdadero,
• Si char asignado y no coincide, devuelve falso
• Si el carácter no está asignado y el dígito correcto ya se usó, devuelve falso
• Si el carácter no está asignado y el dígito correcto no se usa,
  asígnelo y recurra en la siguiente columna a la izquierda con acarreo, si tiene éxito, devuelve verdadero
• devuelve falso para activar el retroceso

Fuente:
http://see.stanford.edu/materials/icspacs106b/H19-RecBacktrackExamples.pdf