K. Puzzles and pastimes

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

   file k1mastm.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, Mar. 2002
*******************************************************!)

model "K-1 Mastermind"
 uses "mmxprs"

 declarations
  POS = 1..4                          ! Positions in a row
  COLORS = {"White","Blue","Yellow","Black","Red","Green"}
    
  place: array(POS,COLORS) of mpvar   ! 1 if color at the position, 0 otherwise
 end-declarations

! Assign one color per position
 forall(p in POS) sum(c in COLORS) place(p,c) = 1 

! Round 1: 1 color well positioned, 1 color on wrong position
  place(1,"Red") + place(2,"Yellow") + place(3,"White") + place(4,"Green") = 1
  sum(p in POS | p<>1) place(p,"Red") + 
    sum(p in POS | p<>2) place(p,"Yellow") +
    sum(p in POS | p<>3) place(p,"White") + 
    sum(p in POS | p<>4) place(p,"Green") = 1
 
! Round 2: 1 color well positioned
  place(1,"Blue") + place(2,"Green") + place(3,"White") + place(4,"Blue") = 1
  sum(p in POS | p<>1 and p<>4) place(p,"Blue") + 
    sum(p in POS | p<>2) place(p,"Green") +
    sum(p in POS | p<>3) place(p,"White") = 0

! Round 3: 1 color well positioned, 1 color on wrong position
  place(1,"Yellow") + place(2,"Black") + place(3,"White") + place(4,"Black") = 1
  sum(p in POS | p<>1) place(p,"Yellow") + 
    sum(p in POS | p<>2 and p<>4) place(p,"Black") +
    sum(p in POS | p<>3) place(p,"White") = 1
 
! Round 4: 4 colors on wrong position
  place(1,"Blue") + place(2,"Yellow") + place(3,"Red") + place(4,"Black") = 0
  sum(p in POS | p<>1) place(p,"Blue") + 
    sum(p in POS | p<>2) place(p,"Yellow") +
    sum(p in POS | p<>3) place(p,"Red") + 
    sum(p in POS | p<>4) place(p,"Black") = 4
 
 forall(p in POS, c in COLORS) place(p,c) is_binary
 
! Solve the problem: no objective
 minimize(0)

! Solution printing
 forall(c in COLORS) writeln(c,": ", getsol(sum(p in POS)p*place(p,c)) )

end-model

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

   file k2marath.mos
   ````````````````
   Marathon puzzle
   
   Dominique, Ignace, Naren, Olivier, Philippe, and Pascal
   have arrived as the first six at the Paris marathon.
   Reconstruct their arrival order from the following
   information:
   a) Olivier has not arrived last
   b) Dominique, Pascal and Ignace have arrived before Naren 
      and Olivier
   c) Dominique who was third last year has improved this year.
   d) Philippe is among the first four.
   e) Ignace has arrived neither in second nor third position.
   f) Pascal has beaten Naren by three positions.
   g) Neither Ignace nor Dominique are on the fourth position.
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002
*******************************************************!)

model "K-2 Marathon"
 uses "mmxprs"

 declarations
  POS = 1..6                          ! Arrival positions
  RUNNERS = {"Dominique","Ignace","Naren","Olivier","Philippe","Pascal"}
    
  arrive: array(RUNNERS,POS) of mpvar ! 1 if runner is p-th, 0 otherwise
 end-declarations

! One runner per position
 forall(p in POS) sum(r in RUNNERS) arrive(r,p) = 1 
 
! One position per runner
 forall(r in RUNNERS) sum(p in POS) arrive(r,p) = 1 
 
! a: Olivier not last
 arrive("Olivier",6) = 0

! b: Dominique, Pascal and Ignace before Naren and Olivier
 sum(p in 5..6) (arrive("Dominique",p)+arrive("Pascal",p)+arrive("Ignace",p)) =
   0
 sum(p in 1..3) (arrive("Naren",p)+arrive("Olivier",p)) = 0
 
! c: Dominique better than third
 arrive("Dominique",1)+arrive("Dominique",2) = 1
 
! d: Philippe is among the first four 
 sum(p in 1..4) arrive("Philippe",p) = 1

! e: Ignace neither second nor third
 arrive("Ignace",2)+arrive("Ignace",3) = 0

! f: Pascal three places earlier than Naren
 sum(p in 4..6) arrive("Pascal",p) = 0
 sum(p in 1..3) arrive("Naren",p) = 0

! g: Neither Ignace nor Dominique on fourth position
 arrive("Ignace",4)+arrive("Dominique",4) = 0
 
 forall(p in POS, r in RUNNERS) arrive(r,p) is_binary
 
! Solve the problem: no objective
 minimize(0)

! Solution printing
 forall(r in RUNNERS) writeln(r,": ", getsol(sum(p in POS)p*arrive(r,p)) )

end-model

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

   file k3congress.mos
   ```````````````````
   Congress puzzle
   
   At an international congress taking place on 7-11 August
   five researchers of different nationality are giving talks,
   each on a different day. Find out the date and nationality
   for every researcher from the following information:
   a) Michael is not Japanese.
   b) Eric is French and he talks before the 10th.
   c) Arabinda talks on the 9th.
   d) The Chinese who is not Hitoshi gives his talk on the 8th, 
      before Michael.
   e) Hitoshi does his talk after the Indian and before the American.
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002
*******************************************************!)

model "K-3 Congress"
 uses "mmxprs"

 declarations
  DAYS = 7..11
  NAMES = {"Arabinda","Eric","Hitoshi","Michael","Zhicheng"}
  NAT = {"Japanese","French","Chinese","American","Indian"}
    
  talk: array(NAMES,NAT,DAYS) of mpvar ! (p,n,d) 1 if person p of nationality n
                                       ! gives a talk on day d, 0 otherwise
 end-declarations

! One researcher per day and nationality
 forall(p in NAMES) sum(n in NAT, d in DAYS) talk(p,n,d) = 1 
 
! Every nationality exactly once
 forall(n in NAT) sum(p in NAMES, d in DAYS) talk(p,n,d)  = 1 

! One talk per day
 forall(d in DAYS) sum(p in NAMES, n in NAT) talk(p,n,d) = 1
 
! a: Michael is not Japanese
 sum(d in DAYS) talk("Michael","Japanese",d) = 0

! b: Eric is French and he talks before the 10th
 sum(d in 7..9) talk("Eric","French",d) = 1

! c: Arabinda talks on the 9th
 sum(n in NAT) talk("Arabinda",n,9) = 1

! d: The Chinese who is not Hitoshi gives his talk on the 8th, before Michael
 sum(d in DAYS) (talk("Hitoshi","Chinese",d)+talk("Michael","Chinese",d)) = 0
 sum(p in NAMES) talk(p,"Chinese",8) = 1
 sum(n in NAT, d in 9..11) talk("Michael",n,d) = 1

! e: Hitoshi does his talk after the Indian and before the American
 sum(n in NAT) (talk("Hitoshi",n,7)+talk("Hitoshi",n,11)) = 0
 sum(p in NAMES, d in 10..11) talk(p,"Indian",d) = 0
 sum(p in NAMES, d in 7..8) talk(p,"American",d) = 0
 sum(d in DAYS) (talk("Hitoshi","Indian",d)+talk("Hitoshi","American",d)) = 0
 
 forall(p in NAMES, n in NAT, d in DAYS) talk(p,n,d) is_binary
 
! Solve the problem: no objective
 minimize(0)

! Solution printing
 forall(p in NAMES) do
  write(p," (") 
  dp:=round(getsol(sum(n in NAT, d in DAYS)d*talk(p,n,d)))
  forall(n in NAT) write( if(getsol(talk(p,n,dp))>0, n, "") )
  writeln(") : ", dp)
 end-do

end-model

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

   file k4even.mos
   ```````````````
   Placing a given number of chips on a 4x4 grid 
   such that every row and every column contains
   an even number of chips.
   - Enumerating multiple solutions -
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. June 2011
*******************************************************!)

model "K-4 Even"
 uses "mmxprs"

 declarations
  POS = 1..4                          ! Positions in a row/column
  NCHIP = 10                          ! Number of chips
    
  place: array(POS,POS) of mpvar      ! 1 if chip at the position, 0 otherwise
  row, column: array(POS) of mpvar    ! Chips per row/column divided by 2
 end-declarations

! Total number of chips
 sum(r,c in POS) place(r,c) = NCHIP

! Even number of chips in all rows and columns
 forall(r in POS) sum(c in POS) place(r,c) = 2*row(r)
 forall(c in POS) sum(r in POS) place(r,c) = 2*column(c)
 
 forall(r,c in POS) place(r,c) is_binary
 forall(r in POS) do
  row(r) is_integer; row(r) <= 2
  column(r) is_integer; column(r) <= 2
 end-do   
 
! Solve the problem: no objective
 setparam("XPRS_enummaxsol", 100)   ! Max. number of solutions to be saved
 minimize(XPRS_ENUM,0)

! Solution printing
 forall(i in 1..getparam("XPRS_enumsols")) do
  selectsol(i)                      ! Select a solution from the pool
  writeln("Solution ", i)
  forall(r in POS) do
   forall(c in POS) write( if(getsol(place(r,c))>0, "X ", ". ") )
   writeln
  end-do
 end-do 
 
end-model

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

   file k5nephew.mos
   `````````````````
   Distributing wine barrels among nephews
   
   A farmer wishes to distribute his 45 wine barrels among
   his 5 nephews. 9 barrels are full, 9 filled to 3/4, 
   9 half-full, 9 filled to a quarter, and 9 are empty.
   Each nephew is to receive the same number of barrels
   and the same volume of wine. Furthermore, each nephew
   must receive at least one barrel of every type and 
   no two of the nephews must be allocated exactly the
   same number of barrels of every fill type. 
   - Enumerating multiple solutions -
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. June 2011
*******************************************************!)

model "K-5 Nephew"
 uses "mmxprs"

 declarations
  NN = 5; NT = 5
  NEPHEWS = 1..NN                     ! Nephews
  TYPES = 1..NT                       ! Contents types of wine barrels
  BARRELS = 45
    
  COEF: array(TYPES) of integer       ! Factors for "alldifferent" constraint
  FILL: array(TYPES) of real          ! Fill level of barrels

  give: array(NEPHEWS,TYPES) of mpvar ! Barrels of type t for every nephew
  p: array(NEPHEWS) of mpvar          ! 'Pattern': value of the product
                                      !            c*give(n,t)
 end-declarations

 FILL:: [1, 0.75, 0.5, 0.25, 0]
 COEF:: [10000, 1000, 100, 10, 1]

! Barrels per nephew
 forall(n in NEPHEWS) sum(t in TYPES) give(n,t) = BARRELS/NN
 forall(t in TYPES) sum(n in NEPHEWS) give(n,t) = BARRELS/NN

! Equilibrated contents
 forall(n in NEPHEWS) 
  sum(t in TYPES) FILL(t)*give(n,t) = BARRELS/NN * (sum(t in TYPES) FILL(t))/NT

! Every nephew receives a different number of barrels of any given type
! (that is, a different pattern for every nephew)
 forall(n in NEPHEWS) sum(t in TYPES) COEF(t)*give(n,t) = p(n)
 forall(n in 2..NN) p(n) - p(n-1) >= 1

 forall(n in NEPHEWS,t in TYPES) do
  give(n,t) is_integer
  1 <= give(n,t); give(n,t) <= NN
 end-do

! Solve the problem: no objective
 minimize(XPRS_ENUM,0)

! Solution printing
 forall(i in 1..getparam("XPRS_enumsols")) do
  selectsol(i)                      ! Select a solution from the pool
  writeln("Solution ", i)
  forall(n in NEPHEWS) do
   write(n,": ")
   forall(t in TYPES) write( getsol(give(n,t)), " " )
   writeln
  end-do
 end-do
end-model

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

   file k6queens.mos
   `````````````````
   Placing N queens on an NxN chess board such that 
   they do not attack each other.
   - Enumerating multiple solutions -
   
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Mar. 2002, rev. June 2011
*******************************************************!)

model "K-6 Queens"
 uses "mmxprs"

 declarations
  NQ = 8                              ! Number of rows and columns
  POS = 1..NQ
    
  queen: array(POS,POS) of mpvar      ! 1 if queen at a position, 0 otherwise
 end-declarations

! Objective: total number of queens
 Total:= sum(r,c in POS) queen(r,c)

! Single queen per row and column
 forall(r in POS) sum(c in POS) queen(r,c) = 1
 forall(c in POS) sum(r in POS) queen(r,c) = 1

! Diagonals 
 forall(c in POS) sum(r in c..NQ) queen(r-c+1,r) <= 1
 forall(r in 2..NQ) sum(c in r..NQ) queen(c,c-r+1) <= 1
 forall(c in POS) sum(r in 1..c) queen(r,c-r+1) <= 1
 forall(r in 2..NQ) sum(c in r..NQ) queen(c,NQ-c+r) <= 1

 forall(r,c in POS) queen(r,c) is_binary
 
! Solve the problem
 setparam("XPRS_enummaxsol", 100)   ! Max. number of solutions to be saved
 minimize(XPRS_ENUM,Total)

! Solution printing
 forall(i in 1..getparam("XPRS_enumsols")) do
  selectsol(i)                      ! Select a solution from the pool
  writeln("Solution ", i, ". Total number of queens: ", getobjval)
  forall(r in POS) do
   forall(c in POS) write( if(getsol(queen(r,c))>0, "Q ", ". ") )
   writeln
  end-do
 end-do 

end-model