4

私はPrologを使用して覆面算パズルを解くように頼まれました：

GIVE
* ME 
------
MONEY

上記はパズルです。どこに問題があるのか​​わかりません。結果は常にfalseを返します。さらに、SWI-Prologでライブラリを使用することは許可されていません。

solve(Z) :-
    assign(Z,[0,1,2,3,4,5,6,7,8,9]),
    check(Z).

find( VAL , G,I,V,E  ) :- VAL  is G * 1000 + I * 100 + V * 10 + E.
find2(VALR, M,E      ) :- VALR is M * 10 + E.
find3(VALA, M,O,N,E,Y) :- VALA is M * 10000 + O * 1000 + N * 100 + E * 10 + Y.

check(Z) :- 
    G #>= 1, 
    M #>= 1,
    find( VAL,  G,I,V,E), 
    find2(VALR, M,E), 
    find3(VALA, M,O,N,E,Y), 
    VAL * VALR =:= VALA.

assign(Z,L) :-
    permute(L,Z).

/* permute is similar to all_different in swi-prolog */
addany(X,K,[X|K]).
addany(X,[F|K],[F|L1]) :-
    addany(X,K,L1).

permute([],[]).
permute([X|K],P) :- 
    permute(K,L1),
    addany(X,L1,P).

サンプルクエリ：

?- solve([G,I,V,E,M,O,N,Y]).
false.                          % fails unexpectedly
4

2 に答える 2

2

問題の核心に迫りましょう！

  • のすべての順列 は、長さ10[0,1,2,3,4,5,6,7,8,9]のリストです。
  • [G,I,V,E,M,O,N,Y]長さ8のリストです。
  • の順列は[0,1,2,3,4,5,6,7,8,9]で統一できません[G,I,V,E,M,O,N,Y]。

簡単な修正として、次のcheck/1ように定義を調整します。

check（[G、I、V、E、M、O、N、Y、_、_]）：-
   find（VAL、G、I、V、E）、
   G> = 1、
   find2（VALR、M、E）、
   M> = 1、
   find3（VALA、M、O、N、E、Y）、
   VAL * VALR =：=VALA。

次に、次の「固定」クエリを実行します。

？-Expr =（[G、I、V、E] * [M、E] = [M、O、N、E、Y]）、
   Zs = [G、I、V、E、M、O、N、Y、_、_]、
   time（solve（Zs））。
％24,641,436推論、7.709秒で7.692 CPU （ 100％CPU、3203506リップ）
Expr =（[1,0,7,2] * [9,2] = [9,8,6,2,4]）、Zs 
= [1,0,7,2,9,8,6,4、3,5 ];
％7,355推論、0.007秒で0.007 CPU（100％CPU、1058235リップ）
Expr =（[1,0,7,2] * [9,2] = [9,8,6,2,4]）、％冗長
Zs = [1,0,7,2,9,8,6 、4、5、3 ];
％6,169,314推論、1.939秒で1.935 CPU（100％CPU、3188312リップ）
Expr =（[1,0,9,2] * [7,2] = [7,8,6,2,4]）、Zs 
= [1,0,9,2,7,8,6,4、3,5 ];
％7,355推論、0.005秒で0.005 CPU（99％CPU、1360603リップ）
Expr =（[1,0,9,2] * [7,2] = [7,8,6,2,4]）、％冗長
Zs = [1,0,9,2,7,8,6 、4、5、3 ];
％6,234,555推論、1.959秒で1.955 CPU（100％CPU、3189462リップ）
false。

問題を解決する別の方法は次のとおりです。

まず、を使用してください！

:- use_module(library(clpfd)).

第二に、関連する質問への私の答えの前半で提示されたコードを（再）使用するPrologでの覆面算のより速い実装：

？-Expr =（[G、I、V、E] * [M、E]＃= [M、O、N、E、Y]）、
   Zs = [G、I、V、E、M、O、N、Y]、
   crypt_arith_（Expr、Zs）、
   time（labeling（[]、Zs））。
％397,472推論、0.088秒で0.088 CPU（100％CPU、4521899リップ）
Expr =（[1,0,7,2] * [9,2]＃= [9,8,6,2,4]）、Zs = [1,0,7,2,9,8,6、 4];
％128,982推論、0.037秒で0.037 CPU（100％CPU、3502788リップ）
Expr =（[1,0,9,2] * [7,2]＃= [7,8,6,2,4]）、Zs = [1,0,9,2,7,8,6、 4];
％77,809推論、0.028秒で0.028 CPU（100％CPU、2771783リップ）
false。

冗長なソリューションはありません。「生成とテスト」よりも桁違いに高速です。ロック！

于 2015-08-12T18:27:08.847 に答える
0

エリック・ワイスタインとエド・ペグによる次の記事が役に立ちます。Mathematicaの同様の問題に対していくつかの解決策を提供します。

非常に力ずくのアプローチを使用すると、2つの解決策があります：1072 * 92 = 98624と1092 * 72 = 78624。私が使用したコード：

In[16]:= Cases[
 Permutations[
  Range[0, 9], {5}], {g_, i_, v_, e_, m_} /; g > 0 && m > 0 :> 
  With[{dig = IntegerDigits[(g*10^3 + i*10^2 + v*10 + e) (10 m + e)]},
   Join[{g, i, v, e, m}, dig[[{2, 3, 5}]]] /; 
    And[Length[dig] == 5, Unequal @@ dig, dig[[{1, 4}]] == {m, e}, 
     Intersection[dig[[{2, 3, 5}]], {g, i, v, e, m}] === {} ]
   ]]

Out[16]= {{1, 0, 7, 2, 9, 8, 6, 4}, {1, 0, 9, 2, 7, 8, 6, 4}}
于 2011-04-17T20:52:38.683 に答える