自分がPrologの勉強のために参考にしているM.Hiroiさんのページで掲載されている小町算の問題を、広井さんの解法とは異なり制約論理プログラミングと最近勉強したDCGを使用して解いてみました。
(参照：http://www.geocities.jp/m_hiroi/prolog/prolog14.html)
問題：
小町算
1 から 9 までの数字を順番に並べ、間に + と – を補って 100 になる式を作ってください。
例：1 + 2 + 3 – 4 + 5 + 6 + 78 + 9 = 100
プログラム
|
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 28 29 |
:-use_module(library(clpfd)). solve_komachi:- phrase(komachi(RetNumList),[1,2,3,4,5,6,7,8,9],[]), length(RetNumList,Len), length(SignLst,Len), SignLst ins -1\/1, SignLst = [1 | Rest], maplist(mul,RetNumList,SignLst,SignedNumList), sum(SignedNumList,#=,100), label(SignedNumList), write(SignedNumList),nl. mul(A,B,C):- C #= A*B. komachi([])-->[]. komachi([LeftListNum|RestNumList])-->{between(1,9, Len),length(LeftList,Len)},LeftList,{tonum(LeftList,LeftListNum)},komachi(RestNumList). tonum(List,Num):- length(List,Digit), tonum(List,Num,Digit). tonum([Num],Num,1). tonum([First|Rest],Num,Digit):- ThisDigitNum is First * 10 ^(Digit - 1), NextDigit is Digit - 1, tonum(Rest,RestNum,NextDigit), Num is ThisDigitNum + RestNum. |
実行結果
|
1 2 3 4 5 6 7 8 9 10 11 12 |
[7] 35 ?- solve_komachi. [1,2,3,-4,5,6,78,9] [1,2,34,-5,67,-8,9] [1,23,-4,5,6,78,-9] [1,23,-4,56,7,8,9] [12,-3,-4,5,-6,7,89] [12,3,4,5,-6,-7,89] [12,3,-4,5,67,8,9] [123,-4,-5,-6,-7,8,-9] [123,4,-5,67,-89] [123,45,-67,8,-9] [123,-45,-67,89] |