How many combinations of this pattern are there?

izoneiz

izoneiz

izoneiz

Associate
Joined
18 Oct 2002
Posts
2,333
Location
London, WC1
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.

MjJ7k.png
 
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
 
estebanrey said:
Is 't' always 4?
Click to expand...

I think that's just an example isn't it?

My best guess (I'm too lazy to actually think it through), would be t=3n!-4n because you have 3 choices of direction at each node except the ones at the edges, and you reduce the nodes you can hit by 1 each time. Or something. It probably has a huge hole in the logic somewhere, but that's 5 mins of effort I won't get back.
 
I think you should consider a few different zones.

e.g. zones where edges cant 'interfere'
zones where only edges (no corners) can interfere
zones where edges and corners interfere
...
 
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.
 
i've worked it out for a path of length one. still thinking of how to tackle a journey of higher lengths though

P = number of paths possible
n = length of edge of square (number of points in edge of square)
t = path length = 1

P = (number of centre points * 8) + (number of edge points * 5) + (number of corner points * 3)
so

for N<=1, P = 0

for N>1,
P = ((n-2)^2)*8 + 4(n-2)*5 + 4*3

hopefully this will help someone work out longer journeys
 
izoneiz said:
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.
Click to expand...

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 :eek:
 
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 :eek:
Click to expand...

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.
 
You must log in or register to reply here.
Back
Top Bottom