0
$\begingroup$

Is it possible to solve a 3x3 Rubik's cube using a tree similar to a 'mini-max game tree' (listing all possible unique moves, then listing further moves from this and so on), or is the sample space too large, given that most combinations require only 17/18 moves to be solved (and the maximum is proved to be 20)?

$\endgroup$
5
  • 1
    $\begingroup$ The sample space is finite, hence there is no obstacle $\endgroup$ Nov 28, 2014 at 10:38
  • 1
    $\begingroup$ @HagenvonEitzen Yes there are obstacles: Assuming one move consists of a quarter or a 180° turn, there are 18 possible moves. If you want to list all possible move 'paths' up to a length of 20 we will get a tree that has about $1.3 \cdot 10^{25}$ nodes on the last layer. Assuming we need 1 byte (which is way to few) for each state we end up needing more than $10^13$ terabytes of memory. This is where I see a possible obstacle. $\endgroup$
    – flawr
    Nov 28, 2014 at 10:44
  • $\begingroup$ @flawr the question asks if it is possible, not whether it is feasible $\endgroup$
    – AakashM
    Nov 28, 2014 at 10:54
  • $\begingroup$ @AakashM I meant feasible, not just possible. $\endgroup$ Nov 28, 2014 at 11:20
  • $\begingroup$ @flawr You don't need to store the entire tree. As long as the last node is present, it should be enough to calculate the next node. Once a node is not needed anymore, it can be deleted. So memory should not be a problem; I'm asking about the time. $\endgroup$ Nov 28, 2014 at 11:23

0

You must log in to answer this question.

Browse other questions tagged .