c语言回溯法求解七巧板着色问题

七巧板着色问题是一个经典的NP完全问题，回溯法是一种常用的解法。

七巧板是由七个不同形状的小板组成的，要求用完所有小板，将它们拼成一个规定形状的大板，并且每个小板都要被染上一种颜色。这就是七巧板着色问题，其实质是将七巧板分别染成不同的颜色，使得它们拼成的大板符合要求。

回溯法的基本思想是从问题的某一种状态出发，搜索所有可能的解，当搜索到某一步时发现该步不能得到可行解时，就返回上一步继续搜索，直到找到解或者所有可能的状态都被搜索过。

具体实现时，我们可以从七巧板的某个小板开始，枚举该小板可能的位置和颜色，然后递归搜索下一个小板的位置和颜色。每次递归时，我们检查当前的状态是否合法，如果不合法就回溯到上一个状态继续搜索。

下面是C语言的实现代码：

#include <stdio.h>
#include <stdbool.h>

const int BOARD_SIZE = 35;  // 大板的大小
const int BLOCK_NUM = 7;  // 小块的数量
const int MAX_COLOR = 4;  // 最多的颜色数

// 每个小块的形状和初始位置
const int blocks[BLOCK_NUM][4][2] = {
    {{0, 0}, {0, 1}, {0, 2}, {0, 3}},  // I
    {{0, 0}, {0, 1}, {1, 0}, {1, 1}},  // O
    {{0, 0}, {0, 1}, {0, 2}, {1, 1}},  // T
    {{0, 0}, {0, 1}, {0, 2}, {1, 2}},  // L
    {{0, 0}, {0, 1}, {0, 2}, {1, 0}},  // J
    {{0, 0}, {0, 1}, {1, 1}, {1, 2}},  // S
    {{0, 0}, {0, 1}, {1, 0}, {1, -1}}  // Z
};

int board[BOARD_SIZE][BOARD_SIZE];  // 大板
bool used_color[MAX_COLOR];  // 记录每种颜色是否已经使用过

// 判断当前状态是否合法
bool is_valid(int block_id, int color, int x, int y) {
    // 遍历小块的每个格子
    for (int i = 0; i < 4; i++) {
        int nx = x + blocks[block_id][i][0];
        int ny = y + blocks[block_id][i][1];
        // 判断是否越界
        if (nx < 0 || nx >= BOARD_SIZE || ny < 0 || ny >= BOARD_SIZE) {
            return false;
        }
        // 判断是否与相邻的小块颜色相同
        if (board[nx][ny] >= 0 && board[nx][ny] == color) {
            return false;
        }
    }
    return true;
}

// 回溯搜索
bool backtrack(int block_id) {
    // 如果所有小块都已经染色，说明已经找到了可行解
    if (block_id == BLOCK_NUM) {
        return true;
    }
    // 枚举当前小块可能的位置和颜色
    for (int x = 0; x < BOARD_SIZE; x++) {
        for (int y = 0; y < BOARD_SIZE; y++) {
            for (int color = 0; color < MAX_COLOR; color++) {
                // 如果该颜色已经被使用过，跳过
                if (used_color[color]) {
                    continue;
                }
                // 判断是否可以将当前小块染成该颜色
                if (is_valid(block_id, color, x, y)) {
                    // 染色
                    for (int i = 0; i < 4; i++) {
                        int nx = x + blocks[block_id][i][0];
                        int ny = y + blocks[block_id][i][1];
                        board[nx][ny] = color;
                    }
                    used_color[color] = true;
                    // 递归搜索下一个小块
                    if (backtrack(block_id + 1)) {
                        return true;
                    }
                    // 回溯
                    for (int i = 0; i < 4; i++) {
                        int nx = x + blocks[block_id][i][0];
                        int ny = y + blocks[block_id][i][1];
                        board[nx][ny] = -1;
                    }
                    used_color[color] = false;
                }
            }
        }
    }
    return false;
}

int main() {
    // 初始化大板和颜色
    for (int i = 0; i < BOARD_SIZE; i++) {
        for (int j = 0; j < BOARD_SIZE; j++) {
            board[i][j] = -1;
        }
    }
    for (int i = 0; i < MAX_COLOR; i++) {
        used_color[i] = false;
    }
    // 搜索可行解
    if (backtrack(0)) {
        // 输出结果
        for (int i = 0; i < BOARD_SIZE; i++) {
            for (int j = 0; j < BOARD_SIZE; j++) {
                printf("%d ", board[i][j]);
            }
            printf("\n");
        }
    } else {
        printf("No solution.\n");
    }
    return 0;
}

在上面的代码中，我们使用一个二维数组`board`表示大板的状态，-1表示该位置没有被染色，0~3表示四种颜色。使用一个布尔数组`used_color`记录每种颜色是否已经被使用过。`is_valid`函数用于判断当前状态是否合法，`backtrack`函数用于递归搜索解。

最后，我们在`main`函数中初始化大板和颜色，然后调用`backtrack`函数搜索可行解。如果找到了可行解，就输出结果；否则输出"No solution"。