### 3.7.77. Degree of diversity of a set of solutions

A constraint that allows for finding a set of solutions with a certain degree of diversity. As an example, consider the problem of finding 9 diverse solutions for the 10-queens problem. For this purpose we create a 10 by 9 matrix $ℳ$ of domain variables taking their values in interval $\left[0,9\right]$. Each row of $ℳ$ corresponds to a solution of the 10-queens problem. We assume that the variables of $ℳ$ are assigned row by row, and that within a given row, they are assigned from the first to the last column. Moreover values are tried out in increasing order. We first post for each row of $ℳ$ the 3 $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints related to the 10-queens problem (see Figure 5.5.1 for an illustration of the 3 $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$). With a $\mathrm{𝚕𝚎𝚡}_\mathrm{𝚌𝚑𝚊𝚒𝚗}_\mathrm{𝚕𝚎𝚜𝚜}$ constraint, we lexicographically order the first two variables of each row of $ℳ$ in order to enforce that the first two variables of any pair of solutions are always distinct. We then impose a $\mathrm{𝚜𝚘𝚏𝚝}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚌𝚝𝚛}$ constraint on the variables of each column of $ℳ$. Let ${C}_{i}$ denote the corresponding cost variable associated with the $\mathrm{𝚜𝚘𝚏𝚝}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚌𝚝𝚛}$ constraint of the $i$-th column of $ℳ$ (i.e., the first argument of the $\mathrm{𝚜𝚘𝚏𝚝}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚌𝚝𝚛}$ constraint). We put a maximum limit (e.g., 3 in our example) on these cost variables. We also impose that the sum of these cost variables should not exceed a given maximum value (e.g., 8 in our example). Finally, in order to balance the diversity over consecutive variables we state that the sum of two consecutive cost variables should not exceed a given threshold (e.g., 2 in our example). As a result we get the following nine solutions depicted below.

• ${S}_{1}=〈0,2,5,7,9,4,8,1,3,6〉$,

• ${S}_{2}=〈0,3,5,8,2,9,7,1,4,6〉$,

• ${S}_{3}=〈1,3,7,2,8,5,9,0,6,4〉$,

• ${S}_{4}=〈2,4,8,3,9,6,1,5,7,0〉$,

• ${S}_{5}=〈3,6,9,1,4,7,0,2,5,8〉$,

• ${S}_{6}=〈5,9,2,6,3,1,8,4,0,7〉$,

• ${S}_{7}=〈6,8,1,5,0,2,4,7,9,3〉$,

• ${S}_{8}=〈8,1,4,9,7,0,3,6,2,5〉$,

• ${S}_{9}=〈9,5,0,4,1,8,6,3,7,2〉$.

The costs associated with the $\mathrm{𝚜𝚘𝚏𝚝}_\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}_\mathrm{𝚌𝚝𝚛}$ constraints of columns $1,2,...,10$ are respectively equal to 1, 1, 1, 0, 1, 0, 1, 1, 1, and 1. The different types of constraints between the previous 9 solutions are illustrated by the next figure.

Approaches for finding diverse and similar solutions based on the Hamming distance between each pair of solutions are presented by E. Hebrard and al. in