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?

CodePudding user response：

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).