Resources

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;