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 :

(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) == 0step 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?

I noticed that since the number always had to be even when there were 2, 4, 6, or 8 digits in it, that meant the digits in positions 2,4,6,8 had to be even and the other digits had to be odd. That means instead of 9! permutations of digits there were only 4!*5! = 2880 permutations to consider, so it was easy to enumerate those with Data.List(permutations) and that runs very fast. It turns out simple brute force search is also fast, about 160 msec on my laptop:

import Data.List

check ds = all check’ (inits ds)

check’ ds = n

`rem`

s==0 wheren = foldl’ (\n d -> 10*n+d) 0 ds

s = length ds

`max`

1main = print . filter check . permutations $ [1..9]

Here is the efficient version (rewritten from my first one):

import Data.List

check ds = all check’ (inits ds) where

check’ ds = n

`rem`

s==0 wheren = foldl’ (\n d -> 10*n+d) 0 ds

s = length ds

`max`

1main = print . filter check . map interleave . sequence $ [po,pe] where

po = permutations [1,3,5,7,9]

pe = permutations [2,4,6,8]

interleave [[a,b,c,d,e],[w,x,y,z]] = [a,w,b,x,c,y,d,z,e]