九位不同数字乘法等式的递归与非递归回溯算法（一）

有如下题目：使用集合{1, 2, 3…9}组成形如X×Y=Z的乘法等式，要求在该等式中使用且仅使用集合中的全部数字一次，请列举出所有符合条件的等式．

1  算法分析

计算机算法设计通常采用数学分析或穷举方法，显然该问题属于NP^[1]问题，故采用数学分析算法求解非常困难，而穷举算法求解则成为普遍思路^[2]．实现穷举算法的具体方法有很多，诸如回溯、枚举、全排列等^[3]，本文仅设计、实现了递归与非递归回溯算法．

通过分析题目，首先穷举该集合的所有排列，然后从中找出可构成等式的排列．设9个数字分别为任意的且互不相同的a₁,a₂,a₃,…,a₉，所谓符合条件的等式其实是在排列：a₁a₂a₃a₄a₅a₆a₇a₈a₉中找到可使等式成立的乘号、等号的位置，即确定两个因子的数字位数．若因子X为1位数字时，则因子Y一定为4位数字，积Z才可能为4位数字；若因子X为2位数字时，则因子Y一定为3位数字，积Z才可能为4位数字；其他情形中除了使用乘法交换率得到的两组等价表达不做统计外，剩余的因为其积均超出（例如3位数字乘3位数字，积至少为5位数字）或不足（例如2位数字乘2位数字，积至多为4位数字）等式要求，故不成立，即等式一定为以下两种情形：

     a₁×a₂a₃a₄a₅=a₆a₇a₈a₉         ⑴

     a₁a₂×a₃a₄a₅=a₆a₇a₈a₉         ⑵

式⑴表示为：

(a₁×10⁰)×(a₂×10³+a₃×10²+a₄×10¹+a₅×10⁰)=

(a₆×10³+a₇×10²+a₈×10¹+a₉×10⁰)       ⑶

式⑵表示为：

(a₁×10¹+a₂×10⁰)+(a₃×10²+a₄×10¹+a₅×10⁰)=

(a₆×10³+a₇×10²+a₈×10¹+a₉×10⁰)        ⑷

因此，搜索符合条件的排列，即判定每一组排列能否使式⑶、⑷成立．

2  判定算法

建立一维数组r[1,…,9]，共9个元素，存放a₁,a₂,a₃,…,a₉构成的一组排列，下面的函数判定该排列是否符合要求．

1. type TArr=array[1..9] of integer;  
2. function TestArr(var r:TArr):boolean;  
3. var  
4.   f1, f2, f3, f4, m:integer;  
5. begin 
6.   f1:= r[1];  
7.   f2:= r[2]*1000+r[3]*100+r[4]*10+r[5];  
8.   f3:= r[1]*10+r[2];  
9.   f4:= r[3]*100+r[4]*10+r[5];  
10.   m:= r[6]*1000+r[7]*100+r[8]*10+r[9];  
11.   if f1 * f2 = m then 
12.   begin 
13.     OutResult(f1, f2);  
14.     result:= true;  
15.   end 
16.   else if f3 * f4 = m then 
17.   begin 
18.     OutResult(f3, f4);  
19.     result:= true;  
20.   end 
21.   else 
22.     result:= false;  
23. end; 

函数TestArr测试数组r中存放的一组排列，如果此排列符合要求，则函数返回“真”，否则返回“假”．其中局部变量f1和f2表示式⑶中的两个因子，f3和f4表示式⑷中的两个因子，m表示式⑶及式⑷中相同的积．函数OutResult用来输出一组符合要求的排列，即一组解．

只要能穷举集合{1, 2, 3,…,9}的所有排列，然后将每一组排列送入判定算法验证是否符合要求，问题便得解．因此，下文将讨论实现穷举该集合所有排列的两种算法．

（未完待续……）