Search code examples
algorithmmatrixnearest-neighborneighbours

Avoid clash of positions in a matrix algorithm

Assume you have a n x m matrix. In this matrix, you will be randomly positioning FOUR different objects say a, b, c, d. There will be many of each.

Now what is the best algorithm so that when they are randomly placed, their positions don't clash?

My approach would be to:

  1. Randomly place them
  2. Check through all the object's position, and if they clash, keep on moving until an empty space is found?

I am just wondering if there is any other efficient solution.

Solution

  • If the end goal is to fill the board, you could just choose for each space on the matrix which type goes on it (the choice is random).

    To add an option of an empty space, add a fifth option of NO_TYPE.

    If the number of appearances is known, try this:

    1. Create a list of size n X m (call it L) with values 1..L.

    2. For each appearance, choose randomly from the list ( something like pos = rand(L) and the remove that value form the list (don't forget to decrease L).

    3. Do this as many times as the necessary.