CSP medium

Problem Quasigroup Existence

From CSPLib (Problem 03): A quasigroup of order n is a $n \times n$ multiplication table in which each element occurs once in every row and column (i.e., is a Latin square), while satisfying some specific properties. Hence, the result a*b of applying the multiplication operator * on a (left operand) and b (right operand) is given by the value in the table at row a and column b. Classical variants of quasigroup existence correspond to taking into account the following properties:

QG3: quasigroups for which $(ab)(b*a)=a$
QG4: quasigroups for which $(ba)(a*b)=a$
QG5: quasigroups for which $((ba)b)*b=a$
QG6: quasigroups for which $(ab)b=a(ab)$
QG7: quasigroups for which $(ba)b=a(ba)$

For each of these problems, we may additionally demand that the quasigroup is idempotent. That is, $a*a=a$ for every element $a$. This is what we consider below.

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. Actually, we just need an integer $n$. For example, the value 5.

n = 5

We start our CSP model by introducing an array $x$ of variables.

# x[i][j] is the value at row i and column j of the quasi-group
x = VarArray(size=[n, n], dom=range(n))

We can display the structure of the array, as well as the domain of the first variable (note that all variables have the same domain).

print("Array x: ", x)
print("Domain of any variable: ", x[0][0].dom)

Array x:  [
  [x[0][0], x[0][1], x[0][2], x[0][3], x[0][4]]
  [x[1][0], x[1][1], x[1][2], x[1][3], x[1][4]]
  [x[2][0], x[2][1], x[2][2], x[2][3], x[2][4]]
  [x[3][0], x[3][1], x[3][2], x[3][3], x[3][4]]
  [x[4][0], x[4][1], x[4][2], x[4][3], x[4][4]]
]
Domain of any variable:  0..4

Concerning the constraints, we have to post first a constraint AllDifferentMatrix in order to impose a Latin square.

satisfy(
   # ensuring a Latin square
   AllDifferent(x, matrix=True)
);

Then, we post a group of unary constraints Intension to enforce idempotence.

satisfy(
   # ensuring idempotence  tag(idempotence)
   x[i][i] == i for i in range(n)
);

We can display the internal representation of the posted constraints; this way, although a little bit technical, we can see that the arguments of the constraints are correct (note that ‘eq’ stands for ‘equal to’).

print(posted())

allDifferent(matrix:(x[0][0],x[0][1],x[0][2],x[0][3],x[0][4])(x[1][0],x[1][1],x[1][2],x[1][3],x[1][4])(x[2][0],x[2][1],x[2][2],x[2][3],x[2][4])(x[3][0],x[3][1],x[3][2],x[3][3],x[3][4])(x[4][0],x[4][1],x[4][2],x[4][3],x[4][4]))
intension(function:eq(x[0][0],0))
intension(function:eq(x[1][1],1))
intension(function:eq(x[2][2],2))
intension(function:eq(x[3][3],3))
intension(function:eq(x[4][4],4))

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

if solve() is SAT:
    print(values(x))

[
  [0, 2, 1, 4, 3]
  [3, 1, 4, 0, 2]
  [4, 3, 2, 1, 0]
  [2, 4, 0, 3, 1]
  [1, 0, 3, 2, 4]
]

We can see that until now everything is on the right track.

We now introduce the three representative variants QG4, QG5 and QG7 for wich the existence of a quasigroup is guaranteed for $n =5$.

QG4

For the variant QG4, we have to post a group of constraints ElementMatrix:

satisfy(
    x[x[j][i], x[i][j]] == i for i in range(n) for j in range(n)
);

For control, we can display the two last posted constraints:

print(posted()[-2:])

element(matrix:(x[0][0],x[0][1],x[0][2],x[0][3],x[0][4])(x[1][0],x[1][1],x[1][2],x[1][3],x[1][4])(x[2][0],x[2][1],x[2][2],x[2][3],x[2][4])(x[3][0],x[3][1],x[3][2],x[3][3],x[3][4])(x[4][0],x[4][1],x[4][2],x[4][3],x[4][4]), index:[x[3][4], x[4][3]], condition:(eq,4))
element(matrix:(x[0][0],x[0][1],x[0][2],x[0][3],x[0][4])(x[1][0],x[1][1],x[1][2],x[1][3],x[1][4])(x[2][0],x[2][1],x[2][2],x[2][3],x[2][4])(x[3][0],x[3][1],x[3][2],x[3][3],x[3][4])(x[4][0],x[4][1],x[4][2],x[4][3],x[4][4]), index:[x[4][4], x[4][4]], condition:(eq,4))

An we can run the solver.

if solve() is SAT:
    print(values(x))

[
  [0, 2, 1, 4, 3]
  [3, 1, 4, 0, 2]
  [4, 3, 2, 1, 0]
  [2, 4, 0, 3, 1]
  [1, 0, 3, 2, 4]
]

We can compute the number of solutions as follows:

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

Number of solutions:  12

QG5

For the variant QG5, we have to post a group of complex constraints Intension. They will be partly decomposed by introducing auxiliary variables and constraints Element, in order to remain in the perimeter of XSCP$^3$-core.

But first, we have to remove all constraints that have been posted at the last call to satisfy().

unpost()

We can check that these constraints have been discarded.

print(posted())

allDifferent(matrix:x[][])
instantiation(list:x[0][0] x[1][1] x[2][2] x[3][3] x[4][4], values:[0, 1, 2, 3, 4])

We post the new group of constraints:

satisfy(
    x[x[x[j,i],j],j] == i for i in range(n) for j in range(n)
);

We run the solver.

if solve() is SAT:
    print(values(x))

[
  [0, 2, 1, 4, 3]
  [3, 1, 4, 0, 2]
  [4, 3, 2, 1, 0]
  [2, 4, 0, 3, 1]
  [1, 0, 3, 2, 4]
]

And we compute the number of solutions.

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

Number of solutions:  6

QG7

For the variant QG7, we have to post a group of complex constraints Intension. They will be decomposed by introducing auxiliary variables and constraints Element, in order to remain in the perimeter of XSCP$^3$-core.

But first, we have to remove all constraints that have been posted at the last call to satisfy().

unpost()

We post the new group of constraints:

satisfy(
    x[x[j][i],j] == x[i,x[j][i]] for i in range(n) for j in range(n)
);

We run the solver.

if solve() is SAT:
    print(values(x))

[
  [0, 2, 1, 4, 3]
  [3, 1, 4, 0, 2]
  [4, 3, 2, 1, 0]
  [2, 4, 0, 3, 1]
  [1, 0, 3, 2, 4]
]

And we compute the number of solutions.

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

Number of solutions:  12

Finally, we give below the model in one piece. Here the data is expected to be given by the user (in a command line). The user must also indicate the variant (with the option -variant on the command line).

from pycsp3 import *

n = data or 8

# x[i][j] is the value at row i and column j of the quasi-group
x = VarArray(size=[n, n], dom=range(n))

satisfy(
    # ensuring a Latin square
    AllDifferent(x, matrix=True),

    # ensuring idempotence  tag(idempotence)
    [x[i][i] == i for i in range(n)]
)


if variant("v3"):
    satisfy(
        x[x[i][j], x[j][i]] == i for i in range(n) for j in range(n)
    )
elif variant("v4"):
    satisfy(
        x[x[j][i], x[i][j]] == i for i in range(n) for j in range(n)
    )
elif variant("v5"):
    satisfy(
        x[x[x[j][i], j], j] == i for i in range(n) for j in range(n)
    )
elif variant("v6"):
    satisfy(
        x[x[i][j], j] == x[i, x[i][j]] for i in range(n) for j in range(n)
    )
elif variant("v7"):
    satisfy(
        x[x[j][i], j] == x[i, x[j][i]] for i in range(n) for j in range(n)
    )