62 59 54 bytes
Input is a complex number.
(Don't) Try it online!
The program is quite slow, and times out online for all of the test cases, but works offline. Here's an example with two test cases:
Let the four directions in which the cube can be rolled be numbered as
1: N, 2: W, 3: S, 4: E.
Let the six positions of the cube faces be numbered as
0: top, 1: north, 2: west, 3: south, 4: east, 5, bottom
The face which is initially at the top will be called "reference face".
The essential part of the code is a matrix M that indicates, for any direction of roll (matrix row) and given the current position of the reference face (matrix column), what is the new position of the reference face:
1 2 3 4 5 0
1| 5 2 0 4 3 1
2| 1 5 3 0 4 2
3| 0 2 5 4 1 3
4| 1 0 3 5 2 4
For instance, M(4,2) = 0 indicates that if the cube is rolled east (4) when the reference face is on the west side of the cube (2), the reference face moves to the top (0).
This matrix is stored in the program in compressed form. It has been represented with column index 0 at the end because MATL's indexing is 1-based and modular, so 0 represents the last column.
The code generates all paths, with increasing length, until a solution is found. Each path is a sequence of numbers 1, 2, 3, 4, indicating roll directions. A path is a solution if it arrives at the destination (*) with the reference face at the top (**). To see how these conditions are checked, consider an example path 1,4,1,3,4 (NENSE).
- (*) The first condition is checked using complex-number operations. The imaginary unit j raised to each number in the path gives a direction in the complex plane. The sum of all the complex numbers is the final location for the path. In this example, j^1 + j^4 + j^1 + j^3 + j^4 = j+1+j−j+1 = 2+j. This is compared with the input.
- (**) The second condition is checked by repeatedly indexing into the above matrix. The initial position of the reference face is 0 (top). Since the first step of the path is 1 (N), we read M(1,0) = 1. So the reference face is now in the north side (1) of the cube. The next step of the path is 4 (E), and M(4,1) = 1. Next, M(1,1) = 5; and so on. The final result should be 0 for the path to be valid.
To generate all paths we increase a counter starting at 1, convert to base 4 with digits 1,2,3,4 instead of 0,1,2,3, and remove the first digit. If the first digit were not removed, paths starting with 1 (which is the zero digit in this numbering system) would not be generated.
` % Do...while
J % Push j (imaginary unit)
@ % Push loop counter, starting at 1. Each value generates a path
4_YA % Convert to base 4 using 1,2,3,4 as digits
4L) % Remove first digit. This is the path
XH % Copy into clipboard H
^ % Element-wise power
s % Sum
G= % Does it equal the input? This gives true (1) or false (0) (*)
0 % Push 0. This is the initial position of the reference face
H % Push path again
" % For each step in the path (with value 1, 2, 3 or 4)
'(-9@%3Vuao' % Push this string
F6Za % Convert base from ASCII chars except single quote to base 6
4e % Reshape as a 4-column matrix. This is matrix M
@ % Push current step
b % Bubble up: move current position of reference face to top of stack
3$) % Index into the matrix. This updates the position of reference face
] % End. Top of stack contains the final position of reference face (**)
>~ % Less than or equal? This gives false if and only if (*) is 1 and
% (**) is 0, which means a solution has been found; and in that case
% the loop will be exited
} % Finally: execute on loop exit
'NWSE' % Push this string
H % Push current path, which is the solution
) % Index. This gives a string with 1 replaced by 'N' etc
% Implicit end. The loop exits if the top of the stack is falsy
% Implicit display