How many combinations of this pattern are there?

izoneiz · 18 May 2012 at 18:06

Imagine a square 2D grid of nodes of dimension n by n nodes.

Now imagine you can start at any node, and travel in any direction (up, down, left, right, or in any of the diagonal directions). Moving to an adjacent node constitutes '1 length'.

The rules are:
a. You can move diagonally.
b. You cannot backtrack
c. For a particular journey, you cannot travel over the same path, but you can cross it if necessary.
d. You can start and end the journey at any node, providing you have travelled the required journey length set by the game.

The journey length is called 't'.

How many possible different patterns are there as a function of t and n?

I have attached the image to explain.

izoneiz · 18 May 2012 at 18:19

No. It's something I've been thinking about, and I like to think that I can solve this type of thing but I really can't - I haven't been successful. It's not a game or for any sort of work - just a challenge I set myself

izoneiz · 18 May 2012 at 18:40

Josh P said:
Are you allowed to revisit nodes (as opposed to backtracking) ?

Yes, you are permitted to revisit nodes, but as long as you do not re-travel along a path you have already taken for that journey (in either direction).

izoneiz · 18 May 2012 at 19:30

No. t does not have to equal 4. And l does not have to equal 3 or whatever. They are just variables in the game.

I think it would be something along the lines of:

combinations = f(t,n)_non_edge_start + f(t,n)_edge_start

Where edge_start signifies journeys commencing from the edges, and non_edge_start commences journeys commencing away from the edge.

izoneiz · 18 May 2012 at 20:09

Amleto said:
first thing to recognise is that a corner is different to an edge

and non edge starts can potentially visit edge/corner and non-edge/corner nodes multiple times non-consecutively

Yes, very true. So you can see why this problem is really quite tough to solve. It's not impossible, obviously. Just difficult. There IS a solution.

izoneiz · 19 May 2012 at 12:48

piggeh said:
is the grid always square?

Yes, the grid is always square.

Could one of you bright buttons have a stab at how many combinations we're talking about for say: n = 4, t = 4? An educated guess. I want to know if we're talking hundreds or tens of thousands or perhaps more?

I'm going to email my faculty at uni and have the PhDs look at it.