|
Hi.
The SAS/OR development crew has been very busy lately, completely
overhauling their suite of mathematical programming routines. I'm only
just getting acquainted with the new PROCs. One of the new babies is PROC
CLP for constraint programming. So, inspired by Larry Hoyle's masterful
base SAS Sudoku solver, I thought I'd tackle the popular puzzle as my
first PROC CLP project. I suspect it can be done much more elegantly, but
this worked pretty quickly on Larry's example. The macro borrows Larry's
input data set format (although it only needs the cell number and value),
and his PROC TABULATE statement.
* Larry Hoyle's example ;
data PuzzleEntered ;
retain cell 0 ;
do row = 1 to 9 ;
do col = 1 to 9 ;
input value 1. @@ ;
cell = cell + 1 ;
sqRow = int((row+2)/3) ;
sqCol = int((col+2)/3) ;
output ;
end ;
input ;
end ;
datalines ;
.........
.4.1.6.9.
.7.3.9.8.
.13...75.
7..5.1..8
5.......6
6.......1
.52...84.
3..9.2..5
;
run ;
%macro sudclp(puzdsi=PuzzleEntered,puzdso=PuzzleSolved) ;
*
note: input data set has 81 observations, one for each cell,
missing or otherwise
variables in puzdsi are numeric
cell 1-81 goes across rows, column by column then onto next
row
value 1-9 initial values, missing if missing(!)
;
* macro variables to fill in linear constraints, which just identify
the given values ;
data _null_ ;
set &puzdsi. end = last ;
call symput("value" || compress(put(cell,2.)), compress
(put(value,1.))) ;
run ;
%do i = 1 %to 81 ;
%put value&i. = &&value&i. ;
%end ;
proc clp out = sudout1 ;
var (value1 - value81) = [1,9] ;
* initial configuration ;
lincon
%let con1 = 1 ;
%do i = 1 %to 81 ;
%if "&&value&i." ge "1" and
"&&value&i." le "9" %then %do ;
%if &con1. ne 1 %then %do ;
%str(,)
%end ;
%else %do ;
%let con1 = 0 ;
%end ;
value&i. = &&value&i.
%end ;
%end ;
;
* row constraints ;
alldiff (value1 - value9) ;
alldiff (value10 - value18) ;
alldiff (value19 - value27) ;
alldiff (value28 - value36) ;
alldiff (value37 - value45) ;
alldiff (value46 - value54) ;
alldiff (value55 - value63) ;
alldiff (value64 - value72) ;
alldiff (value73 - value81) ;
* column constraints ;
alldiff (value1 value10 value19 value28 value37 value46 value55
value64 value73) ;
alldiff (value2 value11 value20 value29 value38 value47 value56
value65 value74) ;
alldiff (value3 value12 value21 value30 value39 value48 value57
value66 value75) ;
alldiff (value4 value13 value22 value31 value40 value49 value58
value67 value76) ;
alldiff (value5 value14 value23 value32 value41 value50 value59
value68 value77) ;
alldiff (value6 value15 value24 value33 value42 value51 value60
value69 value78) ;
alldiff (value7 value16 value25 value34 value43 value52 value61
value70 value79) ;
alldiff (value8 value17 value26 value35 value44 value53 value62
value71 value80) ;
alldiff (value9 value18 value27 value36 value45 value54 value63
value72 value81) ;
* box constraints ;
alldiff (value1 - value3 value10 - value12
value19 - value21) ;
alldiff (value4 - value6 value13 - value15
value22 - value24) ;
alldiff (value7 - value9 value16 - value18
value25 - value27) ;
alldiff (value28 - value30 value37 - value39
value46 - value48) ;
alldiff (value31 - value33 value40 - value42
value49 - value51) ;
alldiff (value34 - value36 value43 - value45
value52 - value54) ;
alldiff (value55 - value57 value64 - value66
value73 - value75) ;
alldiff (value58 - value60 value67 - value69
value76 - value78) ;
alldiff (value61 - value63 value70 - value72
value79 - value81) ;
run ;
data &puzdso. ;
set sudout1 ;
keep value row col ;
array val{1:81} value1 - value81 ;
do i = 1 to 81 ;
value = val{i} ;
row = ceil(i/9) ;
col = mod(i,9) + (9 *
(mod(i,9) = 0)) ;
output ;
end ;
stop ;
run ;
PROC TABULATE
DATA = &puzdso. ;
VAR value ;
CLASS col / ORDER = UNFORMATTED MISSING ;
CLASS row / ORDER = UNFORMATTED MISSING ;
TABLE /* Row Dimension */
row,
/* Column Dimension */
col *
value *
Sum * F = 1.0 ;
RUN ;
%mend sudclp ;
%sudclp() ;
-- TMK --
"The Macro Klutz"
| 
