Logic Based Puzzles (clpe01)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: clpe01 */
/* TITLE: Logic Based Puzzles (clpe01) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: CLP, IML */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 1 from the CLP Procedure chapter of the */
/* Constraint Programming book. */
/* */
/***************************************************************/
/* Given a sudoku problem */
data indata;
input C1-C9;
datalines;
. . 5 . . 7 . . 1
. 7 . . 9 . . 3 .
. . . 6 . . . . .
. . 3 . . 1 . . 5
. 9 . . 8 . . 2 .
1 . . 2 . . 4 . .
. . 2 . . 6 . . 9
. . . . 4 . . 8 .
8 . . 1 . . 5 . .
;
/* store ds values into macro variable C_i_j */
%macro store_values(ds, n);
/* define C_i_j global */
%do i=1 %to &n.;
%do j=1 %to &n.;
%global C_&i._&j.;
%end;
%end;
/* store values into C_i_j */
data _null_;
set &ds;
array C{&n.};
do j = 1 to &n.;
i = _N_;
call symput(compress('C_'||put(i,best.)||'_'||put(j,best.)),
put(C[j],best.));
end;
run;
%mend store_values;
%store_values(indata, 9);
/* Print sudoku */
%macro print_sudoku;
goptions hsize=4in vsize=4in;
data sdk;
length function style color $8 text $1;
retain xsys ysys hsys "3";
/* squares and values C_i_j */
do i=1 to 9;
do j=1 to 9;
function="move"; x=100*i/9; y=100*(9-j)/9; output;
function="bar"; x=100*(i-1)/9; y=100*(10-j)/9;
size=0.5; line=1; color="black"; output;
function="move"; x=100*(i-1)/9+4; y=100*(10-j)/9; output;
function="label";
text=input(left(symget('C_'||put(j,1.)||'_'||put(i,1.))),1.);
if text='.' then text='';
position="9"; style=""; color="black"; size=5; output;
end;
end;
/* draw the out frame */
function="move"; x=100; y=100; output;
function="bar"; x=0; y=0; size=2; line=0; color="black"; output;
/* Thick Vertical lines */
function="move"; x=100/3; y=0; output;
function="draw"; x=100/3; y=100; size=0.6; line=1; output;
function="move"; x=200/3; y=0; output;
function="draw"; x=200/3; y=100; output;
/* Thick Horizontal lines */
function="move"; x=0; y=100/3; output;
function="draw"; x=100; y=100/3; output;
function="move"; x=0; y=200/3; output;
function="draw"; x=100; y=200/3; output;
run;
proc ganno annotate=sdk;
run;
%mend print_sudoku;
%print_sudoku;
%macro condata;
/* Declare variables */
/* Nine row constraints */
%do i = 1 %to 9;
var (X_&i._1-X_&i._9) = [1,9];
alldiff(X_&i._1-X_&i._9);
%end;
/* Nine column constraints */
%do j = 1 %to 9;
alldiff(
%do i = 1 %to 9;
X_&i._&j
%end;
);
%end;
/* Nine 3x3 block 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;
/* Initialize variables to cell values */
/* 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;
%mend condata;
%macro solve;
proc clp out=outdata;
%condata;
run;
%put &_ORCLP_;
%mend solve;
%solve;
/* convert solution to matrix in dense format */
%macro convert_to_dense(ds, n);
data outdata_dense;
set &ds;
array C{&n.};
%do i = 1 %to &n.;
%do j = 1 %to &n.;
C[&j] = X_&i._&j;
%end;
output;
%end;
drop X:;
run;
%mend convert_to_dense;
%convert_to_dense(outdata, 9);
%store_values(outdata_dense,9);
%print_sudoku;
data raw;
input C1-C12;
datalines;
3 . . 1 5 4 . . 1 . 9 5
. 1 . . 3 . . . . 1 3 6
. . 4 . . 3 . 8 . . 2 .
5 . . 1 . . 9 2 5 . . 1
. 9 . . 5 . . 5 . . . .
5 8 1 . . 9 . . 3 . 6 .
. 5 . 8 . . 2 . . 5 5 3
. . . . 5 . . 6 . . 1 .
2 . . 5 1 5 . . 5 . . 9
. 6 . . 4 . 1 . . 3 . .
1 5 1 . . . . 5 . . 5 .
5 5 . 4 . . 3 1 6 . . 8
;
/* store each pre-filled value into macro variable C_i_j */
%store_values(raw, 12);
%macro print_piday;
goptions reset=title;
goptions hsize=4in vsize=4in;
data piday;
length function style color $8 text $1;
retain xsys ysys hsys "3";
/* draw the color bars */
function="move"; x=100; y=100; output; /* whole */
function="bar"; x=0; y=0; size=1; line=0; color="cxffedaf"; style='s';
output;
function="move"; x=300/12; y=100; output; /* left up */
function="bar"; x=0; y=700/12; color="cxfde28a"; output;
function="move"; x=100; y=300/12; output; /* right down */
function="bar"; x=600/12; y=0; output;
function="move"; x=100; y=100; output; /* right up */
function="bar"; x=900/12; y=700/12; color="cxffdc61"; output;
function="move"; x=600/12; y=300/12; output; /* left down */
function="bar"; x=0; y=0; output;
function="move"; x=600/12; y=1000/12; output; /* purple left up */
function="bar"; x=200/12; y=700/12; color="cxbd85ff"; output;
function="move"; x=900/12; y=700/12; output; /* purple right down */
function="bar"; x=700/12; y=100/12; output;
function="move"; x=1000/12; y=1000/12; output; /* purple right up */
function="bar"; x=600/12; y=700/12; color="cxd3aefe"; output;
function="move"; x=500/12; y=700/12; output; /* purple left down */
function="bar"; x=300/12; y=100/12; output;
function="move"; x=700/12; y=300/12; color="cxffedaf"; output;
function="bar"; x=500/12; y=100/12; output;
/* squares and values C_i_j */
do i=1 to 12;
do j=1 to 12;
function="move"; x=100*i/12; y=100*(12-j)/12; output;
function="bar"; x=100*(i-1)/12; y=100*(13-j)/12;
size=0.5; line=1; color="black"; style='e'; output;
function="move"; x=100*(i-1)/12+3; y=100*(13-j)/12-1; output;
function="label";
text=input(left(symget('C_'||trim(left(j))||'_'||
trim(left(i)))),1.);
if text='.' then text='';
position="F"; style=""; color="black"; size=5; output;
end;
end;
/* draw the out frame */
function="move"; x=100; y=100; output;
function="bar"; x=0; y=0; size=2; line=0; position="9"; color="black";
output;
/* Horizontal separating lines */
function="move"; x=1000/12; y=1000/12; output;
function="draw"; x=200/12; y=1000/12; size=0.6; line=1; output;
function="move"; x=100; y=700/12; output;
function="draw"; x=0; y=700/12; output;
function="move"; x=300/12; y=300/12; output;
function="draw"; x=0; y=300/12; output;
function="move"; x=100; y=300/12; output;
function="draw"; x=900/12; y=300/12; output;
function="move"; x=900/12; y=100/12; output;
function="draw"; x=300/12; y=100/12; output;
/* Vertical separating lines */
function="move"; x=200/12; y=1000/12; output;
function="draw"; x=200/12; y=700/12; output;
function="move"; x=300/12; y=100; output;
function="draw"; x=300/12; y=1000/12; output;
function="move"; x=300/12; y=700/12; output;
function="draw"; x=300/12; y=100/12; output;
function="move"; x=500/12; y=700/12; output;
function="draw"; x=500/12; y=100/12; output;
function="move"; x=600/12; y=1000/12; output;
function="draw"; x=600/12; y=700/12; output;
function="move"; x=600/12; y=100/12; output;
function="draw"; x=600/12; y=0; output;
function="move"; x=700/12; y=700/12; output;
function="draw"; x=700/12; y=100/12; output;
function="move"; x=900/12; y=100; output;
function="draw"; x=900/12; y=1000/12; output;
function="move"; x=900/12; y=700/12; output;
function="draw"; x=900/12; y=100/12; output;
function="move"; x=1000/12; y=1000/12; output;
function="draw"; x=1000/12; y=700/12; output;
run;
proc ganno annotate=piday;
run;
%mend print_piday;
%print_piday;
%macro cons_row(r);
/* Row r must contain two 1's, two 3's, three 5's, no 7's, */
/* and one for each of other values from 1 to 9. */
gcc(X_&r._1-X_&r._12) =
( (1, 2, 2) (3, 2, 2) (5, 3, 3) (7, 0, 0) DL=1 DU=1 );
%mend cons_row;
%macro cons_col(c);
/* Column c must contain two 1's, two 3's, three 5's, */
/* no 7's, and one for each of other values from 1 to 9. */
gcc( %do r = 1 %to 12;
X_&r._&c.
%end;
) = ((1, 2, 2) (3, 2, 2) (5, 3, 3) (7, 0, 0) DL=1 DU=1);
%mend cons_col;
%macro cons_region(vars);
/* Jigsaw region that contains &vars must contain two 1's, */
/* two 3's, three 5's, no 7's, and one for each of other */
/* values from 1 to 9. */
gcc(&vars.) = ((1, 2, 2) (3, 2, 2) (5, 3, 3) (7, 0, 0) DL=1 DU=1);
%mend cons_region;
%macro pds(solns=allsolns,varsel=MINR,maxt=900);
proc clp out=pdsout &solns
varselect=&varsel /* Variable selection strategy */
maxtime=&maxt; /* Time limit */
/* Variable X_i_j represents the grid of ith row and jth column. */
var (
%do i = 1 %to 12;
X_&i._1 - X_&i._12
%end;
) = [1,9];
/* X_i_j = C_i_j if C_i_j is non-missing */
%do i = 1 %to 12;
%do j = 1 %to 12;
%if &&C_&i._&j ne . %then %do;
lincon X_&i._&j = &&C_&i._&j;
%end;
%end;
%end;
/* 12 Row constraints: */
%do r = 1 %to 12;
%cons_row(&r);
%end;
/* 12 Column constraints: */
%do c = 1 %to 12;
%cons_col(&c);
%end;
/* 12 Jigsaw region constraints: */
/* Each jigsaw region is defined by the macro variable &vars. */
/* Region 1: */
%let vars = X_1_1 - X_1_3 X_2_1 - X_2_3
X_3_1 X_3_2 X_4_1 X_4_2 X_5_1 X_5_2;
%cons_region(&vars.);
/* Region 2: */
%let vars = X_1_4 - X_1_9 X_2_4 - X_2_9;
%cons_region(&vars.);
/* Region 3: */
%let vars = X_1_10 - X_1_12 X_2_10 - X_2_12
X_3_11 X_3_12 X_4_11 X_4_12 X_5_11 X_5_12;
%cons_region(&vars.);
/* Region 4: */
%let vars = X_3_3 - X_3_6 X_4_3 - X_4_6 X_5_3 - X_5_6;
%cons_region(&vars.);
/* Region 5: */
%let vars = X_3_7 - X_3_10 X_4_7 - X_4_10 X_5_7 - X_5_10;
%cons_region(&vars.);
/* Region 6: */
%let vars = X_6_1 - X_6_3 X_7_1 - X_7_3
X_8_1 - X_8_3 X_9_1 - X_9_3;
%cons_region(&vars.);
/* Region 7: */
%let vars = X_6_4 X_6_5 X_7_4 X_7_5 X_8_4 X_8_5
X_9_4 X_9_5 X_10_4 X_10_5 X_11_4 X_11_5;
%cons_region(&vars.);
/* Region 8: */
%let vars = X_6_6 X_6_7 X_7_6 X_7_7 X_8_6 X_8_7
X_9_6 X_9_7 X_10_6 X_10_7 X_11_6 X_11_7;
%cons_region(&vars.);
/* Region 9: */
%let vars = X_6_8 X_6_9 X_7_8 X_7_9 X_8_8 X_8_9
X_9_8 X_9_9 X_10_8 X_10_9 X_11_8 X_11_9;
%cons_region(&vars.);
/* Region 10: */
%let vars = X_6_10 - X_6_12 X_7_10 - X_7_12
X_8_10 - X_8_12 X_9_10 - X_9_12;
%cons_region(&vars.);
/* Region 11: */
%let vars = X_10_1 - X_10_3 X_11_1 - X_11_3 X_12_1 - X_12_6;
%cons_region(&vars.);
/* Region 12: */
%let vars = X_10_10 - X_10_12 X_11_10 - X_11_12 X_12_7 - X_12_12;
%cons_region(&vars.);
run;
%put &_ORCLP_;
%mend pds;
%pds;
%convert_to_dense(pdsout, 12);
proc print data=outdata_dense;
title "Pi Day Sudoku 2008";
run;
%store_values(outdata_dense, 12);
%print_piday;
%macro magic(n);
%put n = &n;
/* magic constant */
%let sum = %eval((&n*(&n*&n+1))/2);
proc clp out=magic&n evalvarsel maxtime=3;
/* X_i_j = entry (i,j) */
%do i = 1 %to &n;
var (X_&i._1-X_&i._&n) = [1,%eval(&n*&n)];
%end;
/* row sums */
%do i = 1 %to &n;
lincon 0
%do j = 1 %to &n;
+ X_&i._&j
%end;
= ∑
%end;
/* column sums */
%do j = 1 %to &n;
lincon 0
%do i = 1 %to &n;
+ X_&i._&j
%end;
= ∑
%end;
/* diagonal: upper left to lower right */
lincon 0
%do i = 1 %to &n;
+ X_&i._&i
%end;
= ∑
/* diagonal: upper right to lower left */
lincon 0
%do i = 1 %to &n;
+ X_%eval(&n+1-&i)_&i
%end;
= ∑
/* symmetry-breaking */
lincon X_1_1 + 1 <= X_&n._1;
lincon X_1_1 + 1 <= X_&n._&n;
lincon X_1_&n + 1 <= X_&n._1;
alldiff();
run;
%put &_ORCLP_;
%put &_ORCLPEVS_;
%mend magic;
%magic(7);
%macro convert_to_dense(n);
/* convert solution to matrix in dense format */
data magic7_dense;
set magic7;
array C{7};
%do i = 1 %to &n;
%do j = 1 %to &n;
C[&j] = X_&i._&j;
%end;
output;
%end;
drop X:;
run;
%mend convert_to_dense;
%convert_to_dense(7);
%store_values(magic7_dense, 7);
/* Print Magic Square */
%macro print_msq;
goptions hsize=3in vsize=3in;
data msq;
length function style color $8 text $2;
retain xsys ysys hsys "3";
/* squares and values C_i_j */
do i=1 to 7;
do j=1 to 7;
function="move"; x=100*i/7; y=100*(7-j)/7; output;
function="bar"; x=100*(i-1)/7; y=100*(8-j)/7;
size=0.5; line=1; color="black"; output;
function="move"; x=100*(i-1)/7+4; y=100*(8-j)/7; output;
function="label";
text=input(left(symget('C_'||put(j,1.)||'_'||put(i,1.))),2.);
if text='.' then text='';
position="9"; style=""; color="black"; size=5; output;
end;
end;
run;
proc ganno annotate=msq;
run;
%mend print_msq;
%print_msq;
