Sign in to follow this  

Trouble with an algorithm

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

If you intended to correct an error in the post then please contact us.

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
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[i][j] == 0)
{
grid[i][j] = depth+1;
BackTrack(depth+1);
grid[i][j] = 0;
}
}
}
}
}

//main, or some other section of your code
int 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]

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this