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

雖說『直覺自明』的事物容易理解,然而有時卻會失於浮面,不能夠深入內蘊。以致於對某些典型問題不易給『嚴密』的描述,難以用『邏輯』來處理。舉例說所謂的『覆面算

覆面算是用英文字母(亦可以是方塊字或符號)來取代 0 至 9 的數字,要求玩者找回那些字母代表的數字的趣題形式。 

是一種有『約束條件』的『方程式』求解。通常這類問題一聽就懂 ,卻因有太多的變數框住,不好求解。維基百科『語詞算術』

Verbal arithmetic

Verbal arithmetic, also known as alphametics, cryptarithmetic, crypt-arithmetic, cryptarithm or word addition, is a type of mathematical game consisting of a mathematical equation among unknown numbers, whose digits are represented by letters. The goal is to identify the value of each letter. The name can be extended to puzzles that use non-alphabetic symbols instead of letters.

The equation is typically a basic operation of arithmetic, such as addition, multiplication, or division. The classic example, published in the July 1924 issue of Strand Magazine by Henry Dudeney,[1] is:

\begin{matrix}<br />      &   & \text{S} & \text{E} & \text{N} & \text{D} \\<br />    + &   & \text{M} & \text{O} & \text{R} & \text{E} \\<br />  \hline<br />    = & \text{M} & \text{O} & \text{N} & \text{E} & \text{Y} \\<br /> \end{matrix}

The solution to this puzzle is O = 0, M = 1, Y = 2, E = 5, N = 6, D = 7, R = 8, and S = 9.

Traditionally, each letter should represent a different digit, and (as in ordinary arithmetic notation) the leading digit of a multi-digit number must not be zero. A good puzzle should have a unique solution, and the letters should make up a phrase (as in the example above).

Verbal arithmetic can be useful as a motivation and source of exercises in the teaching of algebra. ……

詞條所舉的『亨利‧杜德耐』Henry Dudeney 於一九二四年,在 Strand Magazine 所發表的『SEND + MORE = MONEY』就是經典的例子。既然 pyDatalog 是一種『宣告式編程』,就讓我們開個專題研究一下如何用 pyDatalog 來寫『約束編程』

Constraint programming

In computer science, constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties of a solution to be found. This makes constraint programming a form of declarative programming. The constraints used in constraint programming are of various kinds: those used in constraint satisfaction problems (e.g. “A or B is true”), those solved by the simplex algorithm (e.g. “x ≤ 5″), and others. Constraints are usually embedded within a programming language or provided via separate software libraries.

Constraint programming can be expressed in the form of constraint logic programming, which embeds constraints into a logic program. This variant of logic programming is due to Jaffar and Lassez, who extended in 1987 a specific class of constraints that were introduced in Prolog II. The first implementations of constraint logic programming were Prolog III, CLP(R), and CHIP.  ……

之程式,希望能加深讀者對 pyDatalog 語言及應用的了解。

如果考之以歷史,或許最早的『語詞算術』,可能源於中國古代的『天元術』︰

在中國數學史上最早創立天元概念的是北宋平陽蔣周所著的《益古集》,隨後有博陸李文一撰《照膽》,鹿泉石信道撰《鈐經》,平水劉汝諧撰《如積釋鎖》,處州李思聰《洞淵九容》後人才知道有天元。

李冶在東平獲得劉汝諧撰《如積釋鎖》,書中用十九個單字表示未知數的各個x^9x^-9的冪:

仙、明、霄、漢、壘、層、高、上、天、人、地、下、低、減、落、逝、泉、暗、鬼;其中立天元在上。

後來有太原彭澤彥出,反其道而行,以天元在下[2]

《益古集》,《照膽》,《鈐經》,《如積釋鎖》,《洞淵九容》等早期天元術著作今已失傳。李冶在《測圓海鏡》中使用天元在上的天元術。後來李冶又著《益古演段》,採用天元在下的次序。朱世傑四元玉鑒》和《算學啟蒙》卷下也採用天元在下的次序。

 

Wylie_on_Tian_Yuen

 

在天元術中,一次項係數旁記一「元」字(或在常數項旁記一「太」字)。

歷史上有兩種次序:
《測圓海鏡》式

「元」以上的係數表示各正次冪,「元」以下的係數表示常數項和各負次冪)。

例:李冶《測圓海鏡》第二卷第十四問方程:-x^2-680x+96000=0

Counting rod v-1.png
Counting rod h6.pngCounting rod h-8.pngCounting rod 0.png
Counting rod v9.pngCounting rod h6.pngCounting rod 0.pngCounting rod 0.pngCounting rod 0.png
《益古演段》式

「元」以下的係數表示各正次冪,「元」以上的係數表示常數和各負次冪

例一:

李冶益古演段》卷中第三十六問中的方程=3x^2+210x-20325 用天元術表示為:

 

Counting rod v2.pngCounting rod 0.pngCounting rod v-3.pngCounting rod h2.pngCounting rod v5.png

Counting rod v2.pngCounting rod h1.pngCounting rod 0.png 元(x)

Counting rod v3.pngx^2項)

 

其中「太」是常數項,算籌Counting rod v3.png 打斜線表示該項常數為負數。 「元」相當於未知數x

 

對於東方早期古典『高階方程式論』有興趣之讀者,也許可以讀讀金代數學家李冶所著『測圓海鏡』,體會一下不同的『思路』。或將可以感受『符號學』的發展對於『數理邏輯』的貢獻,了解有時理解的難易就藏在『記號法』之中,畢竟『符號』也能有『美學』的吧!!