Solving Sudoku with PROC CLP

From sasCommunity

/* Solving Sudoku puzzles with PROC CLP
/* Author: Rob Pratt, SAS/OR

/* Place a number into each box so that each row across, each 
column down, and each small 9-box square within the larger square
(there are 9 of these) will contain every number from 1 through 9. */

/* specify input matrix in dense format, with missing values for empty boxes */
data indata;
   input C1-C9;
   if (_n_=1 | _n_=4 | _n_=7) then put '-------------------------';
   put   '| ' C1 C2 C3 '| ' C4 C5 C6 '| ' C7 C8 C9 '|';
   if (_n_=9) then put '-------------------------'/;
   datalines;
1 . . . . 7 . 9 .
. 3 . . 2 . . . 8
. . 9 6 . . 5 . .
. . 5 3 . . 9 . .
. 1 . . 8 . . . 2
6 . . . . 4 . . .
3 . . . . . . 1 .
. 4 . . . . . . 7
. . 7 . . . 3 . .
;
run;


%macro solve;
/* store each value into macro variable C_i_j */
data _null_;
   set indata;
   array C{9};
   do j = 1 to 9;
      i = _N_;
      call symput(compress('C_'||put(i,best.)||'_'||put(j,best.)), put(C[j],best.));
   end;
run;


/* call clp to solve Sudoku */
proc clp out=outdata;
   /* row constraints */
   %do i = 1 %to 9;
      var (X_&i._1-X_&i._9) = [1,9];
      alldiff(X_&i._1-X_&i._9);
   %end;
   /* column constraints */
   %do j = 1 %to 9;
      alldiff(
      %do i = 1 %to 9;
         X_&i._&j
      %end;
      );
   %end;
   /* 9-box square constraints */
   %do s = 0 %to 2;
      %do t = 0 %to 2;
         alldiff(
         %do i = 3*&s + 1 %to 3*&s + 3;
            %do j = 3*&t + 1 %to 3*&t + 3;
               X_&i._&j
            %end;
         %end;
         );
      %end;
   %end;
   /* X_i_j = C_i_j if C_i_j is non-missing */
   %do i = 1 %to 9;
      %do j = 1 %to 9;
         %if &&C_&i._&j ne . %then %do;
            lincon X_&i._&j = &&C_&i._&j;
         %end;
      %end;
   %end;
run;
%put &_ORCLP_;


/* convert solution to matrix in dense format */
data outdata_dense;
   set outdata;
   array C{9};
   %do i = 1 %to 9;
      %do j = 1 %to 9;
         C[&j] = X_&i._&j;
      %end;
      output;
   %end;
   drop X:;
run;


/* print solution */
data _null_;
   set outdata_dense;
   if (_n_=1 | _n_=4 | _n_=7) then put '-------------------------';
   put   '| ' C1 C2 C3 '| ' C4 C5 C6 '| ' C7 C8 C9 '|';
   if (_n_=9) then put '-------------------------'/;
run;
%mend solve;


%solve;