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)?

  • 1
    $\begingroup$ The sample space is finite, hence there is no obstacle $\endgroup$ – Hagen von Eitzen Nov 28 '14 at 10:38
  • $\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 '14 at 10:44
  • $\begingroup$ @flawr the question asks if it is possible, not whether it is feasible $\endgroup$ – AakashM Nov 28 '14 at 10:54
  • $\begingroup$ @AakashM I meant feasible, not just possible. $\endgroup$ – ghosts_in_the_code Nov 28 '14 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$ – ghosts_in_the_code Nov 28 '14 at 11:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.