type: CSP

difficulty: medium

# Problem *Quasigroup Existence*

From CSPLib: 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 $(a
*b)*(b*a)=a$ - QG4: quasigroups for which $(b
*a)*(a*b)=a$ - QG5: quasigroups for which $((b
*a)*b)*b=a$ - QG6: quasigroups for which $(a
*b)*b=a*(a*b)$ - QG7: quasigroups for which $(b
*a)*b=a*(b*a)$

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)
)
```