C语言解决回溯法求解n后问题和图的M着色问题

回溯法是一种常用的解决问题的算法思想。对于n后问题，可以使用回溯法求解。n后问题是指在一个n×n的棋盘上放置n个皇后，使得任意两个皇后都不在同一行、同一列或同一斜线上。以下是C语言实现的n后问题的代码：

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

#define N 8 // 棋盘大小为8

int queen[N] = {0}; // 存放皇后所在列的数组
bool col[N] = {false}; // 判断列是否有皇后
bool left[N * 2 - 1] = {false}; // 判断左斜线是否有皇后
bool right[N * 2 - 1] = {false}; // 判断右斜线是否有皇后

void print_result() // 输出结果
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (j == queen[i])
            {
                printf("Q ");
            }
            else
            {
                printf(". ");
            }
        }
        printf("\n");
    }
    printf("\n");
}

void search(int row) // 搜索皇后的位置
{
    if (row == N) // 找到解
    {
        print_result(); // 输出结果
        return;
    }
    for (int i = 0; i < N; i++) // 遍历列
    {
        if (!col[i] && !left[row + i] && !right[N - 1 + row - i]) // 判断该位置是否可以放置皇后
        {
            queen[row] = i; // 记录皇后所在列
            col[i] = true; // 记录该列已有皇后
            left[row + i] = true; // 记录左斜线已有皇后
            right[N - 1 + row - i] = true; // 记录右斜线已有皇后
            search(row + 1); // 继续搜索下一行
            col[i] = false; // 回溯
            left[row + i] = false; // 回溯
            right[N - 1 + row - i] = false; // 回溯
        }
    }
}

int main()
{
    search(0); // 从第0行开始搜索
    return 0;
}

M着色问题是指在一个无向图中对每个节点进行着色，使得相邻的节点颜色不同。以下是C语言实现的M着色问题的代码：

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

#define N 5 // 图的节点数
#define M 3 // 颜色数

bool graph[N][N] = { // 无向图的邻接矩阵
    { false, true, true, true, false },
    { true, false, true, false, true },
    { true, true, false, true, true },
    { true, false, true, false, true },
    { false, true, true, true, false }
};

int color[N] = {0}; // 存放节点的颜色

bool check(int node, int c) // 判断节点能否被着色
{
    for (int i = 0; i < N; i++)
    {
        if (graph[node][i] && c == color[i]) // 如果该节点与相邻节点颜色相同，则无法着色
        {
            return false;
        }
    }
    return true;
}

void print_result() // 输出结果
{
    for (int i = 0; i < N; i++)
    {
        printf("%d ", color[i]);
    }
    printf("\n");
}

void search(int node) // 搜索节点的颜色
{
    if (node == N) // 找到解
    {
        print_result(); // 输出结果
        return;
    }
    for (int i = 0; i < M; i++) // 遍历颜色
    {
        if (check(node, i)) // 判断该节点能否被着色
        {
            color[node] = i; // 记录节点的颜色
            search(node + 1); // 继续搜索下一个节点
            color[node] = 0; // 回溯
        }
    }
}

int main()
{
    search(0); // 从第0个节点开始搜索
    return 0;
}

以上是回溯法解决n后问题和M着色问题的C语言实现。