[Community Puzzle] Cubax Folding

Puzzles
1

Hi guys,

I have problems limiting the search space for this puzzle: https://www.codingame.com/training/expert/cubax-folding

My code runs forever for the 4x4x4 testcase. How can optimize this?

Best,
fafl

2

Hello

Was wondering if you made any progress since then and possibly could share some insights?

My naive brute force recursion approach is suffering from the same exponential slowness and I’d like to make it less dumb. However, I don’t know what concepts I should be studying more closely.

3

The search tree is huge, but it can be pruned a lot.

List all the prunes you can think of. In plain English: if you’ve got a partial folding, how can you know in advance that it’s never going to end up in a solution, without completing it to the end?

Sort them by ease of implementation. Implement them one by one, until performance is enough.

For an example prune that doesn’t spoil the problem, this one’s not in my final code so it’s obviously not needed (though it could help if you’ve got a different set) but could give you an idea of what to try. It’s common sense, but to succeed a complete fold you need to have long enough of Cubax to reach the end. At any point in the search, if the distance from where you are to the goal exceeds the remaining length, there’s no point in even branching to find a clear path: there won’t be one and you’d better backtrack immediately.

1 Like
4

Just the kind of pointers I was hoping for to get some new ideas off the ground.
Thank you very much JBM! :+1:

5

Happy to help. :blush:

6

I don’t get Cubax Folding. None of the examples explain the 3D aspect of the puzzle. Besides, the example 3332 doesn’t add up to a cubic number. Can we get some better examples, maybe one in 3D.

7

The real puzzle is also known as Snake Cube.

8

Hi

May I missed one constraint but on the first IDE test, I obtain this list of possibilities:

FRBUFLB

FRBULFR

FRULBRD

FUBRDFU

FUBRFDB

FURDBUL

RFLUBRF

RFLURBL

RFUBLFD

RUFDLUB

RULFDRU

RULFRDL

UFDRBUF

UFDRUBD

UFRBDFL

URDFLUR

URDFULD

URFLDRB

It includes the solutions but also others which for my understanding seems also correct. Is there anything I missed here ?

Thanks !

9

Some solutions don’t satisfy this requirement in the statement:

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)

10

Ha I did spot the start point but not the end point…

Thank you