## 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;

```