约束编程图着色问题：C++回溯法代码调试求助

你的区域着色回溯代码存在几个关键逻辑错误，导致无法正确找到解。下面我会逐个指出问题，并提供修复后的完整代码。

核心问题排查 #

1. 错误使用capacity()判断完成状态 #

你用zSolVec.capacity() == 5来判断是否所有区域都已着色，但capacity()返回的是容器预分配的内存空间大小，不是实际存储的元素数量。正确的判断应该用size()，它返回容器当前的元素个数：

// 错误
if(zSolVec.capacity() == 5) 
// 正确
if(zSolVec.size() == 5)

同样，判断zSolVec是否为空也应该用size() == 0，而不是capacity() == 0。

2. 相邻区域判断逻辑完全错误 #

你的代码中，判断两个区域是否相邻的逻辑是检查它们的sides列表有没有重叠元素，这完全不符合需求。实际上，sides存储的是当前区域相邻的区域编号（比如z1的sides是2、3、4、5，代表它和z2、z3、z4、z5相邻）。正确的判断应该是：

• 先确定当前区域的编号
• 遍历所有已着色的区域，检查当前区域是否和该区域相邻，并且颜色是否冲突

你之前的逻辑只检查了zSolVec.back()（最后一个着色的区域）和当前区域的关系，而且判断条件错误，会漏掉和其他已着色区域的冲突。

3. 递归分支终止逻辑错误 #

当发现当前颜色和相邻区域冲突时，你直接return;，这会终止整个循环的后续颜色尝试。正确的做法是跳过当前颜色，继续尝试下一个颜色（用continue;而不是return;）。

4. 缺少区域编号的存储 #

你的Zones类没有存储区域的编号，只能通过name字符串提取，这既麻烦又容易出错。建议在Zones类中添加一个id成员变量，直接存储区域编号（比如z1的id是1）。

5. 参数传值导致的效率问题 #

mapColouring函数中的zSolVec和zVec是传值传递，每次递归都会复制整个容器，虽然不影响正确性，但效率很低。可以改为传引用，并在需要修改时创建副本，或者使用const引用配合局部修改。

修复后的完整代码 #

#include <iostream>
#include <vector>
#include <string>

enum Colours{red, green, blue, yellow};
static int count = 0;

class Zones {
    int id; // 添加区域编号成员
    std::vector<int> adjacentIds; // 存储相邻区域的id
    Colours colour;
public:
    std::string name;

    // 默认构造函数，初始化默认值
    Zones() : id(0), colour(red) {}

    // 构造函数：区域id，相邻区域id列表，名称
    Zones(int zoneId, const std::vector<int>& adjIds, const std::string& nm) 
        : id(zoneId), adjacentIds(adjIds), name(nm), colour(red) {}

    void setZoneColour(Colours c) {
        this->colour = c;
    }

    Colours getZoneColour() const {
        return this->colour;
    }

    int getId() const {
        return this->id;
    }

    // 判断当前区域是否和另一个区域相邻
    bool isAdjacentTo(const Zones& other) const {
        for (int adjId : adjacentIds) {
            if (adjId == other.getId()) {
                return true;
            }
        }
        return false;
    }
};

// 辅助函数：将颜色枚举转为字符串，方便打印
std::string colourToString(Colours c) {
    switch(c) {
        case red: return "red";
        case green: return "green";
        case blue: return "blue";
        case yellow: return "yellow";
        default: return "unknown";
    }
}

void mapColouring(const std::vector<Colours>& colVec, std::vector<Zones> zSolVec, std::vector<Zones> zVec);

int main(int argc, char **argv) {
    // 初始化区域：id，相邻区域id列表，名称
    Zones z1(1, {2,3,4,5}, "z1");
    Zones z2(2, {1,3,4,5}, "z2");
    Zones z3(3, {1,2,4}, "z3");
    Zones z4(4, {1,2,3,5}, "z4");
    Zones z5(5, {1,2,4}, "z5");

    std::vector<Zones> zVec = {z1, z2, z3, z4, z5};
    std::vector<Colours> shades = {red, green, blue, yellow};

    mapColouring(shades, {}, zVec);

    if (count == 0) {
        std::cout << "No valid solutions found." << std::endl;
    }

    return 0;
}

void mapColouring(const std::vector<Colours>& colVec, std::vector<Zones> zSolVec, std::vector<Zones> zVec) {
    // 所有区域都已着色，输出解
    if (zSolVec.size() == 5) {
        count++;
        std::cout << "\n" << count << ") ";
        for (const Zones& z : zSolVec) {
            std::cout << z.name << "-" << colourToString(z.getZoneColour()) << " ";
        }
        return;
    }

    if (zVec.empty()) {
        return;
    }

    // 取出当前要着色的区域
    Zones curZone = zVec.back();
    zVec.pop_back();

    // 尝试所有颜色
    for (Colours c : colVec) {
        curZone.setZoneColour(c);

        // 检查当前颜色是否和已着色的相邻区域冲突
        bool isValid = true;
        for (const Zones& coloredZone : zSolVec) {
            if (curZone.isAdjacentTo(coloredZone) && curZone.getZoneColour() == coloredZone.getZoneColour()) {
                isValid = false;
                break;
            }
        }

        if (isValid) {
            // 复制已着色列表，添加当前区域，递归
            std::vector<Zones> newSolVec = zSolVec;
            newSolVec.push_back(curZone);
            mapColouring(colVec, newSolVec, zVec);
        }
        // 如果无效，跳过当前颜色，继续尝试下一个
    }
}

关键修改说明 #

1. Zones类优化：

   • 添加id成员存储区域编号，adjacentIds存储相邻区域id，替代原来的side1-side4，更灵活
   • 添加isAdjacentTo方法，封装相邻判断逻辑，代码更清晰
   • 构造函数初始化colour为默认值，避免未定义行为

2. 递归逻辑修复：

   • 用size()判断完成状态和空容器
   • 遍历所有已着色区域，检查当前颜色是否冲突，确保没有遗漏
   • 冲突时跳过当前颜色，不终止整个分支

3. 打印优化：

   • 添加colourToString函数，将枚举值转为可读字符串，方便查看结果

现在运行代码，应该能正确输出所有合法的区域着色方案。

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