417-回溯算法-八皇后问题

深藏阁楼爱情的钟 2022-09-05 01:41 219阅读 0赞

## 八皇后问题 ##

**一个国际象棋，棋盘有8行8列，现在有8个皇后，8皇后就是8个棋子，皇后是不能处在同一行或者同一列或者同一斜线上。问：有多少种摆法，让8个皇后不能互相吃掉？**

**原始序列下满足特定条件的排列方式。**

从根节点开始，处理的是第0个位置，然后处理第1个位置，接下来处理第2个位置…直到处理最后一个位置。  
相当于就是处理第1行的皇后棋子，第2行的皇后棋子，第3行的皇后棋子…  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
**下标代表行，下标对应的值是列**  
**i == j 判断同一行 ar\[i\] == ar\[j\]判断同一列，这2种情况是不可能的**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**主要判断是否在同一个斜线**  
两个元素的 行-行==列-列  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][44837eef319a4f6d991bb2fe00f07b78.png]

int cnt = 0;//统计8皇后的排列次数
    void swap(int arr[], int i, int j)//交换元素
    {
        
    	int tmp = arr[i];
    	arr[i] = arr[j];
    	arr[j] = tmp;
    }
    bool judge(int ar[], int i)//i表示当前放置皇后棋子的位置
    {
        
    	for (int j = 0; j < i; ++j)//遍历的就是0行-i-1行，已经确定好的
    	{
        
    		if (i == j || ar[i] == ar[j] || abs(i - j) == abs(ar[i] - ar[j]))
    		//i == j判断同一行 ar[i] == ar[j]判断同一列，这2种情况是不可能的。主要判断是否在同一个斜线
    		{
        
    			return false;
    		}
    	}
    	return true;
    }
    void func(int ar[], int i, int length)//排列树的实现
    {
        
    	if (i == length)//到达叶子节点了，访问到一种排列方式了
    	{
        
    		cnt++;
    		for (int j = 0; j < length; ++j)//得到一种排列了
    		{
        
    			cout << ar[j] << " ";
    		}
    		cout << endl;
    	}
    	else
    	{
        
    		for (int k = i; k < length; ++k)//当前节点从i开始
    		{
        
    			swap(ar, i, k);//i的位置和k的位置的值进行交换，生成1个孩子，进入下一层
    			//现在放的是第i个位置，第i个位置确定放好了
    			if (judge(ar, i))//判断第i个位置的元素，是否满足8皇后的条件   0 - i-1的放好了//剪枝操作
    				func(ar, i + 1, length);//生成孩子节点，也就是说会生成一系列的排列方式
    			swap(ar, i, k);//回溯到父节点
    		}
    	}
    }
    int main()
    {
        
    	//把ar数组的下标当作行，下标对应的元素的值当作列，即8行8列
    	//初始化是，1行1列，2行2列，3行3列....8行8列
    	//表示了不可能放在同一行同一列的。下标都不同了
    	//所以现在我们主要判断不在一条斜线上
    	int ar[] = {
         1,2,3,4,5,6,7,8 };
    	int n = 8;
    	func(ar, 0, n);
    	cout << "cnt:" << cnt << endl;
    	return 0;
    }

![在这里插入图片描述][c33acec2917f487c8391166dd3e6ed9f.png]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/accb97b4e3af404490adedb42531365e.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/97b937cc22434881afc8536379599e27.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_13_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/000ce45154374af885fcbabc9ab23e3b.png
[44837eef319a4f6d991bb2fe00f07b78.png]: /images/20220829/4783437dca524c7982af0b7a7b0b7348.png
[c33acec2917f487c8391166dd3e6ed9f.png]: /images/20220829/4f47cfafb08d47eb80a57b381ef52d27.png