haskell backtracking with integer

Question

I am a Haskell newbie. So, I would like to ask a simple question.

I have to find with help of backtracking the (unique) number containing 9 numbers with the following characteristics:

The numbers 1/9 appear exactly once.

The first k numbers of n are divisible by k for k runs from 1/9

Example

n = 123456789 1 (the first number of n) should be divisible by 1. true! 2 (the first 2 numbers of n) should be divisible by 2. true! 3 (the first 3 numbers of n) should be divisible by 3. true! 4 (the first 4 numbers of n) should be divisible by 4. false!

So, 123456789 is not the desired number.

Though I don't know haskell. But [This Link](https://puzzling.stackexchange.com/questions/3017/10-digit-number-where-first-n-digits-are-divisible-by-n) might be helpful to you because it gives answer to same problem. There are multiple answers and both answer will help you because one is from algorithmic point of view and another is from programming point of view.. — Chirag, May 16 '17 at 11:06
Yeah, I know C but don't know haskel. So by interpreting that `C` code you'll have to convert it into haskel. Sorry For that. — Chirag, May 16 '17 at 11:14
(I'd prefer distinction between *number* and *digit*, with a mention of *decimal*.) — greybeard, May 16 '17 at 20:27

score 0 · Answer 1 · answered Jun 14 '17 at 22:52

Here is the solution:

module Main where

import Data.Maybe
import Data.Set (Set)
import qualified Data.Set as Set

findUniqueNumber :: Int -> Int -> Set Int -> Maybe Int
findUniqueNumber currNum divisor remDigits
  | divisor == 9 && currNum `rem` divisor == 0 = Just currNum
  | divisor > 0 && currNum `rem` divisor /= 0  = Nothing
  | otherwise                                  =
    case filter isJust posNums of
       []             -> Nothing
       [uniqueNumber] -> uniqueNumber
    where
        posNums   = map posAns (Set.toList remDigits)
        posAns d' = findUniqueNumber (currNum * 10 + d') (divisor + 1) (Set.delete d' remDigits)

main :: IO ()
main = (print . fromJust) $ findUniqueNumber 0 0 (Set.fromList [1..9])

score 0 · Accepted Answer · answered Jun 19 '17 at 14:57

uniekGetal :: [Int]
uniekGetal = [val9 | 
        x1 <- [1..9],
        let val = x1,
        x2 <- [x| x <- [1..9], x /= x1],
        let val2 = val * 10 + x2,
        mod val2 2 == 0,
        x3 <- [x| x <- [1..9], x /= x1, x /= x2],
        let val3 = val2 * 10 + x3,
        mod val3 3 == 0,
        x4 <- [x| x <- [1..9], x /= x1, x /= x2, x /= x3],
        let val4 = val3 * 10 + x4,
        mod val4 4 == 0,
        x5 <- [x| x <- [1..9], x /= x1, x /= x2, x /= x3, x /= x4],
        let val5 = val4 * 10 + x5,
        mod val5 5 == 0,
        x6 <- [x| x <- [1..9], x /= x1, x /= x2, x /= x3, x /= x4, x /= x5],
        let val6 = val5 * 10 + x6,
        mod val6 6 == 0,
        x7 <- [x| x <- [1..9], x /= x1, x /= x2, x /= x3, x /= x4, x /= x5, x /= x6],
        let val7 = val6 * 10 + x7,
        mod val7 7 == 0,
        x8 <- [x| x <- [1..9], x /= x1, x /= x2, x /= x3, x /= x4, x /= x5, x /= x6, x /= x7],
        let val8 = val7 * 10 + x8,
        mod val8 8 == 0,
        x9 <- [x| x <- [1..9], x /= x1, x /= x2, x /= x3, x /= x4, x /= x5, x /= x6, x /= x7, x /= x8],
        let val9 = val8 * 10 + x9,
        mod val9 9 == 0]

this was the solution to my problem.

haskell backtracking with integer

2 Answers2