Imagine a game on a grid of $m$ rows and $n$ columns. Player One will place a fixed number $r$ of markers in each row. Player Two will select the two rows which maximize the number of columns having markers in both rows, while Player One will try to minimize this number.


  • $m = 3$
  • $n = 3$
  • $r = 2$

(a $3\times 3$ grid, placing 2 markers in each row)

First, Player One chooses two columns in each row, and places markers in those cells:

$$ \begin{array}{|c|c|c|} \hline X&X&\\ \hline X&X&\\ \hline &X&X\\ \hline \end{array} $$

Player Two then checks the row pairs $(1,2),(1,3)$ and $(2,3)$. The first pair shares 2 columns, and the last two pairs share only 1 column, so Player Two selects rows 1 and 2 because they have the most matching columns (2).

I am looking for a general strategy for placing markers given $(m,n,r)$. The strategy need not be optimal as it is intended to be uses in stochastic local search. This problem arises as a sub problem in investment design in finance. An easy to calculate lower bound exist, and for almost all instances I have seen a solution where the similarity is this lower bound exist.

Example instances: $(10,30,9)$ has lower bound 2. $(11,22,10)$ has lower bound 4.

The instance $(10,8,3)$ has a lower bound of 2 with the following solution: $$ \begin{array}{|c|c|c|c|c|c|c|c|} \hline X&X&X&&&&&\\ \hline X&X&&X&&&&\\ \hline X&X&&&X&&&\\ \hline X&X&&&&X&&\\ \hline X&X&&&&&X&\\ \hline X&X&&&&&&X\\ \hline X&&X&X&&&&\\ \hline X&&X&&X&&&\\ \hline X&&X&&&X&&\\ \hline X&&X&&&&X&\\ \hline \end{array} $$

The most similar rows (1 and 2, among others) share 2 markers and the solution is therefore optimal.

  • $\begingroup$ "Player one will place a fixed number $r$ of markers such that the two rows." - is there supposed to be more here? It sounds like player one is placing $r$ markers in each row, is that correct? $\endgroup$
    – DylanSp
    Feb 3, 2016 at 13:51
  • $\begingroup$ @DylanSp You're right! I must have changed my mind when phrasing the question. Thanks for pointing that out. $\endgroup$
    – Block
    Feb 3, 2016 at 13:56
  • $\begingroup$ Can you check your example instances? If m=10 and n=30, how can r be 90? 90 markers in each row, but there's only space for 30 markers. I feel like the order of those numbers should be changed. $\endgroup$
    – Duncan
    Feb 3, 2016 at 17:55
  • 1
    $\begingroup$ Do you have solutions for your lower bound examples? I'm playing around with it, but can't figure out how to get anywhere close to those numbers. $\endgroup$
    – Matt
    Feb 4, 2016 at 14:26
  • 1
    $\begingroup$ @Matt I have added an example of an optimal solution. $\endgroup$
    – Block
    Feb 4, 2016 at 15:45

1 Answer 1


The following brutish algorithm does okay, it might be a start. It generates an optimal solution for $(10,8,3)$ and gets scores of 3 and 6 for $(10,30,9)$ and $(11,22,10)$, respectively by building the board one row at a time.

To create the first row, place markers in the first $r$ columns. To generate the next row, $R$, start with a row with no markers. While $R$ has less than $r$ markers:

  • For each column $i$, create a candidate row $R_i$ which is $R$ but with a marker added to column $i$. (If $R$ already has a marker in column $i$, ignore this candidate).
  • Score $R_i$ pairwise against each other row already added to the board, note the highest pairwise scoring as $S_i$.
  • Among the rows already in the board, count how many also have a marker in column $i$, denote this count as $C_i$.
  • Choose the column $c$ so that $S_c \le S_j$ for any $j \ne c$. If there are two columns with the same minimum score, choose the column with the lower $C_c$.
  • Add a marker into column $c$.

Do this until all the rows have been generated.

For $(10,8,3)$ this generates the following table. Markers are numbered as they are added:

\begin{array}{|c|c|c|c|c|c|c|c|} \hline 1&2&3&&&&&\\ \hline &&&1&2&3&&\\ \hline 3&&&&&&1&2\\ \hline &1&&2&&&3&\\ \hline &&1&&2&&&3\\ \hline 2&3&&&&1&&\\ \hline &&1&2&3&&&\\ \hline &&3&&&1&2&\\ \hline 3&2&&&&&&1\\ \hline &&&1&3&&&2\\ \hline \end{array}

A gist with a Python implementation can be found here: https://gist.github.com/maafy6/d414a7a561116f784063

  • $\begingroup$ I have Python code that I'm using to test this out. Not sure what the etiquette on posting that in the answer is. $\endgroup$
    – Matt
    Feb 4, 2016 at 16:37
  • 1
    $\begingroup$ Looks promising! I am going to take a proper look during the week end. Thanks! $\endgroup$
    – Block
    Feb 5, 2016 at 12:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.