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

TwistyPuzzles.com Forum
 It is currently Wed Jul 23, 2014 7:14 am

 All times are UTC - 5 hours

 Page 1 of 1 [ 6 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: A puzzle about a puzzlePosted: Tue Mar 05, 2013 1:35 pm

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

 Post subject: Re: A puzzle about a puzzlePosted: Tue Mar 05, 2013 2:09 pm

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

 Post subject: Re: A puzzle about a puzzlePosted: Tue Mar 05, 2013 4:06 pm

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

_________________
-

Top

 Post subject: Re: A puzzle about a puzzlePosted: Tue Mar 05, 2013 4:50 pm

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

 Post subject: Re: A puzzle about a puzzlePosted: Tue Mar 05, 2013 5:18 pm

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

 Post subject: Re: A puzzle about a puzzlePosted: Tue Mar 05, 2013 5:38 pm

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

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 6 posts ]

 All times are UTC - 5 hours

#### Who is online

Users browsing this forum: No registered users and 2 guests

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

Search for:
 Jump to:  Select a forum ------------------ Announcements General Puzzle Topics New Puzzles Puzzle Building and Modding Puzzle Collecting Solving Puzzles Marketplace Non-Twisty Puzzles Site Comments, Suggestions & Questions Content Moderators Off Topic