Help with "alphametics" exercism exercise

First, hi again everybody, been away a while, but getting back into Elixir. Still haven’t landed actual work in it, but seeing more mention of it spurs me to get back in gear learning it.

I’m working on the very last side-quest^Wexercise on Exercism’s Elixir track, “Alphametics”. The aim is to solve puzzles in which letters are substituted for digits, like “SEND + MORE == MONEY” (you have to figure out what digit each letter stands for, and leading digits must not be zero, like S or M in this case).

I’ve solved it in two different ways, but the efficiency is horrible (taking multiple minutes for a nine or ten unique-letter puzzle), so I was thinking there might be some FP-ish or Elixir-ish thing I’m missing. (I’m coming from a background of about nine years of mostly OO programming with a little imperative mixed in, preceded by 26 years of vice-versa.)

The first way, to describe it in English is:

• extract the unique letters
• extract which ones must not be zero (actually I was doing this wrong and getting only the leading digits of the first addend and the sum, but I don’t think that should impact the performance drastically)
• starting with the pool of all digits, recursively:
  – use Enum.any? to give each digit a chance in turn at the below
  – check if this is zero and the “head” letter is one that must not be zero, in which case return nil
  – else take it as the digit to translate the “head” letter to
  – if we have any letters left, recurse using the rest of the digits and puzzle-letters
  – else see if the puzzle (which should now be all digits) evaluates to true or false (using Code.eval_string); if false, return nil, else I’ve tried both building the map on the way “down” when recursing and on the way back “up” when finishing up after finding the correct solution

The second one is to use a stream to create all possible digit subsets of the correct length, and check one at a time whether they solve it. This turned out to be about 4x faster on the small ones (like up to four unique letters), and I don’t have reliable timing on the larger ones, but the code is large enough that I’m thinking there must be a much more elegant way, both more efficient and more compact. This version is currently visible at Exercism (I didn’t submit the first one but have it in Git if you want to look).

I do not want to take all the time to build in the human-like smarts to figure out “this digit plus that one equals the other one so this one can’t be whatever” and keep track of all that; it seems like a semi-smart brute force solution should be good enough here.

Any clues, or at least ideas? Thanks!