As the first step in the decommissioning of sasCommunity.org the site has been converted to read-only mode.


Here are some tips for How to share your SAS knowledge with your professional network.


Solving Samurai Sudoku with PROC OPTMODEL using MILP solver

From sasCommunity
Jump to: navigation, search
/* Solving Samurai Sudoku puzzles with PROC OPTMODEL using MILP solver
/* 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 solve;
proc optmodel presolver=none;
   number n = 9;
   set PUZZLES = 1..5;
   set DIGITS = 1..n;
   set ROWS = 1..n;
   set COLS = 1..n;
   number f {PUZZLES,ROWS,COLS};

   /* read two-dimensional data */
   %do p = 1 %to 5;
      read data indata&p into [i = _n_] {j in COLS} <f[&p,i,j] = col("c"||j)>;
   %end;
   print f;

   /* decision variables: 
   x[p,i,j,k] = 1 if puzzle p, cell (i,j) contains digit k, 0 otherwise */
   var x {PUZZLES,ROWS,COLS,DIGITS} binary;

   /* dummy objective */
   max z = 0;

   /* digit constraints */
   con digit {p in PUZZLES, i in ROWS, j in COLS}:
       sum {k in DIGITS} x[p,i,j,k] = 1;
   /* row constraints */
   con row_con {p in PUZZLES, i in ROWS, k in DIGITS}:
       sum {j in COLS} x[p,i,j,k] = 1;
   /* column constraints */
   con col_con {p in PUZZLES, j in COLS, k in DIGITS}:
       sum {i in ROWS} x[p,i,j,k] = 1;
   /* 9-box square constraints */
   con box_con {p in PUZZLES, ri in 1..n by sqrt(n), rj in 1..n by sqrt(n), k in DIGITS}:
       sum {i in ri..ri+sqrt(n)-1, j in rj..rj+sqrt(n)-1} x[p,i,j,k] = 1;

   /* fix initial values */
   for {p in PUZZLES, i in ROWS, j in COLS: f[p,i,j] ne .}
      fix x[p,i,j,f[p,i,j]] = 1;

   /* overlap constraints */
   con overlap {<p1,i1,j1,p2,i2,j2> in 
      {<1,7,7,5,1,1>, <2,7,1,5,1,7>, <3,1,7,5,7,1>, <4,1,1,5,7,7>},
      i in 0..2, j in 0..2, k in DIGITS}:
         x[p1,i1+i,j1+j,k] = x[p2,i2+i,j2+j,k];

   *expand;
   *solve;
   solve with milp / heuristics=aggressive cuts=none varsel=maxinfeas;
   put (symget("_OROPTMODEL_"));

   for {p in PUZZLES, i in ROWS, j in COLS, k in DIGITS}
      x[p,i,j,k] = round(x[p,i,j,k].sol);
   print _page_;
   print "Nonzero variables"
      {p in PUZZLES, i in ROWS, j in COLS, k in DIGITS: x[p,i,j,k] = 1} x[p,i,j,k];
   print _page_;
   print {p in PUZZLES, i in ROWS, j in COLS} (sum {k in DIGITS} k * x[p,i,j,k]);

   create data outdata(drop=i) from [p i]=(PUZZLES cross ROWS) {j in COLS} 
      <col("C"||j) = (sum {k in DIGITS} k * x[p,i,j,k])>;

   /* to check for uniqueness, exclude this solution and solve again
   con exclude_con:
      sum {p in PUZZLES, i in ROWS, j in COLS, k in DIGITS: x[p,i,j,k].sol = 0} x[p,i,j,k]
    + sum {p in PUZZLES, i in ROWS, j in COLS, k in DIGITS: x[p,i,j,k].sol = 1} (1 - x[p,i,j,k])
   >= 1;
   print _page_;
   solve;
   put (symget("_OROPTMODEL_")); */
quit;

data _null_;
   set outdata;
   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