数独问题SAS/OR求解

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

利用PROC CLP求解数独问题.
Translated From SAS HELP........
CLP过程简介：
解决CSP（约束满足问题），即由一个变量集合和一个约束集合组成。问题的一个状态是由对一些或全部变量的一个赋值定义的完全赋值：每个变量都参与的赋值。问题的解是满足所有约束的完全赋值，或更进一步，使目标函数最大化。

var 语句：声明变量的定义域：例如：variable <=[lower-bound <, upper-bound>]>
alldiff语句：互不相等条件，约束输入变量必须为互不相等的变量
如：var (X1-X3) A B;  alldiff (X1-X3) (A B); 等价于：X1 ne X2，X2 ne X3 ，X3 ne X1 and A ne B

lincon语句：线性约束,例如：lincon 4 * x1 - 3 * x2 = 5;

有如下数独问题（以下代码需在SAS9.3版本或以上方可运行成功）



1.输入数独矩阵：

1. data indata;
   
2.    input C1-C9;
   
3.    datalines;
   
4. . . 5 . . 7 . . 1
   
5. . 7 . . 9 . . 3 .
   
6. . . . 6 . . . . .
   
7. . . 3 . . 1 . . 5
   
8. . 9 . . 8 . . 2 .
   
9. 1 . . 2 . . 4 . .
   
10. . . 2 . . 6 . . 9
    
11. . . . . 4 . . 8 .
    
12. 8 . . 1 . . 5 . .
    
13. ;
    
14. run;     

复制代码

2.将数独矩阵赋值给宏变量C_1_1至C_9_9

1. %macro store_initial_values;
   
2.    /* 储存初值到宏变量C_i_j */
   
3.    data _null_;
   
4.       set indata;
   
5.       array C{9};
   
6.       do j = 1 to 9;
   
7.          i = _N_;
   
8.          call symput(compress('C_'||put(i,best.)||'_'||put(j,best.)),
   
9.             put(C[j],best.));
   
10.       end;
    
11.    run;
    
12. %mend store_initial_values;
    
13. 
    
14. %store_initial_values;

复制代码

3.利用CLP过程求解数独问题

1. %macro solve;
   
2.    proc clp out=outdata;
   
3. 
   
4. /* VAR 语句 声明求解变量X_1_1至X_9_9  取值范围为[1,9]    */     
   
5. /* alldiff语句：约束条件：行约束，每行元素互不相同，如X_1_1:X_1_9的取值互不相同*/
   
6.       %do i = 1 %to 9;
   
7.          var (X_&i._1-X_&i._9) = [1,9];
   
8.          alldiff(X_&i._1-X_&i._9);
   
9.       %end;
   
10. 
    
11.     /* alldiff语句：约束条件：列约束，每列元素互不相同，如X_1_1:X_9_1的取值互不相同*/
    
12.       %do j = 1 %to 9;
    
13.          alldiff(
    
14.          %do i = 1 %to 9;
    
15.             X_&i._&j
    
16.          %end;
    
17.          );
    
18.       %end;
    
19. 
    
20.        /* alldiff语句：约束条件：块约束，3X3矩阵元素互不相同，如X_1_1:X_3_3的取值互不相同*/
    
21.       %do s = 0 %to 2;
    
22.          %do t = 0 %to 2;
    
23.             alldiff(
    
24.             %do i = 3*&s + 1 %to 3*&s + 3;
    
25.                %do j = 3*&t + 1 %to 3*&t + 3;
    
26.                   X_&i._&j
    
27.                %end;
    
28.             %end;
    
29.             );
    
30.          %end;
    
31.       %end;
    
32. 
    
33.       /* lincon语句：初值约束，已知变量约束如X_1_3=C_1_3=5   */
    
34.       /* 如果C_i_j非缺失，则X_i_j = C_i_j  */
    
35.       %do i = 1 %to 9;
    
36.          %do j = 1 %to 9;
    
37.             %if &&C_&i._&j ne . %then %do;
    
38.                lincon X_&i._&j = &&C_&i._&j;
    
39.             %end;
    
40.          %end;
    
41.       %end;
    
42. 
    
43.    run;
    
44.    %put &_ORCLP_;
    
45. %mend solve;
    
46.    
    
47. %solve

复制代码

4.输出结果work.outdata
     

本帖曾在论坛引起争议，自知理亏，不辩解。日后SASHELP的东西也注明出处。。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享4 收藏17 回帖

关键词：Translated translate compress Variable Initial 定义域

@.@ 跪拜

ding

。记得SAS官方也提出了一个方法。。。各种数组 各种循环   似乎你这个更好 哈哈哈

http://www.sascommunity.org/wiki/Solving_Sudoku_with_PROC_CLP

原创？

There was one example
http://www2.sas.com/proceedings/forum2007/011-2007.pdf

I believe Zhou Wen's code is more clear than what's in the 6-year-old paper.
However, I still couldn't understand nothing about Sudoku!

google     proc clp sudoku  第一个

膜拜大神