Mixing
Calculating the Search Space for Dr. Eureka's Puzzle
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
I have to prepare an algorithm to solve the puzzle part of Dr. Eureka, a multiplayer game from Blue Orange Games. This is part of a research project that also involves computer vision and robotics. The game also involves agility and dexterity, but here I am looking for advice on the logic puzzle part only. Here is an image
In particular I need some advice on calculating the search space. There are three tubes and six balls of three different colors (two balls of each color). Up to four balls can be stacked inside each tube, in a specific order. All balls must be inside a tube, but each tube may hold four, three, two, one, or no balls. The order of the tubes may be rearranged (e.g. if tube A has balls green and red, and tube B has the purple ball, this is the same as if tube A had the purple ball and tube B had balls blue and red). Also, a tube may be flipped over, upside-down, so reversing the order also does not matter.
The number of possible solutions to a given game goal (to match the picture in the card) can be calculated as the sum of all permutations of balls of same colors (8 permutations of colors) times the possible flip-overs (8 permutations of flip-overs) times the possible order of the three tubes (6 permutations of order of tubes), resulting in 384 possible configurations.
I seek some advice on how to calculate the number of possible valid configuration states for this game.
combinatorics combinations
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
add a comment |Â
up vote
1
down vote
favorite
I have to prepare an algorithm to solve the puzzle part of Dr. Eureka, a multiplayer game from Blue Orange Games. This is part of a research project that also involves computer vision and robotics. The game also involves agility and dexterity, but here I am looking for advice on the logic puzzle part only. Here is an image
In particular I need some advice on calculating the search space. There are three tubes and six balls of three different colors (two balls of each color). Up to four balls can be stacked inside each tube, in a specific order. All balls must be inside a tube, but each tube may hold four, three, two, one, or no balls. The order of the tubes may be rearranged (e.g. if tube A has balls green and red, and tube B has the purple ball, this is the same as if tube A had the purple ball and tube B had balls blue and red). Also, a tube may be flipped over, upside-down, so reversing the order also does not matter.
The number of possible solutions to a given game goal (to match the picture in the card) can be calculated as the sum of all permutations of balls of same colors (8 permutations of colors) times the possible flip-overs (8 permutations of flip-overs) times the possible order of the three tubes (6 permutations of order of tubes), resulting in 384 possible configurations.
I seek some advice on how to calculate the number of possible valid configuration states for this game.
combinatorics combinations
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
Nice question! I take it that the balls are subject to gravity? So if you flip a tube, you're reversing not its entire contents (including the empty spaces), but rather the empty spaces end up on top again and only the part filled with balls is reversed?
– joriki
Jul 25 at 18:11
You say you want to "calculate the search space" and "formalize the space of possible solutions". What exactly do you mean by that? Do you want to count the number of inequivalent configurations? Or describe them somehow? If so, what sort of description would be useful to you? -- Ah, you just answered that question by an edit while I was writing it :-)
– joriki
Jul 25 at 18:18
Hi @joriki. Yes, indeed the balls are subject to gravity (it's an actual physical game). So when you flip, the spaces move to the top. Also, on the "search space" vs. "possible solutions", you were quicker than me on spotting this -- I apologize. I want to count both actually. I need to have an idea of the size of the problem, to decide whether or not it makes sense using a very classical approach, like Dijkstra algorithm. Dijkstra is almost like brute force, so for a large search space it may not be feasible (the game has to be played fast).
– Rodrigo Da Silva Guerra
Jul 25 at 18:23
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
I have to prepare an algorithm to solve the puzzle part of Dr. Eureka, a multiplayer game from Blue Orange Games. This is part of a research project that also involves computer vision and robotics. The game also involves agility and dexterity, but here I am looking for advice on the logic puzzle part only. Here is an image
In particular I need some advice on calculating the search space. There are three tubes and six balls of three different colors (two balls of each color). Up to four balls can be stacked inside each tube, in a specific order. All balls must be inside a tube, but each tube may hold four, three, two, one, or no balls. The order of the tubes may be rearranged (e.g. if tube A has balls green and red, and tube B has the purple ball, this is the same as if tube A had the purple ball and tube B had balls blue and red). Also, a tube may be flipped over, upside-down, so reversing the order also does not matter.
The number of possible solutions to a given game goal (to match the picture in the card) can be calculated as the sum of all permutations of balls of same colors (8 permutations of colors) times the possible flip-overs (8 permutations of flip-overs) times the possible order of the three tubes (6 permutations of order of tubes), resulting in 384 possible configurations.
I seek some advice on how to calculate the number of possible valid configuration states for this game.
combinatorics combinations
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
I have to prepare an algorithm to solve the puzzle part of Dr. Eureka, a multiplayer game from Blue Orange Games. This is part of a research project that also involves computer vision and robotics. The game also involves agility and dexterity, but here I am looking for advice on the logic puzzle part only. Here is an image
In particular I need some advice on calculating the search space. There are three tubes and six balls of three different colors (two balls of each color). Up to four balls can be stacked inside each tube, in a specific order. All balls must be inside a tube, but each tube may hold four, three, two, one, or no balls. The order of the tubes may be rearranged (e.g. if tube A has balls green and red, and tube B has the purple ball, this is the same as if tube A had the purple ball and tube B had balls blue and red). Also, a tube may be flipped over, upside-down, so reversing the order also does not matter.
The number of possible solutions to a given game goal (to match the picture in the card) can be calculated as the sum of all permutations of balls of same colors (8 permutations of colors) times the possible flip-overs (8 permutations of flip-overs) times the possible order of the three tubes (6 permutations of order of tubes), resulting in 384 possible configurations.
I seek some advice on how to calculate the number of possible valid configuration states for this game.
combinatorics combinations
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
edited Jul 25 at 18:18
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
asked Jul 25 at 18:02
Rodrigo Da Silva Guerra
92
92
Nice question! I take it that the balls are subject to gravity? So if you flip a tube, you're reversing not its entire contents (including the empty spaces), but rather the empty spaces end up on top again and only the part filled with balls is reversed?
– joriki
Jul 25 at 18:11
You say you want to "calculate the search space" and "formalize the space of possible solutions". What exactly do you mean by that? Do you want to count the number of inequivalent configurations? Or describe them somehow? If so, what sort of description would be useful to you? -- Ah, you just answered that question by an edit while I was writing it :-)
– joriki
Jul 25 at 18:18
Hi @joriki. Yes, indeed the balls are subject to gravity (it's an actual physical game). So when you flip, the spaces move to the top. Also, on the "search space" vs. "possible solutions", you were quicker than me on spotting this -- I apologize. I want to count both actually. I need to have an idea of the size of the problem, to decide whether or not it makes sense using a very classical approach, like Dijkstra algorithm. Dijkstra is almost like brute force, so for a large search space it may not be feasible (the game has to be played fast).
– Rodrigo Da Silva Guerra
Jul 25 at 18:23
add a comment |Â
Nice question! I take it that the balls are subject to gravity? So if you flip a tube, you're reversing not its entire contents (including the empty spaces), but rather the empty spaces end up on top again and only the part filled with balls is reversed?
– joriki
Jul 25 at 18:11
You say you want to "calculate the search space" and "formalize the space of possible solutions". What exactly do you mean by that? Do you want to count the number of inequivalent configurations? Or describe them somehow? If so, what sort of description would be useful to you? -- Ah, you just answered that question by an edit while I was writing it :-)
– joriki
Jul 25 at 18:18
Hi @joriki. Yes, indeed the balls are subject to gravity (it's an actual physical game). So when you flip, the spaces move to the top. Also, on the "search space" vs. "possible solutions", you were quicker than me on spotting this -- I apologize. I want to count both actually. I need to have an idea of the size of the problem, to decide whether or not it makes sense using a very classical approach, like Dijkstra algorithm. Dijkstra is almost like brute force, so for a large search space it may not be feasible (the game has to be played fast).
– Rodrigo Da Silva Guerra
Jul 25 at 18:23
Nice question! I take it that the balls are subject to gravity? So if you flip a tube, you're reversing not its entire contents (including the empty spaces), but rather the empty spaces end up on top again and only the part filled with balls is reversed?
– joriki
Jul 25 at 18:11
Nice question! I take it that the balls are subject to gravity? So if you flip a tube, you're reversing not its entire contents (including the empty spaces), but rather the empty spaces end up on top again and only the part filled with balls is reversed?
– joriki
Jul 25 at 18:11
You say you want to "calculate the search space" and "formalize the space of possible solutions". What exactly do you mean by that? Do you want to count the number of inequivalent configurations? Or describe them somehow? If so, what sort of description would be useful to you? -- Ah, you just answered that question by an edit while I was writing it :-)
– joriki
Jul 25 at 18:18
You say you want to "calculate the search space" and "formalize the space of possible solutions". What exactly do you mean by that? Do you want to count the number of inequivalent configurations? Or describe them somehow? If so, what sort of description would be useful to you? -- Ah, you just answered that question by an edit while I was writing it :-)
– joriki
Jul 25 at 18:18
Hi @joriki. Yes, indeed the balls are subject to gravity (it's an actual physical game). So when you flip, the spaces move to the top. Also, on the "search space" vs. "possible solutions", you were quicker than me on spotting this -- I apologize. I want to count both actually. I need to have an idea of the size of the problem, to decide whether or not it makes sense using a very classical approach, like Dijkstra algorithm. Dijkstra is almost like brute force, so for a large search space it may not be feasible (the game has to be played fast).
– Rodrigo Da Silva Guerra
Jul 25 at 18:23
Hi @joriki. Yes, indeed the balls are subject to gravity (it's an actual physical game). So when you flip, the spaces move to the top. Also, on the "search space" vs. "possible solutions", you were quicker than me on spotting this -- I apologize. I want to count both actually. I need to have an idea of the size of the problem, to decide whether or not it makes sense using a very classical approach, like Dijkstra algorithm. Dijkstra is almost like brute force, so for a large search space it may not be feasible (the game has to be played fast).
– Rodrigo Da Silva Guerra
Jul 25 at 18:23
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
I think you are in for careful counting. There are only five combinations of numbers of balls in tubes$-4+1+1,4+2+0,3+3+0,3+2+1,2+2+2$ If we take the $4+1+1$ case the two $1$s can be the same color or different. If they are the same there are $3$ choices for that color and three choices for how to stack the $4$-the colors can alternate or either of the two remaining colors can be on the ends, so that gives $9$ possibilities. If the two $1$s are different there are three ways to choose those two colors, and $6$ ways to order the $4$ balls because there are no symmetric arrangements, for $18$. Thus $4+1+1$ gives $27$ arrangements. Now do the other four the same way.
answered Jul 25 at 18:19
Ross Millikan
275k21186351
add a comment |Â
up vote
0
down vote
Implemented Solution
Okay, I just implemented a solution to this puzzle here: https://colab.research.google.com/drive/1UFUtajkD8JgZSGVN0I_h6qa5EqiMz6nS
Thank you for all the comments.
Below I leave my answer from before:
I like the answer from Ross Millikan. So I would like to develop from there, but slightly differently. Let's start with the five configurations of balls in the tubes 4 1 1, 4 2 0, 3 3 0, 3 2 1, 2 2 2.
For each configuration, the 6 the balls can be organized in 6!=720 ways (not yet accounting for the different colors). Note it does not matter, for now, in where each ball is, so all the 5 configurations hold 6 places for balls, and these places can be filled in 6! ways with the actual balls.
Now accounting for colors. Since there are 2 balls of each of the 3 colors, for every possible way of arranging the balls, there are always 2*2*2=8 different permutations of balls result in that same state.
This reduces the total to 720/8 = 90 states for each of the 5 configurations, giving a total of 450 states. This is a much smaller problem than I initially imagined.
Regarding the flip-overs, I think these should not be modeled as different states, but rather as transitions. So there are two ways to perform a transition: either by moving a ball from the top of one tube to the top of another, or by flipping over one (or more) tubes. So, when there is symmetry, the flip-over does not result in a change of states.
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
I think you are in for careful counting. There are only five combinations of numbers of balls in tubes$-4+1+1,4+2+0,3+3+0,3+2+1,2+2+2$ If we take the $4+1+1$ case the two $1$s can be the same color or different. If they are the same there are $3$ choices for that color and three choices for how to stack the $4$-the colors can alternate or either of the two remaining colors can be on the ends, so that gives $9$ possibilities. If the two $1$s are different there are three ways to choose those two colors, and $6$ ways to order the $4$ balls because there are no symmetric arrangements, for $18$. Thus $4+1+1$ gives $27$ arrangements. Now do the other four the same way.
answered Jul 25 at 18:19
Ross Millikan
275k21186351
add a comment |Â
up vote
0
down vote
I think you are in for careful counting. There are only five combinations of numbers of balls in tubes$-4+1+1,4+2+0,3+3+0,3+2+1,2+2+2$ If we take the $4+1+1$ case the two $1$s can be the same color or different. If they are the same there are $3$ choices for that color and three choices for how to stack the $4$-the colors can alternate or either of the two remaining colors can be on the ends, so that gives $9$ possibilities. If the two $1$s are different there are three ways to choose those two colors, and $6$ ways to order the $4$ balls because there are no symmetric arrangements, for $18$. Thus $4+1+1$ gives $27$ arrangements. Now do the other four the same way.
answered Jul 25 at 18:19
Ross Millikan
275k21186351
add a comment |Â
up vote
0
down vote
up vote
0
down vote
I think you are in for careful counting. There are only five combinations of numbers of balls in tubes$-4+1+1,4+2+0,3+3+0,3+2+1,2+2+2$ If we take the $4+1+1$ case the two $1$s can be the same color or different. If they are the same there are $3$ choices for that color and three choices for how to stack the $4$-the colors can alternate or either of the two remaining colors can be on the ends, so that gives $9$ possibilities. If the two $1$s are different there are three ways to choose those two colors, and $6$ ways to order the $4$ balls because there are no symmetric arrangements, for $18$. Thus $4+1+1$ gives $27$ arrangements. Now do the other four the same way.
answered Jul 25 at 18:19
Ross Millikan
275k21186351
I think you are in for careful counting. There are only five combinations of numbers of balls in tubes$-4+1+1,4+2+0,3+3+0,3+2+1,2+2+2$ If we take the $4+1+1$ case the two $1$s can be the same color or different. If they are the same there are $3$ choices for that color and three choices for how to stack the $4$-the colors can alternate or either of the two remaining colors can be on the ends, so that gives $9$ possibilities. If the two $1$s are different there are three ways to choose those two colors, and $6$ ways to order the $4$ balls because there are no symmetric arrangements, for $18$. Thus $4+1+1$ gives $27$ arrangements. Now do the other four the same way.
answered Jul 25 at 18:19
Ross Millikan
275k21186351
edited Jul 25 at 18:21
answered Jul 25 at 18:19
Ross Millikan
275k21186351
answered Jul 25 at 18:19
Ross Millikan
275k21186351
answered Jul 25 at 18:19
Ross Millikan
275k21186351
275k21186351
add a comment |Â
add a comment |Â
up vote
0
down vote
Implemented Solution
Okay, I just implemented a solution to this puzzle here: https://colab.research.google.com/drive/1UFUtajkD8JgZSGVN0I_h6qa5EqiMz6nS
Thank you for all the comments.
Below I leave my answer from before:
I like the answer from Ross Millikan. So I would like to develop from there, but slightly differently. Let's start with the five configurations of balls in the tubes 4 1 1, 4 2 0, 3 3 0, 3 2 1, 2 2 2.
For each configuration, the 6 the balls can be organized in 6!=720 ways (not yet accounting for the different colors). Note it does not matter, for now, in where each ball is, so all the 5 configurations hold 6 places for balls, and these places can be filled in 6! ways with the actual balls.
Now accounting for colors. Since there are 2 balls of each of the 3 colors, for every possible way of arranging the balls, there are always 2*2*2=8 different permutations of balls result in that same state.
This reduces the total to 720/8 = 90 states for each of the 5 configurations, giving a total of 450 states. This is a much smaller problem than I initially imagined.
Regarding the flip-overs, I think these should not be modeled as different states, but rather as transitions. So there are two ways to perform a transition: either by moving a ball from the top of one tube to the top of another, or by flipping over one (or more) tubes. So, when there is symmetry, the flip-over does not result in a change of states.
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
add a comment |Â
up vote
0
down vote
Implemented Solution
Okay, I just implemented a solution to this puzzle here: https://colab.research.google.com/drive/1UFUtajkD8JgZSGVN0I_h6qa5EqiMz6nS
Thank you for all the comments.
Below I leave my answer from before:
I like the answer from Ross Millikan. So I would like to develop from there, but slightly differently. Let's start with the five configurations of balls in the tubes 4 1 1, 4 2 0, 3 3 0, 3 2 1, 2 2 2.
For each configuration, the 6 the balls can be organized in 6!=720 ways (not yet accounting for the different colors). Note it does not matter, for now, in where each ball is, so all the 5 configurations hold 6 places for balls, and these places can be filled in 6! ways with the actual balls.
Now accounting for colors. Since there are 2 balls of each of the 3 colors, for every possible way of arranging the balls, there are always 2*2*2=8 different permutations of balls result in that same state.
This reduces the total to 720/8 = 90 states for each of the 5 configurations, giving a total of 450 states. This is a much smaller problem than I initially imagined.
Regarding the flip-overs, I think these should not be modeled as different states, but rather as transitions. So there are two ways to perform a transition: either by moving a ball from the top of one tube to the top of another, or by flipping over one (or more) tubes. So, when there is symmetry, the flip-over does not result in a change of states.
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Implemented Solution
Okay, I just implemented a solution to this puzzle here: https://colab.research.google.com/drive/1UFUtajkD8JgZSGVN0I_h6qa5EqiMz6nS
Thank you for all the comments.
Below I leave my answer from before:
I like the answer from Ross Millikan. So I would like to develop from there, but slightly differently. Let's start with the five configurations of balls in the tubes 4 1 1, 4 2 0, 3 3 0, 3 2 1, 2 2 2.
For each configuration, the 6 the balls can be organized in 6!=720 ways (not yet accounting for the different colors). Note it does not matter, for now, in where each ball is, so all the 5 configurations hold 6 places for balls, and these places can be filled in 6! ways with the actual balls.
Now accounting for colors. Since there are 2 balls of each of the 3 colors, for every possible way of arranging the balls, there are always 2*2*2=8 different permutations of balls result in that same state.
This reduces the total to 720/8 = 90 states for each of the 5 configurations, giving a total of 450 states. This is a much smaller problem than I initially imagined.
Regarding the flip-overs, I think these should not be modeled as different states, but rather as transitions. So there are two ways to perform a transition: either by moving a ball from the top of one tube to the top of another, or by flipping over one (or more) tubes. So, when there is symmetry, the flip-over does not result in a change of states.
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
Implemented Solution
Okay, I just implemented a solution to this puzzle here: https://colab.research.google.com/drive/1UFUtajkD8JgZSGVN0I_h6qa5EqiMz6nS
Thank you for all the comments.
Below I leave my answer from before:
I like the answer from Ross Millikan. So I would like to develop from there, but slightly differently. Let's start with the five configurations of balls in the tubes 4 1 1, 4 2 0, 3 3 0, 3 2 1, 2 2 2.
For each configuration, the 6 the balls can be organized in 6!=720 ways (not yet accounting for the different colors). Note it does not matter, for now, in where each ball is, so all the 5 configurations hold 6 places for balls, and these places can be filled in 6! ways with the actual balls.
Now accounting for colors. Since there are 2 balls of each of the 3 colors, for every possible way of arranging the balls, there are always 2*2*2=8 different permutations of balls result in that same state.
This reduces the total to 720/8 = 90 states for each of the 5 configurations, giving a total of 450 states. This is a much smaller problem than I initially imagined.
Regarding the flip-overs, I think these should not be modeled as different states, but rather as transitions. So there are two ways to perform a transition: either by moving a ball from the top of one tube to the top of another, or by flipping over one (or more) tubes. So, when there is symmetry, the flip-over does not result in a change of states.
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
edited Jul 25 at 23:52
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
answered Jul 25 at 19:21
Rodrigo Da Silva Guerra
92
92
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2862674%2fcalculating-the-search-space-for-dr-eurekas-puzzle%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Nice question! I take it that the balls are subject to gravity? So if you flip a tube, you're reversing not its entire contents (including the empty spaces), but rather the empty spaces end up on top again and only the part filled with balls is reversed?
– joriki
Jul 25 at 18:11
You say you want to "calculate the search space" and "formalize the space of possible solutions". What exactly do you mean by that? Do you want to count the number of inequivalent configurations? Or describe them somehow? If so, what sort of description would be useful to you? -- Ah, you just answered that question by an edit while I was writing it :-)
– joriki
Jul 25 at 18:18
Hi @joriki. Yes, indeed the balls are subject to gravity (it's an actual physical game). So when you flip, the spaces move to the top. Also, on the "search space" vs. "possible solutions", you were quicker than me on spotting this -- I apologize. I want to count both actually. I need to have an idea of the size of the problem, to decide whether or not it makes sense using a very classical approach, like Dijkstra algorithm. Dijkstra is almost like brute force, so for a large search space it may not be feasible (the game has to be played fast).
– Rodrigo Da Silva Guerra
Jul 25 at 18:23