Mouse & Cheese Cube

[rocdocmac]

Hopefully this one has not appeared before... Suppose 27 identical cubical chunks of cheese are piled together to form a cubical stack, as illustrated below. What is the maximum number of these cheese chunks through which a mouse of negligible size could munch before exiting the stack, assuming that the mouse always travels along the grid of 27 straight lines that pass through the centers of the chunks parallel or perpendicular to their sides, always makes a 90 degree turn at the center of each chunk it enters, and never enters any chunk more than once?

Edited May 6, 2017 by rocdocmac
Figures didn't show!

[Thalia]

I've got 25 right now. Can't prove that's the most though.

[CaptainEd]

(Sorry I don't know how to make spoiler on iPhone, but it seems Thalia is the winner, so I'm not surprising anyone)

Here's why 25 is max: 

Spoiler

 

Lets label a corner C, Edge Center E, Face Center F, and the hidden Center X.

There are 12 E, 8C, 6F, and 1X.

Because of the required 90 degree turn at each cell, CE can only be followed by EF (or Exit). All possible moves are:

CE : EF

FE : EC or EF

EC: CE

EF : FE  or FX

FX : XF

FE : EC

Notice only F can reach X, so the Sequence of moves must include FXF, if the Center is to be reached at all.

Also notice that once you have moved from C to E, you can only move from E to F.

For each C, you can pass through one F. (In CEFE sequence).  But while there are 8 C, there are only 6 F, so the total sequence can have only 6 C, and the maximum is only 25.

Good news is, there are enough E to join all the C and F, so the sequence could look like

ECEF ECEF ECEF

X

FECE FECE FECE

A path that avoids X would have to have an E between two Fs, which would waste an E, leaving only 24.

 

 

Edited September 13, 2017 by bonanova
Spoilered CaptainEd's answer

[Lemony Syrup]

 

The answer should be 25. My "proof" is a brute force programming solution. I have a psuedocode c++ bruteforce solution. I can give the full version

if requested. It takes a few seconds to brute force all possible paths.  This might count as a proof, depending on if you trust the computer 

to be reliable.

 

Basically what it does is it generates all possible paths, and then prunes as it goes along so the program dosen't take basically forever, or 6^27 moves.

Now a proof will involve some theorems in graph theory, which I don't yet know all that well.

 

 

Assume the XYZ plane
void recursive_dumb_solution( A 3D cube,Position of X, Y, and Z of current spot,direction it went twice ago, direction it went to get here){

if traveled along a direction twice in a row, return to the above function.

   else if( x<0 || x > 2 || y < 0 || y > 2 || z < 0 || z > 2)   AKA if it exited the cube, return.
    else if(cube[x][y][z] == 1)  AKA if visited spot already visited, then return.
    else{
        //mark the current position of the cube as visited.
            cube[x][y][z] = 1; 

   /////Moves in every direction possible.  
            recursive_dumb_solution(cube,  x+1,  y,  z, length+1,'x',prev_dir);
            recursive_dumb_solution(cube,  x-1,  y,  z, length+1,'x',prev_dir);
            recursive_dumb_solution(cube,  x,  y+1,  z, length+1,'y',prev_dir);
            recursive_dumb_solution(cube,  x,  y-1,  z, length+1,'y',prev_dir);
            recursive_dumb_solution(cube,  x,  y,  z+1, length+1,'z',prev_dir);
            recursive_dumb_solution(cube,  x,  y,  z-1, length+1,'z',prev_dir);

             cube[x][y][z] = 0;
            return;
    }
}

Edited September 9, 2018 by Lemony Syrup
Duplicate Post

[bonanova]

Nice puzzle. I have the feeling that

Spoiler

it has a relation to the Soma cube puzzle.

Except those pieces probably don't have enough right-angles to be optimal here.

 

[hutchman]

I think starting from any point other than a corner would be non optimal.

Spoiler

So doing this the mouse would have to leave a full face uneaten (9 pieces). So my answer is 18!  Right or Wrong?

 

[rocdocmac]

Spoiler

Nope - more than 18!

 

[rocdocmac]

Have another go!

[Donald Cartmill]

I get 24 cubes ; 7 in the front face ;  9 in the middle  ; and 8 in the rear face

[hutchman]

On 5/10/2017 at 6:25 AM, Thalia said:

 

  Reveal hidden contents

I've got 25 right now. Can't prove that's the most though.

wow Thalia that's more than I got! I'm giving up now. can you tell your details?

 

[Thalia]

1 hour ago, hutchman said:

wow Thalia that's more than I got! I'm giving up now. can you tell your details?

Well, I seem to have forgotten the detail about having to exit the cheese so there goes that!

2 hours ago, hutchman said:

wow Thalia that's more than I got! I'm giving up now. can you tell your details?

Revised attempt. Don't know how to spoiler a photo but since it's wrong anyway, here it is. 

[rocdocmac]

Spoiler

You'll get 25 if you start with the middle of an edge. Remember, however, there are 8 corners plus 6 faces (total 14), but 12 corners and a single center (total 13). Thus, to obtain the maximum one has to start at a corner or middle of a face and end with a corner or middle of a face.

[CaptainEd]

My analysis was incomplete. If you skip the Center X, then a string of alternating C and F (with E between) is constrained by the number of E. With 12 E, at most 13 (C,F) can be interleaved with them. And, because there are only 6 F, that means the upper limit on a path would use 7 Cs and 6Fs. So as Rocdocmac says, if it's possible without touching X, it must start and end with C: CEFECEFECEFECEFECEFECEFEC. Either way, with or without the X cell, 25 appears to be the upper bound, and Thalia found one.

[Thalia]

...I interpreted "have another go" as meaning more was possible... Guess I should have tried harder to spoiler.

For spoilers on phone, use (spoiler)your text here(/spoiler) but use [ ] instead of ( ).

...I interpreted "have another go" as meaning more was possible... Guess I should have tried harder to spoiler.

For spoilers on phone, use (spoiler)your text here(/spoiler) but use [ ] instead of ( ).

[rocdocmac]

Spoiler

I've done this exercise before (round about 2005), working through each and every possible move, which naturally took a long time. I saw my solution that I printed out at that time about three months ago, but now I can't find it anywhere! I'm almost certain that the mouse's path went through all 27 cubes, but so far I couldn't replicate that! Till I find that printed solution again, we'll have to accept 25 as the maximum and Thalia was indeed the winner. So, apology for the "have another go"!. Incidentally, if the center is omitted, you still get 25 of the 26 remaining cubes.