城市网格指定数量建筑布局的回溯法求解及代码问题排查

我有两个输入：

• 一个N×M的城市网格，其中空格代表空地，"X"代表已占用地块，格式为List[List[str]]，示例如下：

X XXX 
 X  X
XXXX 
 XX X

• 一个整数，表示需要放置的建筑数量。

要求返回所有可能的建筑布局列表，格式为List[List[List[str]]]，例如当需要放置3栋建筑时，一种可能结果为：

XBXXX
BXB X
XXXX 
 XX X

另一种结果为：

X XXX 
 X  X
XXXXB
BXXBX

若所需建筑数量大于空地总数，需返回相应错误信息。

我尝试用回溯法解决，但代码存在问题：当find_permutations在required_building_count为0返回时，current_city_map无法回溯到上一层状态，仍保留着已放置的全部建筑。

import copy
from typing import List

def can_place_building(xPos, yPos, city_map, building_code):
    return city_map[yPos][xPos] == ' '


def find_permutations(initial_city_map, current_city_map, building_code, required_building_count, possible_combinations):
    if required_building_count == 0:
        possible_combinations.append(current_city_map)
        return
    for x in range(len(current_city_map[0])):
        for y in range(len(current_city_map)):
            if can_place_building(x, y, current_city_map, building_code):
                current_city_map[y][x] = building_code
                find_permutations(initial_city_map, current_city_map, building_code, required_building_count - 1, possible_combinations)


def find_possible_combinations(initial_city_map, required_building_count: int) -> List:
    building_code = 'B'
    possible_combinations = []
    current_city_map = copy.deepcopy(initial_city_map)
    find_permutations(initial_city_map, current_city_map, building_code, required_building_count, possible_combinations)
    return possible_combinations

核心问题 #

你的回溯逻辑缺少状态回退步骤：修改current_city_map后，递归返回时没有把这块地改回空地，导致后续循环继续使用被修改后的地图，无法生成正确的所有组合。另外还有两处细节问题：

1. 重复遍历所有格子会生成重复布局（比如先放A位置再放B位置，和先放B位置再放A位置会被当成不同结果，但实际是同一个布局）；
2. 没有提前检查所需建筑数量是否超过空地总数，不符合需求。

修复后的代码 #

import copy
from typing import List

def can_place_building(xPos, yPos, city_map):
    return city_map[yPos][xPos] == ' '

def count_empty_spaces(city_map):
    return sum(row.count(' ') for row in city_map)

def find_permutations(current_city_map, building_code, required_building_count, start_x, start_y, possible_combinations):
    if required_building_count == 0:
        # 保存深拷贝，避免后续修改影响已记录的结果
        possible_combinations.append(copy.deepcopy(current_city_map))
        return
    
    rows = len(current_city_map)
    cols = len(current_city_map[0]) if rows > 0 else 0
    
    # 从当前位置的下一个格子开始遍历，避免生成重复布局
    for y in range(start_y, rows):
        start_col = start_x if y == start_y else 0
        for x in range(start_col, cols):
            if can_place_building(x, y, current_city_map):
                # 放置建筑
                current_city_map[y][x] = building_code
                # 计算下一个遍历的起点
                next_x = x + 1
                next_y = y
                if next_x >= cols:
                    next_x = 0
                    next_y = y + 1
                # 递归寻找下一个建筑位置
                find_permutations(current_city_map, building_code, required_building_count - 1, next_x, next_y, possible_combinations)
                # 回溯：撤销放置，恢复空地状态
                current_city_map[y][x] = ' '

def find_possible_combinations(initial_city_map, required_building_count: int) -> List:
    building_code = 'B'
    possible_combinations = []
    
    # 提前检查数量合法性
    empty_count = count_empty_spaces(initial_city_map)
    if required_building_count > empty_count:
        return ["错误：所需建筑数量超过空地总数"]
    if required_building_count == 0:
        return [copy.deepcopy(initial_city_map)]
    
    current_city_map = copy.deepcopy(initial_city_map)
    find_permutations(current_city_map, building_code, required_building_count, 0, 0, possible_combinations)
    return possible_combinations

关键修复点 #

1. 添加回溯回退：递归调用后将修改的格子重新设为' '，让地图回到修改前的状态，确保后续循环能正确处理其他位置；
2. 避免重复布局：通过start_x和start_y控制遍历起点，每次递归只从当前位置的下一个格子开始，不会生成顺序不同但位置集合相同的重复结果；
3. 结果深拷贝：保存结果时存入当前地图的深拷贝，而非原引用，避免后续修改破坏已记录的布局；
4. 合法性检查：提前计算空地总数，若所需建筑数超出则直接返回错误信息，满足需求。

内容的提问来源于stack exchange，提问作者Baeby