Solving Samurai Sudoku with CLP

From sasCommunity

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

/* Sudoku: 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. */

/* Samurai Sudoku: five Sudoku puzzles, with the middle puzzle
sharing a corner 9-box square with each of the other four. */

/* specify input matrices in dense format, with missing values for empty boxes */
/* puzzle 5 is the middle puzzle */
data indata1;
   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;
2 . . . . 9 . . 1
4 8 . . 3 . . . 2
. . 7 . . . 8 . .
. 6 . 9 . 7 . 1 .
. . 1 3 . . 6 . .
. 7 . 2 . . . 5 .
. . 5 . . . . . .
9 1 . . 7 . . . .
. . . . . 2 . . .
;
run;

data indata2;
   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 . . 2 . . . . 9
6 . . . 8 . . 3 5
. . 7 . . . 4 . .
. 3 . 9 . 2 . 6 .
. . 6 . . 3 9 . .
. 1 . . . 6 . 4 .
. . . . . . 3 . .
. . . . 9 . . 7 2
. . . 1 . . . . .
;
run;

data indata3;
   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;
. . . . . 9 . . .
4 1 . . 2 . . . .
. . 8 . . . . . .
. 4 . 5 . . . 1 .
. . 1 8 . . 2 . .
. 8 . 2 . 1 . 6 .
. . 3 . . . 1 . .
8 9 . . 1 . . . 3
1 . . . . 3 . . 5
;
run;

data indata4;
   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;
. . . 4 . . . . .
. . . . 7 . . 5 9
. . . . . . 6 . .
. 6 . . . 4 . 9 .
. . 4 . . 2 8 . .
. 8 . 5 . 7 . 3 .
. . 1 . . . 9 . .
4 . . . 9 . . 7 1
8 . . 1 . . . . 3
;
run;

data indata5;
   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;
. . . 2 . 4 . . .
. . . . 8 . . . .
. . . . . . . . .
. . . 5 . 7 . . .
. . 2 . . . 9 . .
. . . 6 . 8 . . .
. . . . . . . . .
. . . . 4 . . . .
. . . 1 . 2 . . .
;
run;


%macro overlap(p1,i1,j1,p2,i2,j2);
   %do i = 0 %to 2;
      %do j = 0 %to 2;
         lincon X_&p1._%eval(&i1+&i)_%eval(&j1+&j) = X_&p2._%eval(&i2+&i)_%eval(&j2+&j);
      %end;
   %end;
%mend overlap;


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


/* call clp to solve Sudoku */
proc clp out=outdata varselect=maxc;
   %do p = 1 %to 5;
      /* row constraints */
      %do i = 1 %to 9;
         /* X_p_i_j is value in puzzle p, box (i,j) */
         var (X_&p._&i._1-X_&p._&i._9) = [1,9];
         alldiff(X_&p._&i._1-X_&p._&i._9);
      %end;
      /* column constraints */
      %do j = 1 %to 9;
         alldiff(
         %do i = 1 %to 9;
            X_&p._&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_&p._&i._&j
               %end;
            %end;
            );
         %end;
      %end;
      /* X_p_i_j = C_p_i_j if C_p_i_j is non-missing */
      %do i = 1 %to 9;
         %do j = 1 %to 9;
            %if &&C_&p._&i._&j ne . %then %do;
               lincon X_&p._&i._&j = &&C_&p._&i._&j;
            %end;
         %end;
      %end;
   %end;
   /* overlap constraints */
   %overlap(1,7,7,5,1,1);
   %overlap(2,7,1,5,1,7);
   %overlap(3,1,7,5,7,1);
   %overlap(4,1,1,5,7,7);
run;
%put &_ORCLP_;


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


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


%solve;