 FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home   Futoshiki (CP and MIP models)

Description
Playing Futoshiki: fill in the grid so that every row and column contains the numbers 1-5. The `greater than' of `less than' signs indicate where a number is larger or smaller than its neighbor.
• The models futo.mos and futo_ka.mos solve a given Futoshiki grid with MIP and CP respectively.

Source Files

Data Files

futo_ka.mos

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

file futo_ka.mos
````````````````
Solving the Futoshiki puzzle as a CP problem.

(c) 2008 Fair Isaac Corporation
author: S. Heipcke, 2006
*******************************************************!)

model "futoshiki (CP)"
uses "kalis"

parameters
DATAFILE="futo1.dat"
end-parameters

forward procedure print_solution(numsol: integer)

declarations
FIVE = 1..5
ISKNOWN: dynamic array(FIVE,FIVE) of integer
ISGREATER: dynamic array(FIVE,FIVE,FIVE,FIVE) of boolean
y: array(FIVE,FIVE) of cpvar
end-declarations

initializations from "Data/"+DATAFILE
ISKNOWN ISGREATER
end-initializations

forall(i,j in FIVE) setdomain(y(i,j), FIVE)

! Every row and column contains the numbers 1 to 5
forall(i in FIVE) all_different(union(j in FIVE) {y(i,j)})
forall(j in FIVE) all_different(union(i in FIVE) {y(i,j)})

! Definition of the particular grid
forall(i,j in FIVE | exists(ISKNOWN(i,j)))
y(i,j) = ISKNOWN(i,j)
forall(i1,j1,i2,j2 in FIVE | exists(ISGREATER(i1,j1,i2,j2)))
y(i1,j1) >= y(i2,j2) + 1

! Solve the problem
solct:= 0
while (cp_find_next_sol) do
solct+=1
print_solution(solct)
end-do

!****************************************************************
! Solution printing
procedure print_solution(numsol: integer)
writeln(getparam("KALIS_COMPUTATION_TIME"), "sec: Solution ", numsol)
writeln("  | 1 2 3 4 5")
writeln("--------------")
forall(i in FIVE) do
write(i, " | ")
forall(j in FIVE) do
write(getsol(y(i,j)))
if j<5 then
if ISGREATER(i,j,i,j+1) then write (">")
elif ISGREATER(i,j+1,i,j) then write("<")
else write(" ")
end-if
else
writeln
end-if
end-do
if i < 5 then
write("  | ")
forall(j in FIVE)
if ISGREATER(i,j,i+1,j) then write ("v ")
elif ISGREATER(i+1,j,i,j) then write("^ ")
else write("  ")
end-if
end-if
writeln
end-do
end-procedure

end-model

```   