n * n 板上所有大小为 n 的连续链的组合的算法
Algorithm for all the combinations of size-n contiguous chains on a n * n board
我正在尝试编写一个 python 程序来找到在 n * n 棋盘上放置 n 个棋子的所有可能组合，以便它们形成一个连续的链。
我想不出一个递归的方法。每个元素最多可以有 4 个邻居，顶部和底部，左侧和右侧。
例如：A[i, j] 的邻居是 [i - 1, j] [i + 1, j] [i, j - 1] [i, j + 1]
问题示例：
将 n = 3 和一个板视为 3 x 3 矩阵(A[3, 3])
一些有效的组合如下所示：
有没有递归算法可以解决这个问题？
这可能不是解决问题的最有效的 pythonic 方法，但对我来说似乎很清楚。想象一下，您板上的单元格标记为从 0 到 n - 1，如下所示：
0 1 2
3 4 5
6 7 8
代码如下：
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)
必要的功能都记录在案，但让我们一一检查，考虑从 0 到 n - 1 表示的板：
find_neighbors
这是最简单的，结合一些例子很容易理解：
find_neighbors(4) -> (1,3,5,7)
find_neighbors(7) -> (4,6,8)
find_neighbors(2) -> (1,5)
我确保删除 out-of-board 个单元格以及当前路径中已经存在的单元格。
find_paths
这是您要查找的递归函数：
- 基本情况：我的路径长度已经是
n，所以我只需要 return 它作为一个 set 元组，甚至排序。为什么？这是一组，因为我不想重复路径，0-1-2 与 2-1-0 相同，应该只包含一个（sorted 路径有助于避免这种情况）。它是一个元组，因为列表不能是 set/dictionary 中的键，毕竟它们是可变对象。
- 递归情况：必须使用从当前路径中最后一个单元格的每个邻居生成的路径扩展初始集。
find_combinations
它使得 find_path 算法从棋盘中的每个单元格开始，并 union 生成所有集合。
未决问题：我可以避免从板上的每个单元格开始吗？例如，我不需要从单元格 4 开始，因为从所有其他单元格生成的路径包括从 4.
生成的所有路径
额外
print_board_from_path
将O（属于路径）和.（不属于路径）绘制的棋盘中的Tuple[int]进行转换。
我正在尝试编写一个 python 程序来找到在 n * n 棋盘上放置 n 个棋子的所有可能组合，以便它们形成一个连续的链。
我想不出一个递归的方法。每个元素最多可以有 4 个邻居，顶部和底部，左侧和右侧。
例如：A[i, j] 的邻居是 [i - 1, j] [i + 1, j] [i, j - 1] [i, j + 1]
问题示例：
将 n = 3 和一个板视为 3 x 3 矩阵(A[3, 3])
一些有效的组合如下所示：
有没有递归算法可以解决这个问题？
这可能不是解决问题的最有效的 pythonic 方法，但对我来说似乎很清楚。想象一下，您板上的单元格标记为从 0 到 n - 1，如下所示：
0 1 2
3 4 5
6 7 8
代码如下：
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)
必要的功能都记录在案，但让我们一一检查，考虑从 0 到 n - 1 表示的板：
find_neighbors
这是最简单的，结合一些例子很容易理解：
find_neighbors(4) -> (1,3,5,7)
find_neighbors(7) -> (4,6,8)
find_neighbors(2) -> (1,5)
我确保删除 out-of-board 个单元格以及当前路径中已经存在的单元格。
find_paths
这是您要查找的递归函数：
- 基本情况：我的路径长度已经是
n，所以我只需要 return 它作为一个set元组，甚至排序。为什么？这是一组，因为我不想重复路径，0-1-2与2-1-0相同，应该只包含一个（sorted路径有助于避免这种情况）。它是一个元组，因为列表不能是 set/dictionary 中的键，毕竟它们是可变对象。 - 递归情况：必须使用从当前路径中最后一个单元格的每个邻居生成的路径扩展初始集。
find_combinations
它使得 find_path 算法从棋盘中的每个单元格开始，并 union 生成所有集合。
未决问题：我可以避免从板上的每个单元格开始吗？例如，我不需要从单元格 4 开始，因为从所有其他单元格生成的路径包括从 4.
生成的所有路径额外
print_board_from_path
将O（属于路径）和.（不属于路径）绘制的棋盘中的Tuple[int]进行转换。