FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious example

Puzzles and pastimes from the book `Programmation Lineaire'

Description
The following models implement solutions to the puzzles published in the book `Programmation Lineaire' by C. Gueret, C. Prins, and M. Sevaux (Eyrolles 2000, in French). Each problem is implemented as a MIP and as a CP model.



Problem nameDifficulty
K‑1 Playing Mastermind **
K‑2 Marathon puzzle *
K‑3 Congress puzzle *
K‑4 Placing chips *
K‑5 Nephew puzzle **
K‑6 N-queens problem *


These models show how to formulate different logical constraints using binary variables (MIP models) or logical constraint relations and global constraints (CP models).

bookpuzzle.zip[download all files]

Source Files





k1masterm_ka.mos

(!******************************************************
   Mosel Example Problems
   ======================

   file k1masterm_ka.mos
   `````````````````````
   Playing Mastermind

   Given information:
   Round  Pos.1   Pos.2   Pos.3   Pos.4   Judgement
    1     red     yellow  white   green   1 color well positioned, 
                                          1 color on wrong position  
    2     blue    green   white   blue    1 color well positioned
    3     yellow  black   white   black   1 color well positioned, 
                                          1 color on wrong position
    4     blue    yellow  red     black   all colors on wrong position
       
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, March 2005
*******************************************************!)

model "K-1 Mastermind (CP)"
 uses "kalis"

 declarations
  POS = 1..4                          ! Positions in a row
  COLORS = 1..6                       ! 1: White, 2: Blue, 3: Yellow,
                                      ! 4: Black, 5: Red, 6: Green
  place: array(POS) of cpvar          ! Color of position
  use: array(COLORS) of cpvar         ! Number of occurences of a color
 end-declarations
 
! Creation of variables
 forall(p in POS) do 
  1 <= place(p); place(p) <= 6; end-do
 forall(c in COLORS) do 
  0 <= use(c); use(c) <= 4; end-do
 
! Relation between placement variables and choice indicators
 forall(c in COLORS) use(c) = occurrence(c, place)
 sum(c in COLORS) use(c) = 4

! Round 1: 1 color well positioned, 1 color on wrong position
 place(1)=5 or place(2)=3 or place(3)=1 or place(4)=6
 use(5) + use(3) + use(1) + use(6) = 2

 writeln("Round 1: ", place, use) 
 
! Round 2: 1 color well positioned
 place(1)=2 or place(2)=6 or place(3)=1 or place(4)=2
 use(2) + use(6) + use(1) = 1

 writeln("Round 2: ", place, use) 

! Round 3: 1 color well positioned, 1 color on wrong position
 place(1)=3 or place(2)=4 or place(3)=1 or place(4)=4
 use(3) + use(4) + use(1) = 2

 writeln("Round 3: ", place, use) 
 
! Round 4: 4 colors on wrong position
 place(1)<>2; place(2)<>3; place(3)<>5; place(4)<>4
 forall(p in POS) do
  2 <= place(p); place(p) <= 5
 end-do
 use(2)=1; use(3)=1; use(5)=1; use(4)=1 
 
 writeln("Round 4: ", place, use) 



! Branching strategy
 cp_set_branching(assign_var(KALIS_SMALLEST_DOMAIN, KALIS_MIN_TO_MAX, place))

! Solve the problem
 if not cp_find_next_sol then
  writeln("Problem is infeasible")
  exit(1)
 end-if

! Solution printing
 declarations
  COLORNAMES: array(COLORS) of string
 end-declarations
 
 COLORNAMES:: ["White","Blue","Yellow","Black","Red","Green"]
 
 forall(p in POS)
  writeln("Position ", p, ": ", COLORNAMES(getsol(place(p))) )
  
end-model

Back to examples browserPrevious example