Sign in to follow this  

Combinatorics problem?

This topic is 2853 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

Okay here's the problem: I have a cube and 6 panels. The user has to paste these panels in the right cube faces(lets call them faces) to make a picture. The panels can go anywhere, as long as the final result is rotationally congruent to the solution. Also, the panels should be rotatable over the faces. So basically there's more than 1 panel-face set solution. So I can stick these panels to the box and get the user solution. So there's a 1:1 panel-face correspandence, plus the panel orientation (rotation over the face). My problem is how to check if the solution is correct. I don't know to go about this. What topic covers this problem? Graph theory? Combinatorics? Specifically? Thanks for your guidance. Edit: okay came up with a function but there seems to be some problems. First the code:
/*------------------------------------------*
	Adjacent panels in order
	Top, right, bot, left
	Basically this means that the face to the left of face 1 is boxSolution[1][3]... etc
	Visually, panel 0 is facing away from the camera, 
1 is the left side, 2 is the front, 3 is the right, 
4 is top, and 5 is bottom. 
The side panels are oriented as top being the positive y-axis, 
while panel 4's top is away from the camera, and 5's is towards the camera.

/*------------------------------------------*/
int boxSolution[6][4] =
{
	{4,1,5,3},
	{4,2,5,0},
	{4,3,5,1},
	{4,0,5,2},
	{0,3,2,1},
	{2,3,0,1}
};

/*-------------------------------------------------------*
	CheckSolution
	Evaluates the solution and returns true if correct
/*-------------------------------------------------------*/
bool Game::CheckSolution()
{
	//for each panel
	for(u32 i = 0; i < 6; i++)
	{
		//check neighbors
		
		//for each neighbor
		for(u32 j = 0; j < 4; j++)
		{
			int neighbor = ((int)j+vecPanel[i]->orientation) % 4; 
//orientation here is clockwise rotation over the face. 
//This line is since if I rotate the panel,
//the panels adjacent to it have to change indices.

			int fIndex = boxSolution[vecPanel[i]->intAttachedFace][neighbor]; 
// the neighboring face index
			if(
				puzzleBox->face[fIndex].attachedPanel->index 
//top face panel, the actual panel
				!= boxSolution[i][j] ) 
//correct panel, panel that should be there
			{
				return false;
			}

		}
	}
	return true;
}


Hope the variables are descriptive enough to understand. Anyway, the function returns true when I put panel 0 on face 0, 1 on 1 and so on. But the moment I put panel 0 somewhere else, (rotating the panels as I go, making it rotationally congruent) and so on, it returns false. Anyone care to help? [Edited by - kenjinsakura on February 23, 2010 1:43:35 AM]

Share this post


Link to post
Share on other sites
The branch of Mahematics that deals with this type of problem is called Group Theory. Or at least it deals with similar types of problems involving symmetry.

I can't think of an elegant solution to your problem right now, but I'll think about it.

Share this post


Link to post
Share on other sites
I think I figured it out. I don't understand how you are encoding the current position, so I'll describe a possible solution assuming a different description. Let's say an array `int location[6]' tells me where each panel ended up. I'll mark an edge of each panel and indicate the rotation of the panel by saying which neighbor it points to: This will be stored in `int pointing_to[6]'.

Say my canonical solution is this:
Panel 0 is at face 0, pointing to 4.
Panel 1 is at face 1, pointing to 4.
Panel 2 is at face 2, pointing to 4.
Panel 3 is at face 3, pointing to 4.
Panel 4 is at face 4, pointing to 0.
Panel 5 is at face 5, pointing to 0.

Try this:
#include <iostream>

enum Face {
Face_back, Face_left, Face_front, Face_right, Face_top, Face_bottom
};

struct Position {
int location[6]; // where each panel ended up
int pointing_to[6]; // where each panel is pointing to
};

Position canonical_solution={{0,1,2,3,4,5},{4,4,4,4,0,0}};

bool is_solution(Position const &position) {
for (int i=0; i<6; ++i) {
if (position.pointing_to[i]
!= position.location[canonical_solution.pointing_to[i]])
return false;
}
return true;
}

int main() {
Position position={{1,2,3,0,4,5},{4,4,4,4,1,1}};
std::cout << is_solution(position) << '\n';
}


Share this post


Link to post
Share on other sites
It sounds like a typical graph theory problem to me. Call the faces 1,2,3,4,5,6 and imagine they're laid out like this:


5
1 2 3 4
6




If we were to fold this back up into a cube and put face 2 on the table (so that face 4 is facing up to the sky), you could create a graph. Each node would have exactly 4 edges, pointing to the other faces that were adjacent. In addition, they should be named edges so that you maintain the consistent structure of the cube. i.e. name the edges north, south, east, west or something.

Furthermore, each node has an image with a rotation factor.

When you apply any transformation to the cube, all that happens is a) you're changing which edges point north, east, west, etc. and b) you're rotating the image 90 degrees around some axis.

So the problem is a simple search from a starting configuration to an ending configuration, where the possible operations are rotating the cube 90 degrees about the x, y, or z axis. This is a very small search space, so should be easy to solve.

Share this post


Link to post
Share on other sites
Think of it this way... First, physically, as though you'd built this thing out of wood or something:

- Assemble a reference cube which is correct.
- Paint each cube edge a different color (so that color gets on an edge of both tiles sharing that cube edge) and let the paint dry.
- Disassemble the cube.

Now, reassemble the cube however you want. It is correct if and only if the colors agree on all the cube edges.

Now: How would you code this? I'd use a "map" data structure (e.g., the one provided by the STL). Basically, you have a map, initially empty, from colors to cube edges. Now, one tile at a time, start adding the (color,cube_edge) key-value pairs to the map. If you ever overwrite an existing key with a different value, you know your cube isn't right. If you get through adding all the colors to your map without this occurring, then your cube is good.

On second thought, use a simple 1-1 hash instead of a map (i.e., an array that takes color ids as indices, and stores edge ids; it'd be initialized to all "no edge yet.") The same principle applies though.

[Edited by - Emergent on February 23, 2010 4:18:03 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by alvaro
I think I figured it out. I don't understand how you are encoding the current position, so I'll describe a possible solution assuming a different description. Let's say an array `int location[6]' tells me where each panel ended up. I'll mark an edge of each panel and indicate the rotation of the panel by saying which neighbor it points to: This will be stored in `int pointing_to[6]'.

Say my canonical solution is this:
Panel 0 is at face 0, pointing to 4.
Panel 1 is at face 1, pointing to 4.
Panel 2 is at face 2, pointing to 4.
Panel 3 is at face 3, pointing to 4.
Panel 4 is at face 4, pointing to 0.
Panel 5 is at face 5, pointing to 0.

Try this:
*** Source Snippet Removed ***


I got it. My problem was I was rotating the panels counter-clockwise instead of clockwise, so visually, it would be correct, but the data wouldn't. I think we basically came up with similar algorithms, although I had to have the complete face adjacency list encoded because I had no way of knowing where each panel was "pointing" to unless i knew its orientation, position and the face adjacency list. Complicated data structures T_T

Although, you're right, I didn't have to check all the neighbors of each panel, just 1 for each would suffice, so I took out 1 loop right there.

Thanks for the help.

Share this post


Link to post
Share on other sites

This topic is 2853 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