/*------------------------------------------*
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->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->intAttachedFace][neighbor];
// the neighboring face index
if(
puzzleBox->face[fIndex].attachedPanel->index
//top face panel, the actual panel
!= boxSolution[j] )
//correct panel, panel that should be there
{
return false;
}
}
}
return true;
}
Combinatorics problem?
Author
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:
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]
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.
I can't think of an elegant solution to your problem right now, but I'll think about it.
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:
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 != position.location[canonical_solution.pointing_to]) 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';}
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:
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.
51 2 3 4 6If 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.
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]
- 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]
Author
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
