backtracking.rb

require 'continuation'

@cc = []

def backtrack(*choices)
  if @cc.empty?
    raise
  else
    @cc.pop.call
  end
end

def amb(*choices)
  backtrack if choices.empty?

  choices.each do |choice|
    callcc do |cc|
      @cc << cc
      return choice
    end
  end

  backtrack
end

# s = amb(1, 2, 3, 4, 5, 6, 7, 8, 9)
# m = amb(1, 2, 3, 4, 5, 6, 7, 8, 9)
# e = amb(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
# n = amb(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
# d = amb(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
# o = amb(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
# r = amb(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)
# y = amb(1, 2, 3, 4, 5, 6, 7, 8, 9, 0)

choices = [*1..9, 0]

s = amb(*(choices - [0]))
m = amb(*(choices - [0, s]))
e = amb(*(choices - [s, m]))
n = amb(*(choices - [s, m, e]))
d = amb(*(choices - [s, m, e, n]))
o = amb(*(choices - [s, m, e, n, d]))
r = amb(*(choices - [s, m, e, n, d, o]))
y = amb(*(choices - [s, m, e, n, d, o, r]))

constraint = [s, e, n, d, m, o, r, y].uniq.size == 8 && \
  "#{s}#{e}#{n}#{d}".to_i + "#{m}#{o}#{r}#{e}".to_i == "#{m}#{o}#{n}#{e}#{y}".to_i

amb unless constraint

puts  "#{s}#{e}#{n}#{d} + #{m}#{o}#{r}#{e} == #{m}#{o}#{n}#{e}#{y}"

$ time ruby backtracking.rb 
9567 + 1085 == 10652
ruby backtracking.rb  8.00s user 0.05s system 99% cpu 8.089 total