HNU-人工智能-实验2-简单CSP问题

人工智能-实验2

计科210x 甘晴void

一、实验目的

• 求解约束满足问题

• 使用回溯搜索算法求解八皇后问题

  二、实验平台

  • 课程实训平台https://www.educoder.net/paths/369

    三、实验内容

    3.0 题目要求

    回溯搜索算法

    搜索与回溯是计算机解题中常用的算法，很多问题无法根据某种确定的计算法则来求解，可以利用搜索与回溯的技术求解。

    回溯是搜索算法中的一种控制策略。

    基本思想是：为了求得问题的解，先选择某一种可能情况向前探索，在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索，如此反复进行，直至得到解或证明无解。

    编程要求

    在右侧编辑器中完成void searchh(int i)函数，求出八皇后问题共有多少种算法。

    测试说明

    平台会对你编写的代码进行测试：

    预期输出：92

    3.1 A*算法原理

    1. 递归搜索：从第一行开始，逐行放置皇后，每行放置一个皇后，直到所有皇后都被放置。
    2. 选择合适位置：对于当前行的每一列，检查是否能够放置皇后。如果当前位置合法（不与已放置皇后冲突），则放置皇后，继续递归地处理下一行。
    3. 回溯选择：如果当前位置无法放置皇后，说明之前的选择不正确，需要回溯到上一步重新选择位置。
    4. 标记冲突位置：为了避免皇后之间的冲突，需要用数组 b、c、d 来标记已经放置的皇后位置所占据的列和对角线。
    5. 结束条件：当成功放置了八个皇后（即当前行数达到 8）时，找到了一组解，计数器增加，并返回上一层继续搜索其他解。

    3.2 算法实现

    1. searchh 函数中的参数 i 表示当前处理的行数。
    2. 在 for 循环中，对于当前行的每一列，都尝试放置一个皇后。
    3. 在放置皇后时，通过检查数组 b,c,d来判断当前位置是否合法：
       • b[j] 表示第 j 列是否已经有皇后；
       • c[i+j] 表示主对角线是否已经有皇后；
       • d[i-j+7] 表示副对角线是否已经有皇后。
       • 如果当前位置合法，则标记相应列和对角线已经有皇后，并递归地处理下一行。
       • 如果放置完八个皇后，即 i == 8，则找到了一个解，计数器 sum 自增。
       • 在回溯时，需要将相应列和对角线的标记清除，以便重新尝试其他位置放置皇后。

    3.3 源码&分析

    #include
    using namespace std;
    int a[9];
    int b[9]={0};
    int c[16]={0};
    int d[16]={0};
    int sum=0;
    void searchh(int i)
    {
        for(int j=1;j