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

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
 



Back to examples browserPrevious exampleNext example