Brute-force solution of arithmetic restoration problem

README

Original problem:

  ab
- cd
----
  ef
+ gh
----
 iii

Result:

~ time ./restore
[[9,0,2,7,6,3,4,8,1],[9,0,6,3,2,7,8,4,1],[8,5,4,6,3,9,7,2,1],[9,5,2,7,6,8,4,3,1],[8,6,5,4,3,2,7,9,1]]

real	0m1.477s
user	0m1.468s
sys	0m0.008s

restore.hs

import Control.Monad
import Data.List

subsets :: Int -> [a] -> [[a]]
subsets 0 _ = [[]]
subsets _ [] = []
subsets n (x:xs) = map (x:) (subsets (n-1) xs) ++ subsets n xs

main = print $ do
  [a, b, c, d, e, f, g, h, i] <-
    [x | y <- subsets 9 [0..9], x <- permutations y]
  guard $ all (/= 0) [a, c, e, g, i]
  guard $ (10*a+b) - (10*c+d) == (10*e+f)
  guard $ (10*e+f) + (10*g+h) == 111*i
  return [a, b, c, d, e, f, g, h, i]