### 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 $\mathrm{\beta ³}$ of domain variables taking their values in interval $\left[0,9\right]$. Each row of $\mathrm{\beta ³}$ corresponds to a solution to the 10-queens problem. We assume that the variables of $\mathrm{\beta ³}$ 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 $\mathrm{\beta ³}$ the 3 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints related to the 10-queens problem (see FigureΒ 5.12.2 for an illustration of the 3 $\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }$ constraints). With a $\mathrm{\pi \pi \pi ‘}_\mathrm{\pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi }$ constraint, we lexicographically order the first two variables of each row of $\mathrm{\beta ³}$ in order to enforce that the first two variables of any pair of solutions are always distinct. We then impose a $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraint on the variables of each column of $\mathrm{\beta ³}$. Let ${C}_{i}$ denote the corresponding cost variable associated with the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraint of the $i$-th column of $\mathrm{\beta ³}$ (i.e., the first argument of the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ 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}=\beta ©0,2,5,7,9,4,8,1,3,6\beta ͺ$,

• ${S}_{2}=\beta ©0,3,5,8,2,9,7,1,4,6\beta ͺ$,

• ${S}_{3}=\beta ©1,3,7,2,8,5,9,0,6,4\beta ͺ$,

• ${S}_{4}=\beta ©2,4,8,3,9,6,1,5,7,0\beta ͺ$,

• ${S}_{5}=\beta ©3,6,9,1,4,7,0,2,5,8\beta ͺ$,

• ${S}_{6}=\beta ©5,9,2,6,3,1,8,4,0,7\beta ͺ$,

• ${S}_{7}=\beta ©6,8,1,5,0,2,4,7,9,3\beta ͺ$,

• ${S}_{8}=\beta ©8,1,4,9,7,0,3,6,2,5\beta ͺ$,

• ${S}_{9}=\beta ©9,5,0,4,1,8,6,3,7,2\beta ͺ$.

The costs associated with the $\mathrm{\pi \pi \pi \pi }_\mathrm{\pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi \pi }_\mathrm{\pi \pi \pi }$ constraints of columns $1,2,\beta ―,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},\beta ―,{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.