How to visit all points in a 2D grid?

Question

I am trying to have 2 points visit all points in a 3 x 3 grid. The method of visiting the points is:

• I have points P1 and P2, starting from (0, 0).
• P1 moves from (0, 0) to (0, 1), (1, 0) until (3, 3).
• When P1 reached the end of grid ((3, 3)), P2 should update from (0, 0) to (0, 1), then
• P1 starts from position of P2 until end of grid.
• This goes on until P2 reaches (3, 3).

So an exhaustive/brute-force search with a combination of 2 points. I tried:

def traversal_methods(num_particles, grid_size):
    particles = [(0, 0) for _ in range(num_particles)]

    while(particles[1] != (grid_size - 1 , grid_size - 1 )):

        for k in range(0, grid_size):
            for l in range(0, grid_size):
                particles[1] = (k, l)
                particles[0] = (0, 0)

                while(particles[0] != (grid_size-1, grid_size-1)):
                    for i in range(k, grid_size):
                        for j in range(0, grid_size):
                            particles[0] = (i, j)

I am not getting intended result. I also want to extend this to n-points. Can anyone suggest some method to do this?

Answer 1

I also want to extend this to n-points. Can anyone suggest some method to do this?

Using list comprehension and nested loops:

def grid_create(size_x, size_y):
    return [[(x, y) for x in range(size_x)] for y in range(size_y)]


grid = grid_create(3, 3)

Result (tuples as (x, y) in list of lists as [y][x]):

[(0, 0), (1, 0), (2, 0)],
[(0, 1), (1, 1), (2, 1)],
[(0, 2), (1, 2), (2, 2)]

Traversal (P2 from P1):

def grid_traverse(grid):
    c1, c2 = 0, 0

    for y1 in range(len(grid)):
        for x1 in range(len(grid[y1])):
            c1 += 1
            c2  = 0
            print(f'P1 {grid[y1][x1]}')

            for y2 in range(len(grid)):
                for x2 in range(len(grid[y2])):
                    c2 += 1
                    if (c2 < c1): continue
                    print(f'\tP2 {grid[y2][x2]}')


grid = grid_create(3, 3)
grid_traverse(grid)

Result as (x, y):

P1 (0, 0)
    P2 (0, 0)
    P2 (1, 0)
    P2 (2, 0)
    P2 (0, 1)
    P2 (1, 1)
    P2 (2, 1)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (1, 0)
    P2 (1, 0)
    P2 (2, 0)
    P2 (0, 1)
    P2 (1, 1)
    P2 (2, 1)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (2, 0)
    P2 (2, 0)
    P2 (0, 1)
    P2 (1, 1)
    P2 (2, 1)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (0, 1)
    P2 (0, 1)
    P2 (1, 1)
    P2 (2, 1)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (1, 1)
    P2 (1, 1)
    P2 (2, 1)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (2, 1)
    P2 (2, 1)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (0, 2)
    P2 (0, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (1, 2)
    P2 (1, 2)
    P2 (2, 2)
P1 (2, 2)
    P2 (2, 2)

Result illustrated:

Example without grid:

def grid_traverse(size_x, size_y):
    c1, c2 = 0, 0

    for y1 in range(size_y):
        for x1 in range(size_x):
            c1 += 1
            c2  = 0
            print(f'P1 ({x1}, {y1})')

            for y2 in range(size_y):
                for x2 in range(size_x):
                    c2 += 1
                    if (c2 < c1): continue
                    print(f'\tP2 ({x2}, {y2})')


grid_traverse(3, 3)