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

modelling: degree of diversity of a set of solutions A constraint that allows 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 to 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 in increasing order. We first post for each row of $ℳ$ the 3 $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints related to the 10-queens problem (see Figure 5.12.2 for an illustration of the 3 $\mathrm{𝚊𝚕𝚕𝚍𝚒𝚏𝚏𝚎𝚛𝚎𝚗𝚝}$ constraints). 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 one of the possible results 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,\cdots ,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 Figure 3.7.23. The nine diverse solutions ${S}_{1},{S}_{2},\cdots ,{S}_{9}$ are shown by Figure 3.7.24. Figure 3.7.25 depicts the distribution of all the queens of the nine solutions on a unique chessboard.

##### Figure 3.7.23. Constraint network associated with the problem of finding 9 diverse solutions for the 10-queens problem where variables are fixed to the solutions corresponding to ${S}_{1}=〈0,2,5,7,9,4,8,1,3,6〉$, ${S}_{2}=〈0,3,5,8,2,9,7,1,4,6〉$, $\cdots$, ${S}_{9}=〈9,5,0,4,1,8,6,3,7,2〉$, and where each type of constraint (hyperedge) is drawn with its own colour ##### Figure 3.7.24. Nine diverse solutions to the 10-queens problem ##### Figure 3.7.25. Distribution of the queens on the chessboard of the nine diverse solutions depicted by Figure 3.7.24 to the 10-queens problem: a red queen means two queens from two different solutions that are placed on a same cell, non-red queens of a same colour are queens that belong to a same solution; out of the $10·10$ cells of the original chessboard, $9·10-2·8=74$ cells are occupied by a single queen, 8 by two queens, and 18 by no queen at all. Approaches for finding diverse and similar solutions based on the Hamming distances between each pair of solutions are presented by E. Hebrard et al.