回溯算法

一、概念

回溯算法实际上是一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就"回溯"返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为"回溯点"。许多复杂的，规模较大的问题都可以使用回溯法，有"通用解题方法"的美称。

二、思路

1.针对所给问题，定义问题的解空间，它至少包含问题的一个（最优）解。
2.确定易于搜索的解空间结构，使得能用回溯法方便地搜索整个解空间 。
3.以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。

三、应用

八皇后问题

在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上（斜率为1），问有多少种摆法。（答案是92种）

#include<stdio.h> 

int arry[8][8]; //棋盘，放皇后
int map = 0; //存储方案结果数量

void print() { //打印结果
    printf("方案%d:\n", map);
    for(int i=0; i<8; i++) {
        for(int j=0; j<8; j++) {
            if(arry[i][j] == 1) {  
                printf("o ");
            } else {
                printf("+ ");
            }
        }
       printf("\n");
    }
    printf("\n");
}

bool check(int k, int j) { //判断节点是否合适摆放皇后，参数k表示行，参数j表示列 
    for(int i=0; i<8; i++) { //检查列冲突，由于摆放皇后是根据行数递增的顺序，因此行是不会冲突的，只需检查列冲突 
        if(arry[i][j] == 1) {
            return false;
        }
    }
    for(int i=k-1,m=j-1; i>=0 && m>=0; i--,m--) { //检查左对角线冲突 
        if(arry[i][m] == 1) {
            return false;
        }
    }
    for(int i=k-1,m=j+1; i>=0 && m<=7; i--,m++) { //检查右对角线冲突 
        if(arry[i][m] == 1) {
            return false;
        }
    }
    return true;
}

void findQueen(int i) { //寻找皇后摆放位置，参数i表示尝试将皇后i放入第i行（i从0开始算起） 
    if(i>7) { //递归结束条件，i大于7，说明8个皇后已经摆放好 
        map++;
        print(); //打印八皇后的解
        return;
    }
    
    for(int j=0; j<8; j++) { //尝试将皇后放入第i行（i为输入参数）第j列（j从0开始算起） 
        if(check(i, j)) { //检查第i行第j列是否合适摆放皇后 
            arry[i][j] = 1; //合适摆放皇后，则将该位置的值设置为1 
            findQueen(i+1); //递归调用，尝试将皇后i+1放入第i+1行 
            arry[i][j] = 0; //上一条递归语句执行完毕说明已经找到了一种方案，之后会进行递归的回溯阶段，这里需要将上一次设置的合适摆放皇后的位置的值改成0，然后尝试下一个位置看是否合适摆放皇后 
        }
    }   
}

int main() {
    printf("八皇后问题\n");
    findQueen(0);
    printf("八皇后问题共有%d种可能\n", map);
    return 0;
}