Cubax Folding Game

Question

Your task is to solve a new puzzle called Cubax. This toy is actually a Chinese puzzle whose expected “final” state is a simple cube. During the festivities, Cubax unfolded, because it cannot move when folded.

Cubax is composed of N³ smaller cubes (elements) linked together in a kind of doubly linked chain. The chain has two ends, it doesn't loop.

3 successive elements of Cubax are either:

• always aligned
• always at a right angle (90°)

Thus a simple way of defining Cubax's structure is to provide the successive number of aligned blocks, starting from the first element.

For example, representing S as the starting elements, E as the ending element and X as other elements, the structure defined as 332 could take any of the following 2D shapes:

  XE   EX
  X     X
SXX   SXX   SXX   SXX
              X     X
             EX     XE

Another example: 434 could be represented as:

S E
X X
X X
XXX

Note: Counting the successive the number of aligned elements implies that elements in an angle are counted twice. In the last example 434, there are actually only 4+3-1+4-1=9 elements.

To provide the output solution, use the following rules.

For each series of aligned blocks, one character representing the direction where it has to point to is written:

• U Direction Up (increasing y)
• D Direction Down (decreasing y)
• R Direction Right (increasing x)
• L Direction Left (decreasing x)
• F Direction Front (increasing z)
• B Direction Back (decreasing z)

Considering a 3D representation (x,y,z), we will only be interested in the solutions where the first element is located at (1,1,1) and where the last element is located at (N,N,N)

Note: As a consequence, there will be no valid solution starting by D, L or B.

Example

For the input 3332, the output RDRD corresponds to the following planar shape:

SXX
  X
  XXX
    E

For the same input 3332, the output RDLU corresponds to:

SXX
E X
XXX

Input & Output

Your program has to read the initial shape of Cubax and provide the moves to apply so as to pack it back to a full cube of side length N.

You are given an integer N, the side length of the cube, and a string that contains a string of Blocks -> each character providing the successive number of aligned blocks

You are to output the alphabetically-sorted list of all solutions, one solution per line

Test cases:

# 2*2*2 cube

2
2222222
->
FRBULFR
FUBRDFU
RFLUBRF
RULFDRU
UFDRBUF
URDFLUR

# 3*3*3 cube

3
232333232223222233
->
FRFLUBRFDRBLBRDRUF
FUFDRBUFLUBDBULURF
RFRBULFRDFLBLFDFUR
RURDFLURBULDLUBUFR
UFUBRDFULFDBDFLFRU
URULFDRUBRDLDRBRFU

# 4*4*4 cube

4
3232242323232222222233222223422242322222222242
->
FRBULFDRBUBDBRFUFDFULBUBRDRULDFURDFLULDBLFUBRF
FUBRDFLUBRBLBUFRFLFRDBRBULURDLFRULFDRDLBDFRBUF
RFLUBRDFLULDLFRURDRUBLULFDFUBDRUFDRBUBDLBRULFR
RULFDRBULFLBLURFRBRFDLFLUBUFDBRFUBRDFDBLDRFLUR
UFDRBULFDRDLDFURULURBDRDFLFRBLURFLUBRBLDBURDFU
URDFLUBRDFDBDRUFUBUFLDFDRBRFLBUFRBULFLBDLUFDRU

Others:

• You are allowed to output the moves in a string or list/array

• You are allowed to input the aligned blocks numbers via list/array as well

• You may assume there will always be at least 1 solution to the puzzle

• You are allowed to take in the input as 2 lines or on the same line as a list/array/string representation

Credits to the codingame community for the puzzle!

Scoring

This is code-golf, so shortest code wins!

Answer 1

Python, 269 240 232 bytes

from itertools import*
P=product
def f(n,q):
 for w in P(*['BDFLRU']*len(q)):x=y=z=0;{*P(*[range(n)]*3)}-{(x:=x-E%9*E%4+1,y:=y-E*~E%7%4+1,z:=z+E%-83%E%4-1)for d,p in zip(w,q)for E in[ord(d)%13]*~-p}=={(0,)*3}!=n-1==x==y==z!=print(w)

Attempt This Online! This is too slow for the side length 3 cube.

---

Python, 382 bytes

Slighly optimized for speed, but still too slow to run the last case in a minute.

D=dict(zip('BDFLRU',zip((0,0,0,-1,1,0),(0,-1,0,0,0,1),(-1,0,1,0,0,0))))
def f(n,q):
 S=[('',a:=(0,)*3,{a})]
 for i in q:
  N=[]
  for p,w,c in S:
   for d,(X,Y,Z) in D.items():
    nc=c|c;x,y,z=w
    for _ in' '*~-i:
     x+=X;y+=Y;z+=Z;nc|={a:=(x,y,z)}
     if n<=max(a)or x|y|z<0 or a in c:break
    else:N+=(p+d,(x,y,z),nc),
   S=N
 return[p for p,(x,y,z),_ in S if x==y==z==n-1]

Attempt This Online!

Answer 2

05AB1E, 75 bytes

"BDFLRU"¹gãʒ3Å0Uݨ3ãsÇ13%¹<øε`иε9%y*yy±*7%y83(%y%)4%<`()Xs-DU}}€`KJJ_X>²ªË*

Port of @ovs' (first) Python answer, so make sure to upvote him as well!

No TIO, since it even times out for the 2x2x2 test case. To verify it works as intended, here two separated TIOs, so both parts of the program can be verified independently:

• "BDFLRU"¹gã: Generate all possible move-sets that we're going to filter - try it online.
• 3Å0U²Ý¨3ã³Ç13%¹<øε`иε9%y*yy±*7%y83(%y%)4%<`()Xs-DU}}€`KJJ_X>²ªË*: Verify a move-set (which we take as additional third input here) - try it online.

Explanation:

"BDFLRU"     # Push string "BDFLRU"
 ¹g          # Push the length of the first input-list
   ã         # Cartesian product to create all possible move-sets
ʒ            # Filter this list of strings by:
 3Å0         #  Push [0,0,0]
    U        #  Pop and store it in variable `X`
 ²Ý¨         #  Push a list in the range [0, second input-integer)
    3ã       #  Create all possible triplets of this ranged list
 s           #  Swap so the string is at the top again
  Ç          #  Convert it to a list of codepoint-integers
   13%       #  Modulo-13 each
      ¹      #  Push the first input-list again
       <     #  Decrease each of its values by 1
        ø    #  Create pairs at the same positions of these two lists
 ε           #  Map over each pair [y,z]:
  `и         #   Pop the pair, and create a list of `z` amount of `y`s
    ε        #   Map over each integer `a` in this list:
     9%y*    #    Push y%9*y
     yy±*7%  #    Push y*~y%7 (where `~` is the bitwise-NOT)
     y83(%y% #    Push y%-83%y
     )       #    Wrap all three into a list
      4%<    #    Modulo-4 and then decrement each
         `() #    Negate the last item of the triplet:
      Xs-    #    Subtract them from triplet `X` at the same positions
             #     [a,b,c] → [a-(y%9*y%4-1),b-(y*~y%7%4-1),c+(y%-83%y%4-1)]
         DU  #    Store it as new triplet `X` (without popping)
    }        #   Close the inner map
 }           #  Close the outer map
  €`         #  Flatten it one level down to a list of triplets
    K        #  Remove all those from the earlier list of triplets
     JJ_     #  Check if only [0,0,0] is left as item
 X           #  Push the final triplet `X`
  >          #  Increase each of its values by 1
   ²ª        #  Append the second input-integer
     Ë       #  Check if all four values are the same
        *    #  Check if both checks are truthy
             # (after which the filtered list of strings is output implicitly)

Answer 3

Python3, 2040 1759 bytes

B=input();R=range;X=str.maketrans;j=None;e=sum(int(i)-1for i in B)+1;s=round(e**(1/3));l=(s**3)-1
def q(x,y,z):return x+y*s+z*s*s
class P:
 def __init__(s,x=0,y=0,z=0):s.x,s.y,s.z=x,y,z
 def q(s):return q(s.x,s.y,s.z)
 def u(s,v):return P(s.x+v.x,s.y+v.y,s.z+v.z)
 def v(f):return f.x>-1+f.y>-1+f.z>-1+f.x<s+f.y<s+f.z<s
 def I(s):
  r=[]
  for d in P(z=1),P(z=-1),P(y=1),P(y=-1),P(x=1),P(x=-1):
   n=s.u(d)
   if n.v():r+=n,
  return r
n=[0]*e;K=[{}for _ in R(e)]
def I(t):return s>t>-1
for x in R(s):
 for y in R(s):
  for z in R(s):
   p=P(x,y,z);k=p.q();n[k]=len(p.I())
   if I(x-1):K[P(x-1,y,z).q()]["R"]=k
   if I(x+1):K[P(x+1,y,z).q()]["L"]=k
   if I(y-1):K[P(x,y-1,z).q()]["U"]=k
   if I(y+1):K[P(x,y+1,z).q()]["D"]=k
   if I(z-1):K[P(x,y,z-1).q()]["F"]=k
   if I(z+1):K[P(x,y,z+1).q()]["B"]=k
class A:
 def __init__(s,f=j):
  if f:s.E=f.E[:];s.b=f.b;s.N=f.N[:];s.y=f.y;s.g=f.g;s.f=f.f;s.G=f.G
  else:s.E=[0]*e;s.b=e;s.N=n[:];s.G=j;s.y=0;s.e();s.g=0;s.f=""
 def w(s):return A(f=s)
 def t(s,h):
  for c in h:
   s.f+=c;a=[int(c)-1for c in B][s.g];s.g+=1
   for _ in R(a):
    try:s.y=K[s.y][c];s.e()
    except:return
   return 1
 def l(s):return s.b<1
 def e(s):
  k=s.y
  if s.E[k]:g
  s.E[k]=1
  if s.G==k:s.G=j
  elif s.G!=j:g
  s.N[k]=0;s.b-=1;h=K[k]
  for d in h:
   k=h[d]
   if not s.E[k]:
    n=s.N[k]
    if k!=l+n<3:
     if s.G!=j:g
     s.G=k;s.N[k]=n-1
   if s.b>=1and s.E[l]:g
def p(_,z,N):
 N+=1
 for C in{"L":"BDFU","R":"BDFU","U":"BFLR","D":"BFLR","F":"DLRU","B":"DLRU"}[_]:
  c=z.w()
  if c.t(C):
   if c.l():m.append(c.f)
   else:p(C,c,N)
*m,N=0,;S=A()
S.t("FU")
p("U",S,N);T="FBLRUD"
for s in m[:]:m+=s.translate(X(T,"FBDURL")),
for s in m[:]:m+=s.translate(X(T,"UDLRFB")),;m+=s.translate(X(T,"RLBFUD")),
print("\n".join(sorted(m)))

Try it online!

-18 thx to @Unrelatedstring

-65 thx to @TheFifthMarshal

-1 thx to @AidenChow