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),