DFS + 回溯法：N皇后问题

骑猪看日落 2023-10-06 16:55 65阅读 0赞

## DFS + 回溯法：N皇后问题 ##

#### 问题： ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]

#### 思路：DFS+回溯 ####

DFS+回溯法解题是一种思想，不是说这道题目是图的题，非图的题可以使用这种思想解决  
  我们可以建立一个dfs函数逐行遍历所有情况，dfs函数的参数有我们需要return的ans，当前行数row，N  
  我们需要知道哪些点是被禁用的，因此我们需要创建标记数组。对于我们放皇后的点，与它同行、同列、以及在它所在的主对角线和副对角线上的点全部被禁用，由于我们是逐行遍历，因此不需要建立行的标记数组，因此我们需建立列标记数组、主对角线标记数组、副对角线标记数组

列标记数组使用列的下标就可以了，主副对角线标记数组如何表示呢？我们可以注意到，在任一条主对角线上的元素，其列号-行号的值都相等，在任一条副对角线上的元素，其列号+行号的值都相等。 因此我们可以将列号-行号+N作为主对角线标记数组的下标，加N是为了防止列号-行号为负数，将列号+行号作为副对角线标记数组的下标。

在每一行的dfs函数中，我们需要遍历该行的所有列，若当前遍历点没有禁用，在该点放皇后，更新标记数组，接下来调用dfs( ans,N,row+1 )，进入下一行，若从下一行返回，则相当于从树的子节点返回到它的父节点，此时表示这种情况已遍历完，需要移除当前的皇后，即回溯过程，需将之前更新的标记数组还原，以便遍历当前行的下一个点

当row=N时，表示已经放完N个皇后，此时ans++，并return

#### 代码： ####

# include <bits/stdc++.h>
    using namespace std;
    int table_main[30];
    int table[30];
    int col[15];
    void dfs( int& ans,int N,int row )
    {
        
    	if( row==N )
    	{
        
    		ans++;
    		return;
    	}
    	int i;
    	for( i=0;i<N;i++ )
    	{
        
    		if( col[ i ]==1 || table_main[ i-row+N ]==1 || table[ i+row ]==1 )
    			continue;
    		col[ i ]=1;
    		table_main[ i-row+N ]=1;
    		table[ i+row ]=1;
    		dfs( ans,N,row+1 );
    		col[ i ]=0;
    		table_main[ i-row+N ]=0;
    		table[ i+row ]=0;
    	}
    }
    int main()
    {
        
    	int N;
    	memset( table_main,0,sizeof( table_main ) );
    	memset( table,0,sizeof( table ) );
    	memset( col,0,sizeof( col ) );	
    	scanf( "%d\n",&N );
    	int ans=0;
    	dfs( ans,N,0 );
    	printf( "%d\n",ans );
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210320111740123.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20210320111750468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0NzA5OTkw,size_16,color_FFFFFF,t_70