勇闖新世界︰ 《 pyDatalog 》【專題】之約束編程‧四

假使我們在樹莓派 2B 上,嘗試用『蠻力法』求解『亨利‧杜德耐』Henry Dudeney 於一九二四年,在 Strand Magazine 所發表的『SEND + MORE = MONEY』的問題︰

SendMoreMoney

sol(S,E,N,D,M,O,R,Y) <=

(S.in_(range(1,10))) & (E.in_(range(10))) & (N.in_(range(10))) & (D.in_(range(10))) & (M.in_(range(1,10))) & (O.in_(range(10))) & (R.in_(range(10))) & (Y.in_(range(10))) &

(S != E) &(S != N) & (S != D) & (S != M) & (S != O) & (S != R) & (S !=Y) &
(E != N) & (E != D) & (E != M) & (E != O) & (E != R) & (E != Y) &
(N != D) & (N != M) & (N != O) & (N != R) & (N != Y) &
(D != M) & (D != O) & (D != R) & (D != Y) &
(M != O) & (M != R) & (M != Y) &
(O != R) & (O != Y) &
(R != Y) &

( M == (((S-O)*1000 + (E+O-N)*100 +(N+R-E)*10 + (E+D-Y)) / 9000))

,你將會遭遇到 python3 解譯器『記憶爆炸』的現象。這事可令人覺得驚訝,才八個變元,就把系統搞掛了耶?如果想想搜尋空間有 10^6 \times 9^2 \ = \ 81 M 這麼大,也許那結果就不奇怪的了。這也說明了『分析問題』的重要性。比方說,從直式加法

S + M = MO

條件裡,我們可以得出

M = 1 因 S 或 M 最大是 9 , 即使加上前項的進位也小於 20 之故。

S = 9 ,因已得 M = 1 ,而且 S + M >= 10 之故。

即使我們將這個所知放到 osol 述詞裡︰

osol(S,E,N,D,M,O,R,Y) <=

(S == 9) &

(E.in_(range(10))) & (N.in_(range(10))) & (D.in_(range(10))) &

(M == 1) &

(O.in_(range(10))) & (R.in_(range(10))) & (Y.in_(range(10))) &

(S != E) &(S != N) & (S != D) & (S != M) & (S != O) & (S != R) & (S !=Y) & (E != N) & (E != D) & (E != M) & (E != O) & (E != R) & (E != Y) & (N != D) & (N != M) & (N != O) & (N != R) & (N != Y) & (D != M) & (D != O) & (D != R) & (D != Y) & (M != O) & (M != R) & (M != Y) & (O != R) & (O != Y) & (R != Y) &

( M == (((S-O)*1000 + (E+O-N)*100 +(N+R-E)*10 + (E+D-Y)) / 9000))

,卻依然『記憶體不足』而當掉。如此可以知道 pyDatalog 運算時所需的記憶體之大的了。事實上從上式,我們還可以推知 O = 0 ,因 O != SO != M ,就算進位也只能多 1 之故。加上這個事實後,勉強可以算得了答案︰

 

pi@raspberrypi ~ python3 Python 3.2.3 (default, Mar  1 2013, 11:53:50)  [GCC 4.6.3] on linux2 Type "help", "copyright", "credits" or "license" for more information. >>> from pyDatalog import pyDatalog >>> pyDatalog.create_terms('S,E,N,D,M,O,R,Y,sol')  >>> sol(E,N,D,O,R,Y) <= (E.in_(range(10))) & (N.in_(range(10))) & (D.in_(range(10))) & (O.in_(range(2))) & (R.in_(range(10))) & (Y.in_(range(10))) & (E != 1) & (E !=9) & (E != N) & (E != D) & (E != O) & (E != R) & (E != Y) & (N != 1) & (N != 9) & (N != D) & (N != O) & (N != R) & (N != Y) & (D != 1) & (D != 9) & (D != O) & (D != R) & (D != Y) & (O !=1) & (O !=9) & (O != R) & (O != Y) & (R != 1) & (R != 9) & (R != Y) & (Y !=1) & (Y !=9) & (Y == ((9-O)*1000 + (E+O-N)*100 + (N+R-E)*10 + (D+E) - 9000 )) sol(E,N,D,O,R,Y) <= _pyD_in(E,'['0', '1', '2', '3'  >>> print(sol(E,N,D,O,R,Y)) E | N | D | O | R | Y --|---|---|---|---|-- 5 | 6 | 7 | 0 | 8 | 2 >>>  </pre>    這說明了『分析問題』的好處。假使再添上直式加法裡  <span style="font-family: LinBiolinum_K;">D + E  = [0 | 1] Y</span>  的條件,且用 mod 述詞表達為  Y == mod( (D+E), 10 )  。我們將可以定義一個 deyspace 述詞  <span style="color: #808080;"> deyspace(D,E,Y) <= </span>  <span style="color: #808080;">(D.in_((2,3,4,5,6,7,8))) & </span>  <span style="color: #808080;">(E.in_((2,3,4,5,6,7,8))) & </span>  <span style="color: #808080;">(Y.in_((2,3,4,5,6,7,8))) & </span>  <span style="color: #808080;">(D != E) & (D != Y) & (E != Y) & </span>  <span style="color: #808080;">(Y == mod((D+E),10))</span>  大幅縮小搜尋空間以及提昇程式執行速度。  【參考程式】 <pre class="lang:sh decode:true   ">pi@raspberrypi ~ python3
Python 3.2.3 (default, Mar  1 2013, 11:53:50) 
[GCC 4.6.3] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> from pyDatalog import pyDatalog
>>> pyDatalog.create_terms('S,E,N,D,M,O,R,Y,sol')
>>> def mod(a,b):
...     return a % b
... 
>>> pyDatalog.create_terms('mod')
>>> pyDatalog.create_terms('deyspace')

>>> deyspace(D,E,Y) <= (D.in_((2,3,4,5,6,7,8))) & (E.in_((2,3,4,5,6,7,8))) & (Y.in_((2,3,4,5,6,7,8))) & (D != E) & (D != Y) & (E != Y) & (Y == mod((D+E),10))
deyspace(D,E,Y) <= _pyD_in(D,'['2', '3', '4', '5',
>>> len(deyspace(D,E,Y).data)
24
>>> print(deyspace(D,E,Y))
D | E | Y
--|---|--
8 | 5 | 3
3 | 2 | 5
6 | 8 | 4
2 | 5 | 7
7 | 6 | 3
2 | 6 | 8
6 | 2 | 8
5 | 3 | 8
2 | 3 | 5
8 | 7 | 5
6 | 7 | 3
5 | 2 | 7
2 | 4 | 6
7 | 5 | 2
5 | 7 | 2
7 | 8 | 5
8 | 6 | 4
4 | 3 | 7
3 | 5 | 8
4 | 8 | 2
8 | 4 | 2
5 | 8 | 3
3 | 4 | 7
4 | 2 | 6

>>> sol(E,N,D,R,Y) <= deyspace(D,E,Y) & (N.in_(range(10))) & (R.in_(range(10)))  & (E != N) & (E != R) & (N != 1) & (N != 9) & (N !=0) & (N != D) & (N != R) & (N != Y) & (D != R)  & (R != 1) & (R != 9) & (R != 0) & (R != Y)  & (Y == ((E-N)*100 + (N+R-E)*10 + (D+E) ))
sol(E,N,D,R,Y) <= deyspace(D,E,Y)&_pyD_in(N,'['0',

>>> print(sol(E,N,D,R,Y))
E | N | D | R | Y
--|---|---|---|--
5 | 6 | 7 | 8 | 2
>>> 

 

所以說純靠『蠻力』還是可能不足的,若是『窮舉』加上『智力』力量怕是大的多哩!對於『 語詞方程式 』解題要點有興趣的讀者,可以上網讀讀《  A PRIMER ON CRYPTARITHMETIC 》,相信能有不少的收穫呦。