Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a 2x2 grid and I have 5 tokens. I want to place 4 of the 5 tokens on the grid.

Each token has a different value depending on where they are placed on the grid. Essentially if they should not be placed in a certain position they are awarded a value of 20, otherwise they have a score lower than 20.

I am writing a program that needs to figure out which 4 tokens should be placed, in order to use the ones with the lowest value possible.

I need this part of the program to be as fast as possible. I'm wondering if there is an optimal algorithm I should use. I have been researching and came across the Hungarian algorithm but I'm wondering if there is another option I should be considering.

Here is an example of the problem:

My grid has its' positions labelled, a,b,c,d ...

+--------+--------+ | c | d | | | | +--------+--------+ | a | b | | | | +--------+--------+

And I have the following tokens with corresponding values for each location on the grid... a b c d token_p = [20, 20, 15, 20] token_r = [ 1, 1, 20, 20] token_s = [15, 20, 20, 20] token_t = [20, 10, 20, 10] token_u = [20, 20, 5, 20]

The answer should be:

token_s = a (value 15)

token_r = b (value 1)

token_u = c (value 5)

token_t = d (value 10)

share|cite|improve this question

I would create a weighted $K_{t, n}$ graph, with tokens in one partition and grid slots on the other, and use a greedy bipartite matching algorithm.

Here is a tutorial on general bipartite matching:

You will have to adapt it for a greedy approach.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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