#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2013
    Posts
    1
    Rep Power
    0

    Paths around a grid


    Hi
    Can someone give me some hints about how to do the following
    I have a 3 by 3 grid and want a list of all the possible routes, of at least 3 squares, around the grid starting anywhere and moving to an adjacent square (not visited before) including diagonals.
    Thanks a lot
    John
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,996
    Rep Power
    481
    Code:
    Name your nodes
    
    ABC
    DEF
    GHI
    
    Represent the paths.  Connectivity matrix is a standard.
            to
    
         A B C D E F G H I 
       A 0 1 0 1 1 0 0 0 0  A connects to B, D, and E
    f  B 1 0 1 1 1 1 0 0 0
    r  C 0 1 0 0 1 1 0 0 0
    o  D 1 1 0 0 1 0 1 1 0
    m  E 1 1 1 1 0 1 1 1 1
       F 0 1 1 0 1 0 0 1 1
       G 0 0 0 1 1 0 0 1 1
       H 0 0 0 1 1 1 1 0 1
       I 0 0 0 0 1 1 0 1 0
    What are the paths starting from A ?

    Put A into your list of paths.
    A connects to BDE, which are not already in the path. Put BDE into your frontier.
    for each node in the frontier
    extend the paths by appending the node to the path that got you here.
    repeat once

    So I finished the code, labeling the nodes as 0 through 8, and got, for starting at 0, the paths
    Code:
    pprint.pprint(paths(0,CONNECTIVITY))
    [[[0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 1, 5]],
     [[0, 3, 1], [0, 3, 4], [0, 3, 6], [0, 3, 7]],
     [[0, 4, 1], [0, 4, 2], [0, 4, 3], [0, 4, 5], [0, 4, 6], [0, 4, 7], [0, 4, 8]]]
    which looks right to me.
    Last edited by b49P23TIvg; March 8th, 2013 at 01:17 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo