Date: Thu, 11 May 2006 12:42:09 -0400 Talbot Michael Katz "SAS(r) Discussion" Talbot Michael Katz SUDOKU via PROC CLP

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"

Back to: Top of message | Previous page | Main SAS-L page