プロジェクトオイラー Problem 43 「部分列被整除性」 †

Problem 43 「部分列被整除性」 †

数1406357289は0から9のパンデジタル数である (0から9が1度ずつ現れるので). この数は部分列が面白い性質を持っている.

d1を1桁目, d2を2桁目の数とし, 以下順にdnを定義する. この記法を用いると次のことが分かる.

• d2d3d4=406 は 2 で割り切れる
• d3d4d5=063 は 3 で割り切れる
• d4d5d6=635 は 5 で割り切れる
• d5d6d7=357 は 7 で割り切れる
• d6d7d8=572 は 11 で割り切れる
• d7d8d9=728 は 13 で割り切れる
• d8d9d10=289 は 17 で割り切れる

このような性質をもつ0から9のパンデジタル数の総和を求めよ.

解法
手前から全探索しても探索空間が狭いので何の問題もありません。

search2(_,[],[],Num,Num):-!.
search2([D1,D2],List,[Prime|Primes],Num,Result):-
      select(D3,List,List1),
      N is D1*100+D2*10+D3,
      N mod Prime=:=0,
      Num1 is Num*10+D3,
      search2([D2,D3],List1,Primes,Num1,Result).

search(Num1):-
      select(D1,[1,2,3,4,5,6,7,8,9],List),
      List1=[0|List],
      Primes=[2,3,5,7,11,13,17],
      select(D2,List1,List2),
      select(D3,List2,List3),
      Num=D1*100+D2*10+D3,
      search2([D2,D3],List3,Primes,Num,Num1).

sum([],0):-!.
sum([X|Xs],Result):-
      !,
      sum(Xs,Re),
      Result is Re+X.
main43:-
      findall(E,search(E),AnsList),
      sum(AnsList,Ans),
      write(Ans).