### 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.

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