Alphabet Blocks Problem (clpe02)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: clpe02 */
/* TITLE: Alphabet Blocks Problem (clpe02) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: CLP */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 2 from the CLP Procedure chapter of the */
/* Constraint Programming book. */
/* */
/***************************************************************/
proc clp out=out;
/* Each letter except Q and Z is represented with a variable. */
/* The domain of each variable is the set of 4 blocks, */
/* or {1, 2, 3, 4} for short. */
var (A B C D E F G H I J K L M N O P R S T U V W X Y) = [1,4];
/* There are exactly 6 letters on each alphabet block */
gcc (A B C D E F G H I J K L M N O P R S T U V W X Y) = (
(1, 6, 6)
(2, 6, 6)
(3, 6, 6)
(4, 6, 6) );
/* Note 1: Since lv=uv=6 for all v=1,...,4; the above global
cardinality constraint can also specified as:
gcc (A B C D E F G H I J K L M N O P R S T U V W X Y) =(DL=6 DU=6);
*/
/* The letters in each word must be on different blocks. */
gcc (B A K E) = (DL=0 DU=1)
(O N Y X) = (DL=0 DU=1)
(E C H O) = (DL=0 DU=1)
(O V A L) = (DL=0 DU=1)
(G I R D) = (DL=0 DU=1)
(S M U G) = (DL=0 DU=1)
(J U M P) = (DL=0 DU=1)
(T O R N) = (DL=0 DU=1)
(L U C K) = (DL=0 DU=1)
(V I N Y) = (DL=0 DU=1)
(L U S H) = (DL=0 DU=1)
(W R A P) = (DL=0 DU=1);
/* Note 2: These restrictions can also be enforced by ALLDIFF constraints:
alldiff (B A K E) (O N Y X) (E C H O) (O V A L)
(G I R D) (S M U G) (J U M P) (T O R N)
(L U C K) (V I N Y) (L U S H) (W R A P);
*/
/* Breaking the symmetry that blocks can be interchanged by setting
the block that contains the letter B as block1, the block that
contains the letter A as block2, etc. */
lincon B = 1;
lincon A = 2;
lincon K = 3;
lincon E = 4;
run;
/* Format for printer friendly output */
proc transpose data=out out=out1;
run;
proc sort data=out1;
by col1;
run;
data out2;
set out1;
by col1;
var=upcase(_name_);
if first.col1 then cnt=1;
else cnt+1;
retain cnt;
run;
proc sort data=out2;
by col1;
run;
proc transpose data=out2 out=out3(drop=_name_) prefix=Side;
by col1;
var var;
id cnt;
run;
proc print data=out3(rename=(col1=Block)) noobs;
title 'Solution to Alphabet Blocks Problem';
run;