From sasCommunity
/* 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
