045: The Covering Array Problem

language Essence 1.3

$ This is the decision version of the cover test problem

given k,b,t: int(1..), g: int(2..)
where k>=t, b>=g**t

letting alphabet be new type of size g
letting switches be new type of size k

find CoverTest: mset (size b) of function (total) switches --> alphabet

such that 
    forAll testcase: function switches --> alphabet                         $% every test case  
        , |toSet(testcase)| = t
        .  
            exists test in CoverTest. testcase subsetEq test                $% must be covered by some test in CoverTest


$=============================================================================
$INSTANCES

$Note: These are all easy in that they can be solved by MiniZinc in under 2 minutes.
      $The paper cited below uses Ilog Solver, which is tens of times faster.

$These are easy and unsat
$letting t=3, g=2, k=5, b=8
$letting t=3, g=2, k=5, b=9
$letting t=3, g=2, k=6, b=8
$letting t=3, g=2, k=6, b=9
$letting t=3, g=2, k=6, b=10
$letting t=3, g=2, k=7, b=8
$letting t=3, g=2, k=7, b=9
$letting t=3, g=2, k=8, b=8
$letting t=3, g=2, k=8, b=11
$letting t=3, g=2, k=9, b=11
$letting t=3, g=2, k=10, b=11
$letting t=3, g=2, k=11, b=11
$letting t=3, g=2, k=12, b=11

$These are easy and sat
$letting t=3, g=2, k=4, b=8
$letting t=3, g=2, k=4, b=9
$letting t=3, g=2, k=5, b=10
$letting t=3, g=2, k=6, b=12
$letting t=3, g=2, k=7, b=12
$letting t=3, g=2, k=8, b=12
$letting t=3, g=2, k=9, b=12
$letting t=3, g=2, k=10, b=12
$letting t=3, g=2, k=11, b=12