Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Wed Apr 16, 2014 5:55 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 6 posts ] 
Author Message
 Post subject: A puzzle about a puzzle
PostPosted: Tue Mar 05, 2013 1:35 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Numbrix is a pencil-and-paper puzzle played on a 9x9 grid. You have to place the numbers from 1 to 81 in the squares of the grid so they form a path, moving orthogonally (never diagonally) between each step (so 1 is next to 2, which is next to 3, and so on).

How many valid paths are there?


Top
 Profile  
 
 Post subject: Re: A puzzle about a puzzle
PostPosted: Tue Mar 05, 2013 2:09 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
This seems related to Hilbert Curves.

You asked for unique paths so I assume the start and stop of the path matters and I also assume rotation and mirrors and inversions are all "different paths".

In that case, assuming there is only one curve, then there are 81 ways to start that curve, 2 ways forwards and backwards, 4 rotations, and mirroring (which I think is the same thing as inverting the direction and a rotation).

So that'd be 81 * 2 * 4 = 648 different solutions from a single Hilbert Curve. I think one could argue these are all different views of the same solution.

Perhaps there are more space filling curves beyond just the obvious one?

Edit: I suppose zig-zagging like text on a page and spirals are also curves that would work. There must be a lot more. For example you could zig-zag for a bit and then go into a spiral for the remainder.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A puzzle about a puzzle
PostPosted: Tue Mar 05, 2013 4:06 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
bmenrigh wrote:
In that case, assuming there is only one curve, then there are 81 ways to start that curve...
You are assuming a closed path. I don't see anything in the problem statement that requires 1 be next to 81. And that's not possible as the odds form one checker pattern and the evens another. You can never have 2 odds next to each other.

Either that or I'm misunderstanding something in your statement,
Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: A puzzle about a puzzle
PostPosted: Tue Mar 05, 2013 4:50 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
bmenrigh wrote:
In that case, assuming there is only one curve, then there are 81 ways to start that curve...
You are assuming a closed path. I don't see anything in the problem statement that requires 1 be next to 81. And that's not possible as the odds form one checker pattern and the evens another. You can never have 2 odds next to each other.

Either that or I'm misunderstanding something in your statement,
Carl


You're right I was thinking of a closed curve where even though the two ends of the Hilbert Curve are actually adjacent. You wouldn't be able to start the 1 .. 81 at any point because there would be a discontinuity when you reach the end of the curve. I spend too much time thinking in modular arithmetic :-/

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A puzzle about a puzzle
PostPosted: Tue Mar 05, 2013 5:18 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Sorry for not being clear! No, it isn't and can't be a closed loop as mentioned.

I calculated an upper bound of a little more than 600 duodecillion (6 x 10^41) based on the following logic: there are 144 ways to connect two adjacent squares, and 80 will be used in any given path. So, 144 choose 80 gives this number. But of course not all of these selections make valid paths.


Top
 Profile  
 
 Post subject: Re: A puzzle about a puzzle
PostPosted: Tue Mar 05, 2013 5:38 pm 
Offline
User avatar

Joined: Tue Aug 11, 2009 2:44 pm
I could swear I heard Don Knuth give a talk once where he answered this question (for larger squares), but I can't find a paper with the result. Maybe it's just very similar so some other problems he's tackled.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 6 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group