§Problem

Find the max and min of sum of all permutations of [1…9] satisfying the following condition:

1
2
3
4
5
6
sum
== a[1] + a[2] + a[3]
== a[3] + a[4] + a[5]
== a[5] + a[6] + a[7]
== a[7] + a[8]
where sum = a[0] + a[1]

One permutation satisfying that condition is a = [9,4,1,8,3,2,5,6,7], and sum is 13.

§Solution

Originally, I thought I need some kind of constraint programming, but the problem size is small enough that I can brute-force it… The complete code looks fairly succinct.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import Data.List

candidates = permutations [1..9]

predicate list =
  and $
    [ sum == (list !! 1 + list !! 2 + list !! 3)
    , sum == (list !! 3 + list !! 4 + list !! 5)
    , sum == (list !! 5 + list !! 6 + list !! 7)
    , sum == (list !! 5 + list !! 6 + list !! 7)
    , sum == (list !! 7 + list !! 8)
    ]
      where sum = get_sum list

get_sum list = list !! 0 + list !! 1

main =
  mapM_ print $ map ((,) <$> id <*> get_sum) $ filter predicate candidates
-- output:
-- ([8,3,7,1,6,4,5,2,9],11)
-- ([7,6,5,2,3,8,1,4,9],13)
-- ([5,9,2,3,4,7,1,6,8],14)
-- ([9,2,5,4,6,1,7,3,8],11)
-- ([9,4,1,8,3,2,5,6,7],13)
-- ([4,9,1,3,8,2,5,6,7],13)
-- ([7,6,5,2,8,3,1,9,4],13)
-- ([8,6,1,7,4,3,2,9,5],14)