Solution 1308504

Submitted on 22 Oct 2017 by Alfonso Nieto-Castanon

This solution is locked. To view this solution, you need to provide a solution of the same size or smaller.

5 Comments

5 Comments

Daniel Turizo on 22 Oct 2017

This problem was so difficult for me to solve, would you mind explaining what search algorithm did you implement? Thanks.

Alfonso Nieto-Castanon on 23 Oct 2017

It is a best-first search using a heuristic based on the sum of manhattan distances to target for each of the 26 tiles; solution 1310071 is slightly commented in case that helps

Alfonso Nieto-Castanon on 23 Oct 2017

@daniel and by the way congrats on finishing all cody5-hard problems, that is quite an accomplishment! (I had it easier, having created a couple of problems in that same group, so mine does not count :)

Daniel Turizo on 23 Oct 2017

I tried a similiar search but it did not end on time, and I don't know why.
PD: You're being too modest! I've been pulling all nighters all the week to finish them all, I'm sure it didn't take you all that time to solve them all.
PD2: I've made a problem (44390) in honour to all the suffering and latter satisfaction these 5th anniversay problems brought to me, you should check it out :)

Michael on 27 Nov 2017

I have tried something similar to this "best-first search" algorithm (if I understand the term correctly), but as I get closer to the final solution, I keep running into situations where all of the available moves move a tile out of its correct position, so my heuristic judges all of them equally, and the algorithm just starts making pseudo-random moves. Are you looking at all possibilities of some small number of moves, and picking one set of moves to move on from?

Test Suite

Test	Status	Code Input and Output
1	Pass	filetext = fileread('sliding3d.m'); assert(isempty(strfind(filetext,'eval'))) assert(isempty(strfind(filetext,'echo')))
2	Pass	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 = sliding3d(p); for i = 1:numel(m) if round(m(i)) == m(i) && m(i) <= numel(p) && m(i) > 0 zero=find(p == 0); [a0 b0 c0] = ind2sub([3 3 3],zero); [a1 b1 c1] = ind2sub([3 3 3],m(i)); if abs(a1 - a0) + abs(b1 - b0) + abs(c1 - c0) == 1 p([m(i) zero]) = p([zero m(i)]); end end end assert(isequal(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]))
3	Pass	p = [1;0;2;4;8;5;7;9;18;10;21;12;11;14;15;16;17;6;13;3;19;20;22;24;25;23;26]; m = sliding3d(p); for i = 1:numel(m) if round(m(i)) == m(i) && m(i) <= numel(p) && m(i) > 0 zero=find(p == 0); [a0 b0 c0] = ind2sub([3 3 3],zero); [a1 b1 c1] = ind2sub([3 3 3],m(i)); if abs(a1 - a0) + abs(b1 - b0) + abs(c1 - c0) == 1 p([m(i) zero]) = p([zero m(i)]); end end end assert(isequal(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]))
4	Pass	p = [1;4;3;19;10;6;7;2;9;20;11;0;16;14;12;5;13;18;22;23;21;17;15;24;25;8;26]; m = sliding3d(p); for i = 1:numel(m) if round(m(i)) == m(i) && m(i) <= numel(p) && m(i) > 0 zero=find(p == 0); [a0 b0 c0] = ind2sub([3 3 3],zero); [a1 b1 c1] = ind2sub([3 3 3],m(i)); if abs(a1 - a0) + abs(b1 - b0) + abs(c1 - c0) == 1 p([m(i) zero]) = p([zero m(i)]); end end end assert(isequal(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]))
5	Pass	p = [1;5;3;10;7;0;13;9;24;22;2;15;16;11;17;12;8;6;19;20;21;26;14;23;4;25;18]; m = sliding3d(p); for i = 1:numel(m) if round(m(i)) == m(i) && m(i) <= numel(p) && m(i) > 0 zero=find(p == 0); [a0 b0 c0] = ind2sub([3 3 3],zero); [a1 b1 c1] = ind2sub([3 3 3],m(i)); if abs(a1 - a0) + abs(b1 - b0) + abs(c1 - c0) == 1 p([m(i) zero]) = p([zero m(i)]); end end end assert(isequal(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]))

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Problem 44376. The sliding puzzle: 3D

Test Suite

Community Treasure Hunt

Players