Algorithm for all the combinations of size-n contiguous chains on a n * n board

Question

I'm trying to write a python program to find every possible combination of placing n pawns on a n * n board so that they form a contiguous chain.

I couldn't figure out a recursive way for it. Each element can have a maximum of 4 neighbors, top and bottom, left and right.
e.g.: neighbors of the A[i, j] are [i - 1, j] [i + 1, j] [i, j - 1] [i, j + 1]

An example for the problem:
consider n = 3 and a board as a 3 by 3 matrix(A[3, 3])
some of the valid combinations are shown below:

Is there a recursive algorithm to solve this problem?

Answer 1

This might not be the most efficient and pythonic way to solve the problem, but seems clear enough to me. Imagine that the cells in your board are labeled from 0 to n - 1, like this:

0 1 2
3 4 5
6 7 8

Here is the code:

from typing import Iterable, Set, Tuple    

def find_neighbors(cur_path: Tuple, n: int) -> Iterable[int]:
    """Find the neighbors of the last cell in a path

    Args:
        cur_path: the current path
        n: board size
    Returns:
        an iterable of neighbors
    """
    cur_position = cur_path[-1]

    top_cell = cur_position - n if cur_position >= n else None
    bottom_cell = cur_position + n if cur_position < n ** 2 - n else None
    left_cell = cur_position - 1 if cur_position % n != 0 else None
    right_cell = cur_position + 1 if (cur_position + 1 ) % n != 0 else None

    return filter(lambda x: x is not None and x not in cur_path, \
                  (top_cell, bottom_cell, left_cell, right_cell))

def find_paths(cur_path: Tuple, n: int) -> Set[Tuple]:
    """find all possible paths that extend a given path so that the final length is n

    Args:
        cur_path: the given path
        n: max length of the final paths

    Returns:
        a set of paths expressed as tuples
    """

    if len(cur_path) == n:
        return {tuple(sorted(cur_path))}

    paths = set()
    for path in [cur_path + (neighbor,) for neighbor in find_neighbors(cur_path, n)]:
        paths = paths.union(find_paths(path, n))

    return paths

def find_combinations(n: int) -> Set[Tuple]:
    """Aggregates paths found from each cell of the board
    
    Args:
        n: board size

    Returns:
        All the paths that can be found in the board of length n    
    """
    combinations = set()
    for row in range(n):
        for col in range(n):
            starting_position = row * n + col
            paths = find_paths((starting_position,), n)
            combinations = combinations.union(paths)
            
    return combinations

def print_board_from_path(path: Tuple, n: int):
    print("-------------------")
    [print('O' if row * n + col in path else '.', end='\n' if (col + 1) % n == 0 else ' ')\
        for row in range(n) for col in range(n)]
    print("-------------------")

if __name__ == '__main__':
    n = 3
    for path in find_combinations(n):
        print_board_from_path(path, n)

The necessary functions are all documented, but let's examine them one by one, considering the board expressed from 0 to n - 1:

find_neighbors

This is the simplest one, very easy to understand with some examples:

find_neighbors(4) -> (1,3,5,7)
find_neighbors(7) -> (4,6,8)
find_neighbors(2) -> (1,5)

I made sure to remove out-of-board cells and those that are already present in the current path.

find_paths

This is the recursive function you are looking for:

• base case: the length of my path is already n, so I just need to return it as a set of tuple, even sorted. Why? It is a set because I do not want repeated paths, 0-1-2 is the same as 2-1-0 and only one should be included (the sorted path helps to avoid this situation). it is a tuple because lists cannot be keys in a set/dictionary, they are mutable objects afterall.
• recursive case: the initial set must be extended with the paths generated from each neighbor of the last cell in the current path.

find_combinations

It makes the find_path algorithm start from each cell in the board and union all the sets generated.

Open issue: could I avoid to start from every cell in the board? For example I do not need to start from cell 4 because the paths generated from all the other cells includes all the paths generated from 4.

Extra

print_board_from_path

It converts the Tuple[int] in a board drawn by O (belongs to the path) and . (does not belong to the path).