Infinite loop in Alphametics solution

I'm trying to solve the Alphametics problem using backtracking. Quoting Wikipedia:

is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters of the alphabet. The goal is to identify the value of each letter.

For example:

     S E N D
+    M O R E
------------
   M O N E Y

The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.

My code is as follows, which works for all but one edge case, where it runs into an infinite loop. I'm having trouble identifying the bug here. I've added extensive comments to describe the algorithm I'm using.

use std::cmp::max;
use std::collections::HashMap;
use std::collections::HashSet;

pub fn solve(input: &str) -> Option<HashMap<char, u8>> {
    let equation = parse(input);
    // Validate equation, "ABC + DEF == GH" is invalid, sum isn't wide enough
    let n = equation[0..equation.len() - 1]
        .iter()
        .map(|r| r.len())
        .reduce(max)
        .unwrap();
    if n > equation[equation.len() - 1].len() {
        return None;
    }
    // println!("{:?}", equation);
    let solution = &mut HashMap::new();
    if is_solvable(&equation, 0, 0, 0, solution) {
        Some(solution.clone())
    } else {
        None
    }
}

/* SEND + MORE = MONEY is parsed into:
 * [
 *   ['D', 'N', 'E', 'S'],
 *   ['E', 'R', 'O', 'M'],
 *   ['Y', 'E', 'N', 'O', 'M']
 * ]
 */
fn parse(s: &str) -> Vec<Vec<char>> {
    s.split_whitespace()
        .map(|x| x.trim().to_ascii_uppercase())
        .filter(|x| x.chars().all(|y| y.is_ascii_uppercase()))
        .map(|x| x.chars().rev().collect())
        .collect()
}

/*
 * Exit conditions:
 *   If we are beyond the leftmost digit of the sum:
 *     Return true if no carry, false otherwise.
 *     Also check that there is no leading zero in the sum.
 *   Else if addend and current column index is beyond the current row:
 *     Recur on row beneath this one.
 *
 * If we are currently trying to assign a char in one of the addends:
 *   If char already assigned, recur on row beneath this one.
 *   If not assigned, then:
 *     For every possible choice among the digits not in use:
 *       Make that choice and recur on row beneath this one.
 *         If successful, return true.
 *         Else, unmake assignment and try another digit.
 *     Return false if no assignment worked to trigger backtracking.
 *
 * Else if trying to assign a char in the sum:
 *   If char already assigned:
 *     If matches the sum digit, recur on next column to the left with carry.
 *     Else, return false to trigger backtracking.
 *   If char unassigned:
 *     If correct digit already used, return false.
 *     Else:
 *       Assign it and recur on next column to the left with carry:
 *         If successful return true.
 *         Else, unmake assignment, and return false to trigger backtracking.
 */
fn is_solvable(
    equation: &[Vec<char>],
    row: usize,
    col: usize,
    carry: u32,
    solution: &mut HashMap<char, u8>,
) -> bool {
    let is_addend = row < (equation.len() - 1);
    // println!(
    //     "row={}, col={}, carry={}, is_addend={}",
    //     row, col, carry, is_addend
    // );
    if col >= equation[row].len() && is_addend {
        return is_solvable(equation, row + 1, col, carry, solution);
    }
    if col == equation[row].len() && !is_addend {
        return carry == 0 && solution[&equation[row][col - 1]] > 0;
    }

    let digit: char = equation[row][col];
    let assigned = solution.contains_key(&digit);

    // let mut sol: Vec<_> = solution.iter().collect();
    // sol.sort_unstable_by_key(|e| e.0);
    // println!(
    //     "digit={}, assigned={}, solution={:?}",
    //     digit, assigned, sol
    // );

    if is_addend {
        if assigned {
            is_solvable(equation, row + 1, col, carry, solution)
        } else {
            let used: HashSet<&u8> = HashSet::from_iter(solution.values());
            let unused: Vec<u8> = (0..=9).filter(|x| !used.contains(x)).collect();
            for i in unused {
                solution.insert(digit, i);
                if is_solvable(equation, row + 1, col, carry, solution) {
                    return true;
                }
                solution.remove(&digit);
            }
            false
        }
    } else {
        let s: u32 = equation[0..equation.len() - 1]
            .iter()
            .filter(|r| col < r.len())
            .map(|r| solution[&r[col]] as u32)
            .sum::<u32>()
            + carry;
        let carry = s / 10;
        let sum_digit = (s % 10) as u8;
        // println!("s={}, sum_digit={}, carry = {}", s, sum_digit, carry);
        if assigned {
            (solution[&digit] == sum_digit) && is_solvable(equation, 0, col + 1, carry, solution)
        } else {
            let used = solution.values().any(|&x| x == sum_digit);
            if used {
                return false;
            }
            solution.insert(digit, sum_digit);
            if is_solvable(equation, 0, col + 1, carry, solution) {
                return true;
            }
            solution.remove(&digit);
            false
        }
    }
}

Failing test case:

"THIS + A + FIRE + THEREFORE + FOR + ALL + HISTORIES + I + TELL + A + TALE + THAT + FALSIFIES + ITS + TITLE + TIS + A + LIE + THE + TALE + OF + THE + LAST + FIRE + HORSES + LATE + AFTER + THE + FIRST + FATHERS + FORESEE + THE + HORRORS + THE + LAST + FREE + TROLL + TERRIFIES + THE + HORSES + OF + FIRE + THE + TROLL + RESTS + AT + THE + HOLE + OF + LOSSES + IT + IS + THERE + THAT + SHE + STORES + ROLES + OF + LEATHERS + AFTER + SHE + SATISFIES + HER + HATE + OFF + THOSE + FEARS + A + TASTE + RISES + AS + SHE + HEARS + THE + LEAST + FAR + HORSE + THOSE + FAST + HORSES + THAT + FIRST + HEAR + THE + TROLL + FLEE + OFF + TO + THE + FOREST + THE + HORSES + THAT + ALERTS + RAISE + THE + STARES + OF + THE + OTHERS + AS + THE + TROLL + ASSAILS + AT + THE + TOTAL + SHIFT + HER + TEETH + TEAR + HOOF + OFF + TORSO + AS + THE + LAST + HORSE + FORFEITS + ITS + LIFE + THE + FIRST + FATHERS + HEAR + OF + THE + HORRORS + THEIR + FEARS + THAT + THE + FIRES + FOR + THEIR + FEASTS + ARREST + AS + THE + FIRST + FATHERS + RESETTLE + THE + LAST + OF + THE + FIRE + HORSES + THE + LAST + TROLL + HARASSES + THE + FOREST + HEART + FREE + AT + LAST + OF + THE + LAST + TROLL + ALL + OFFER + THEIR + FIRE + HEAT + TO + THE + ASSISTERS + FAR + OFF + THE + TROLL + FASTS + ITS + LIFE + SHORTER + AS + STARS + RISE + THE + HORSES + REST + SAFE + AFTER + ALL + SHARE + HOT + FISH + AS + THEIR + AFFILIATES + TAILOR + A + ROOFS + FOR + THEIR + SAFE == FORTRESSES"

Expected Solution:

('A', 1),
('E', 0),
('F', 5),
('H', 8),
('I', 7),
('L', 2),
('O', 6),
('R', 3),
('S', 4),
('T', 9),

Tried this code locally - got the solution in 6 min 13,220 secs (according to time). If you're running this in some automated system, is it possible that it just timeouts earlier?

1 Like

I tried on Alphametics in Rust on Exercism, which times out. I believe their time limit is 3 seconds, which tells me I'm missing something. LeetCode also has a similar problem, although I've not tried running it there yet.

Edit: I've now submitted the solution at LeetCode, and it passed 100% better than other Rust solutions in 188 ms. LeetCode doesn't have a test case like the above.