CSP easy

Problem Labeled Dice

From Jim Orlin’s Blog: ``There are 13 words as follows: buoy, cave, celt, flub, fork, hemp, judy, junk, limn, quip, swag, visa, wish. There are 24 different letters that appear in the 13 words. The question is: can one assign the 24 letters to 4 different cubes so that the four letters of each word appears on different cubes. There is one letter from each word on each cube. The puzzle was created by Humphrey Dudley’’

To build a CSP (Constraint Satisfaction Problem) model, we need first to import the library PyCSP$^3$:

from pycsp3 import *

Then, we need some data. Here, the data correspond to the 13 words.

words = ["buoy", "cave", "celt", "flub", "fork", "hemp", "judy", "junk", "limn", "quip", "swag", "visa", "wish"]

We compute some auxiliary information. Note that the function alphabet_positions() returns a tuple composed of the positions (indexes) in the Latin alphabet of all letters of a string, or the concatenation of strings of a list, passed as a parameter.

letters = alphabet_positions(words)  # the indexes of present letters
cubes = range(1, 5)                  # the indexes 0, 1, 2, 3 of the four cubes

We can check that, in $\mathtt{letters}$, we have the indexes of all involved characters in the 13 words.

print("Indexes of letters: ", set(letters))

Indexes of letters:  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 24}

We start our CSP model with an array $x$ of variables. for simplicity, the array contains 26 squares (for the 26 possible letters) but only some of them are considered as relevant: those corresponding to an involved letter index.

# x[i] is the cube where the ith letter of the alphabet is put
x = VarArray(size=26, dom=lambda i: cubes if i in letters else None)

By printing the content of $x$, we can clearly see which variables are created. You can check that the letters $x$ and $z$ are not present in any word.

print("Array x: ", x)

Array x:  [x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19], x[20], x[21], x[22], None, x[24], None]

The domain of each variable is ${0,1,\dots,4}$. For example:

print("Domain of variables: ", x[4].dom)

Domain of variables:  1..4

Concerning the constraints, we first post a group of 13 constraints AllDifferent.

satisfy(
   # the four letters of each word appears on different cubes
   AllDifferent(x[i] for i in alphabet_positions(w)) for w in words
);

Interestingly, by calling the function solve(), we can check that the problem is satisfiable (SAT). We can also display the values of each word. Here, we call the function values() that collects the values assigned to a specified list of variables.

if solve() is SAT:
    print("Solution: ", values(x))
    for w in words:
        print(f" - {w}: {values(x[i] for i in alphabet_positions(w))}")

Solution:  [1, 2, 4, 2, 2, 1, 2, 1, 2, 3, 2, 3, 4, 1, 3, 3, 1, 4, 4, 1, 4, 3, 3, None, 1, None]
 - buoy: [2, 4, 3, 1]
 - cave: [4, 1, 3, 2]
 - celt: [4, 2, 3, 1]
 - flub: [1, 3, 4, 2]
 - fork: [1, 3, 4, 2]
 - hemp: [1, 2, 4, 3]
 - judy: [3, 4, 2, 1]
 - junk: [3, 4, 1, 2]
 - limn: [3, 2, 4, 1]
 - quip: [1, 4, 2, 3]
 - swag: [4, 3, 1, 2]
 - visa: [3, 2, 4, 1]
 - wish: [3, 2, 4, 1]

Clearly, the four letters of each word appears on different cubes. According to the order in which solutions are found by the solver, one may or may not observe that some cubes (values) occurs more often than others.

We can compute the number of solutions as follows.

if solve(sols=ALL) is SAT:
    print("Number of solutions: ", n_solutions())

Number of solutions:  72

If we enumerate the solutions (this is possible, but very verbose here), we can see that some solutions violate the requirement that each cube must be assigned 6 letters. We need to post a constraint Cardinality:

satisfy(
    # each cube is assigned 6 letters
    Cardinality(x, occurrences={i: 6 for i in cubes})
);

If we are curious, we can print the intern representation of the constraints that have been posted. Athough a little bit technical, one can see that we have 13 constraints AllDifferent and 1 constraint Cardinality.

print(posted())

allDifferent(list:[x[1], x[20], x[14], x[24]])
allDifferent(list:[x[2], x[0], x[21], x[4]])
allDifferent(list:[x[2], x[4], x[11], x[19]])
allDifferent(list:[x[5], x[11], x[20], x[1]])
allDifferent(list:[x[5], x[14], x[17], x[10]])
allDifferent(list:[x[7], x[4], x[12], x[15]])
allDifferent(list:[x[9], x[20], x[3], x[24]])
allDifferent(list:[x[9], x[20], x[13], x[10]])
allDifferent(list:[x[11], x[8], x[12], x[13]])
allDifferent(list:[x[16], x[20], x[8], x[15]])
allDifferent(list:[x[18], x[22], x[0], x[6]])
allDifferent(list:[x[21], x[8], x[18], x[0]])
allDifferent(list:[x[22], x[8], x[18], x[7]])
cardinality(list:[x[0], x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8], x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18], x[19], x[20], x[21], x[22], x[24]], values:[1, 2, 3, 4], occurs:[6, 6, 6, 6])

We have now the guarantee of obtaining a valid solution.

if solve() is SAT:
    print("Solution: ", values(x))
    for w in words:
        print(f" - {w}: {values(x[i] for i in alphabet_positions(w))}")

Solution:  [1, 2, 3, 2, 2, 3, 2, 1, 2, 1, 2, 1, 4, 3, 1, 3, 1, 4, 3, 4, 4, 4, 4, None, 3, None]
 - buoy: [2, 4, 1, 3]
 - cave: [3, 1, 4, 2]
 - celt: [3, 2, 1, 4]
 - flub: [3, 1, 4, 2]
 - fork: [3, 1, 4, 2]
 - hemp: [1, 2, 4, 3]
 - judy: [1, 4, 2, 3]
 - junk: [1, 4, 3, 2]
 - limn: [1, 2, 4, 3]
 - quip: [1, 4, 2, 3]
 - swag: [3, 4, 1, 2]
 - visa: [4, 2, 3, 1]
 - wish: [4, 2, 3, 1]

And we can compute the number of solutions, and compare with the number found earlier.

if solve(sols=ALL) is SAT:
    print("Number of solutions: ", n_solutions())

Number of solutions:  24

Finally, we give below the model in one piece.

from pycsp3 import *

words = ["buoy", "cave", "celt", "flub", "fork", "hemp", "judy", "junk", "limn", "quip", "swag", "visa", "wish"]

letters = alphabet_positions(words)  # the indexes of present letters
cubes = range(1, 5)                  # the indexes 0, 1, 2, 3 of the four cubes

# x[i] is the cube where the ith letter of the alphabet is put
x = VarArray(size=26, dom=lambda i: cubes if i in letters else None)

satisfy(
    # the four letters of each word appear on different cubes
    [AllDifferent(x[i] for i in alphabet_positions(w)) for w in words],

    # each cube is assigned 6 letters
    Cardinality(x, occurrences={i: 6 for i in cubes})
)