FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

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.

K‑1 K‑2 K‑3 Problem name Difficulty Playing Mastermind ** Marathon puzzle * Congress puzzle * Placing chips * Nephew puzzle ** 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).

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

`