# Trouble with an algorithm

This topic is 4555 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

What I am trying to implement here is an algorithm that can place x dots on a y by z grid, in all possible combinations that they can be. The dots are labeled 1 through x+1. (x, y, and z are constants) A few additional specifications are that if dot 1 is placed at (0,1) and dot 6 is placed on (5,6); and in another instance if dot 6 is placed on (0,1) and dot 1 is placed on (5,6), then they are TWO different combinations. Additionally, two dots cannot be placed on the same point. This probably sounds ridiculous, but I am doing this to try to solve for all possible combinations in a game I am making, so I can solve my game, in a sense. I don't really even know where to start, I would assume it would be a large nested for loop mess, but I really can't think of anything that would work. If anyone could help me out, that would be greatly appreciated. I know this is hard (for me anyway), so definately rating++ to someone who helps. Thank you, Dev578

##### Share on other sites
As near as I can tell, the number of different permutations you have is (y * z)!/(y * z - x)! This can be a really, really big number. Are you sure you need to find all the permutations?

##### Share on other sites
Yes, it's a permutation problem--akin to 'arrange x objects in y*z places'. That's

y*zPx = (y*z)! / (y*z - x)!

as SiCrane mentioned. By the way, if the dots are labelled 1 through x+1 that makes x+1 dots in total. Just wanted to warn you, in case you plan to put that on the cover of the box of your game. [lol]

/edit: An important thing I forgot to mention--this assumes that all the dots are actually placed on the grid. If the number of dots placed is variable, then you are in an even bigger soup.

Total permutations = SUM (n = 0 to x) y*zPn

or something like that.

##### Share on other sites
Thank you, now that I know what it is called, I found a few articles on it that I am reading through. FYI, this is not going to be part of the game, it is separate, just so I can calculate all the possibilities and spit out the best solution. And yes, I understand that this will take awile to iterate through:) Rating++, and thank you.

Dev578

##### Share on other sites
Assuming x,y, and z are reasonable, you can use a recursive backtracking algorithm to generate all placements.

int grid[y][z];void BackTrack(int depth){   if(depth == x)   {      //a solution has been found   }   else   {     for(int i = 0; i < y; ++i)     {       for(int j = 0; j < z; ++j)       {         if(grid[j] == 0)         {           grid[j] = depth+1;           BackTrack(depth+1);           grid[j] = 0;         }       }      }   }}//main, or some other section of your codeint main(){  intialize grid to all 0's  BackTrack(0);  return 0;}

As has already been said, this task quickly becomes too large. If I knew more about your game, I may be able to give a better solution.

[Edited by - Forcas on December 4, 2005 6:18:12 PM]

• 9
• 13
• 40
• 15
• 11