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) `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.

2 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?

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="">