覆面算ソルバー(足し算限定)

CodeIQ で覆面算の問題が出題されたときに書いたもの。

という形限定。
permutation で数字の順列を生成して、数字を割り当てた式を eval で評価すれば短く書けるが、それだと結構遅いから、下から一桁ずつ調べるようにした。

言語は Ruby。
最後の行の 'SEND + MORE = MONEY' のところを適当に書き換えて使用。
不正な入力にはほとんど対応していない。

class Alphametic
  def initialize(problem)
    puts @problem = problem
    terms = @problem.gsub(/\s/, '').reverse.split(/[+=]/)
    @n_solutions = 0
    if terms[0].size >= terms.map {|t| t.size}.max then
      # l が頭に来る文字のとき @leading[l] == true
      @leading = {}
      terms.each {|t| @leading[t[-1]] = true}
      # 下から数えた桁を p として
      # @letters[p] : 下の桁から見ていったとき、p桁目で初めて出現する文字の集合
      # @x[p] : p桁目で満たすべき(下の)方程式に現れる文字
      # @x[p][0] == @x[p][1] + @x[p][2] + … + 下の桁からの繰り上がり
      @letters = []
      @x = []
      terms[0].size.times do |place|
        @letters[place] = []
        @x[place] = []
        terms.each do |term|
          l = term[place]
          @letters[place] << l if l && !@letters.flatten.member?(l)
          @x[place] << l if l
        end
      end
      search(0, {}, (0..9).to_a, 0)
    end
    print 'n_solutions = ', @n_solutions
  end

  # 下の桁から数字を割り当てて再帰的に解いていく
  # place : 着目している桁
  # value : value[letter] は文字 letter に割り当てられた値
  # digits : まだ割り当てられていない数字の集合
  # carry : 下の桁からの繰り上がり
  def search(place, value, digits, carry)
    letters, x = @letters[place], @x[place]
    if letters then
      digits.permutation(letters.size) do |perm|
        letters.each_with_index {|letter, idx| value[letter] = perm[idx]}
        sum = carry
        sum += x[1..-1].map {|l| value[l]}.inject(:+) if x.size > 1
        # この段階で式が成立していないときと、頭に来る文字が 0 のときは枝刈り
        next if sum % 10 != value[x[0]] ||
        letters.index {|letter| value[letter] == 0 && @leading[letter]}
        search(place + 1, value, digits - perm, sum / 10)
      end
    elsif carry == 0 then
      puts @problem.gsub(/\w/, value)
      @n_solutions += 1
    end
  end
end

Alphametic.new('SEND + MORE = MONEY')