I was led from here to here to here, and got intrigued by the 9-digit problem. Here is the description, copied verbatim from here :

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

- The number should be divisible by 9.
- If the rightmost digit is removed, the remaining number should be divisible by 8.
- If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
- And so on, until there’s only one digit (which will necessarily be divisible by 1).

There are solutions in many languages in those webpages, but I wanted to write my own in Haskell, just for kicks. Here it is :

thelist = [1..9]

check [] = False

check xs = (foldl (\x -> \y -> 10*x+y) 0 xs) `mod` (length xs) == 0

onemore [] = [[x] | x <- thelist]

onemore list = [list ++ [l] | l<-thelist,elem l list == False, check (list ++ [l]) == True]

testmore [] = []

testmore (x:xs) = (onemore x) ++ (testmore xs)

result = foldl (.) id (replicate 8 testmore) (onemore [])

check [] = False

check xs = (foldl (\x -> \y -> 10*x+y) 0 xs) `mod` (length xs) == 0

onemore [] = [[x] | x <- thelist]

onemore list = [list ++ [l] | l<-thelist,elem l list == False, check (list ++ [l]) == True]

testmore [] = []

testmore (x:xs) = (onemore x) ++ (testmore xs)

result = foldl (.) id (replicate 8 testmore) (onemore [])

Here is another version in Haskell, just for comparison.

That’s so complicated! Here’s mine.

a `divides` b = (b `mod` a) == 0

step iter (avail, prev) =

let options = [(delete x avail, prev*10 + x) | x concatMap $ step i)

[([1..9], 0)] $

reverse [1..psize]

concatMap is from Data.List and is simply

concatMap f a = concat $ map f a

At each step, generate the list of results for the possible choices. A result consists of the new complete number as well as the digits remaining. Then simply repeat this for the steps 1 through problem size, generating lists of results for every possible starting point and concatenating them.

Haskell being lazy, when you do a head $ solve 9, it should effectively do a linear search, cutting off the search whenever an early condition is not met.

I am a little slow on the uptake, but can you please show the complete working example?