This is an extension of problem 42842. In this case, the puzzle is three-dimensional and is of size 3x3x3. Of the 27 positions in the puzzle, 26 are occupied by cubes numbered 1 thru 26, while the remaining position is empty. You can slide an adjacent cube into the empty position, similarly to sliding an adjacent tile into the empty position in the 15 puzzle.
In this case, for simplicity, the puzzle is represented by a vectorized form of the puzzle, such that the 3D form of the puzzle can be obtained by reshape(p,[3 3 3]). Therefore, a solved cube shall look like this:
p = [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15;16;17;18;19;20;21;22;23;24;25;26;0]
Given the initial state vector, p, return a vector, m, comprising a sequence of integers, representing the linear indices of the cubes you wish to slide, in turn, into the empty position, in order to solve the puzzle.
As before, the solution does not have to be efficient. It must simply result in a correctly solved puzzle. Illegal moves, such as trying to slide a tile that is not adjacent to the open slot, will be ignored.
Example:
p = [0;2;3;1;5;6;4;7;9;10;11;12;13;17;14;16;8;18;19;20;21;22;23;15;25;26;24]
m = [4 7 8 17 14 15 24 27]
Solution Stats
Problem Comments
9 Comments
Solution Comments
Show comments
Loading...
Problem Recent Solvers52
Suggested Problems
-
Determine whether a vector is monotonically increasing
22840 Solvers
-
Rotate and display numbered tile
377 Solvers
-
Create a square matrix of multiples
495 Solvers
-
Multiples of a Number in a Given Range
939 Solvers
-
402 Solvers
More from this Author45
Problem Tags
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
there is a bug in the evaluation function, I believe "abs(a1 + b1 + c1 - a0 - b0 - c0) == 1" should be changed to "abs(a1-a0) + abs(b1-b0) + abs(c1-c0) == 1". In any way, this was a very cool problem, unless I am misremembering this would be the very first one that forced me to implement some version of A* in Cody :)
Alfonso, it is an honor and a pleasure to have read your comment. I'm glad you enjoyed the problem. Thank you for spotting the bug. I will update accordingly.
Alfonso, I've fixed the bug. As a result, I've actually located a tiny typo, one single character in my own solution that was, in fact, the difference between a correct and an incorrect solution based on your correction. Fixed that too, of course. Thanks again!
It takes 9 seconds to solve the four inputs on my laptop, but the system rejected my code with the error of long run time. What's the acceptable time for the four inputs?
This one kept my busy, and I think my solution is a bit of a tour de force. It is recipe based, rather than optimal, but there are just too many corner cases to program around. I should have made better use of invariant sets, I guess.
Difficult problem
Good problem. Tip: use the L1-norm or manhattan distance using the 3 indexes as a cost function.
I am actually giving up :(
tried a lot......
Too difficult