9 Digit Problem in Haskell

Posted by & filed under haskell, programming.

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:

  1. The number should be divisible by 9.
  2. If the rightmost digit is removed, the remaining number should be divisible by 8.
  3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
  4. 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) <code>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.

4 Responses to “9 Digit Problem in Haskell”

  1. Sebastian

    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.

  2. Manjunath

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

  3. none

    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 = nrems==0 where
    n = foldl’ (\n d -> 10*n+d) 0 ds
    s = length ds max 1

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

  4. none

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

    import Data.List

    check ds = all check’ (inits ds) where
    check’ ds = nrems==0 where
    n = foldl’ (\n d -> 10*n+d) 0 ds
    s = length ds max 1

    main = 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]

Leave a Reply

  • (will not be published)

XHTML: You can use these tags: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">