Alphabet Blocks Problem (oclpe02)
/***************************************************************/
/* */
/* S A S S A M P L E L I B R A R Y */
/* */
/* NAME: clp2 */
/* TITLE: Alphabet Blocks Problem (oclpe02) */
/* PRODUCT: OR */
/* SYSTEM: ALL */
/* KEYS: OR */
/* PROCS: CLP */
/* DATA: */
/* */
/* SUPPORT: UPDATE: */
/* REF: */
/* MISC: Example 2 from the CLP Solver chapter of the */
/* Mathematical Programming book. */
/* */
/***************************************************************/
proc optmodel;
/* 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. */
set LETTERS = / A B C D E F G H I J K L M N O P R S T U V W X Y /;
var Block {LETTERS} integer >= 1 <= 4;
set BLOCKS = 1..4;
/* There are exactly 6 letters on each alphabet block */
con SixLettersPerBlock:
gcc(Block, setof {b in BLOCKS} <b,6,6>);
/* The letters in each word must be on different blocks. */
set WORDS = / BAKE ONYX ECHO OVAL GIRD SMUG JUMP TORN LUCK VINY LUSH WRAP /;
con CanSpell {w in WORDS}:
gcc({k in 1..length(w)} Block[char(w,k)], setof {b in BLOCKS} <b,0,1>);
/* Note 2: These restrictions can also be enforced by ALLDIFF constraints:
con CanSpellv2 {w in WORDS}:
alldiff({k in 1..length(w)} Block[char(w,k)]);
*/
/* 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. */
for {k in 1..length('BAKE')} fix Block[char('BAKE',k)] = k;
solve;
print Block;
quit;