haskell 整数回溯

Question

我是 Haskell 新手。所以，我想问一个简单的问题。

我必须在回溯的帮助下找到包含 9 个具有以下特征的数字的（唯一）数字：

The numbers 1/9 appear exactly once.

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

例子

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!

所以，123456789 不是想要的号码。

Answer 1

解决方法如下：

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])

Answer 2

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]

这是我的问题的解决方案。

haskell 整数回溯

haskell backtracking with integer

algorithm

haskell

functional-programming

backtracking