递归---n皇后问题

蔚落 2023-06-25 05:00 22阅读 0赞

# 题目描述： #

在 n x n 的棋盘上面所有的皇后不能相互攻击，即所有的皇后 既不在同一行、不在同一列，也不在同一对角线，如下图所示（以 4 x 4 的棋盘举例）：  
![在这里插入图片描述][70] ![在这里插入图片描述][70 1]  
但是要求求出 n x n 的棋盘上所有排法

# 输入： #

n（皇后个数，代表 n x n 的棋盘）

# 输出： #

第一行：皇后的第一种排法（共 n 个元素，每个元素代表皇后 每行摆放的列数）  
…  
第 k 行：皇后的第 k 种排法

# Sample Input #

# Sample Output #

2413
    3142

# 代码： #

#include<iostream>
    #include<cmath>
    #define _for(a,b,c) for(int a=b;a<c;a++) 
    using namespace std; 
    
    int line[100]; //皇后所在列数
    int n; //皇后个数
     
    void output(int n) //输出 n 皇后的一种排法
    { 
    	_for(i,1,n+1) cout << line[i];
    	cout << endl;
    }
     
    int place(int m,int i) //判断第 m 行皇后能否放在第 i 列
    { 
    	_for(j,1,m)  if(i == line[j] || abs(m-j) == abs(i - line[j]))  return 0; //每行都试一遍，若结果不可行，则返回 0 
    	return 1; //结果可行，则返回 1 
    }
     
    void nqueen(int m) //求第 m 行皇后放置的位置（前提是前 m-1 行皇后已经摆放完毕）
    { 
    	_for(i,1,n+1)
    	{ 
    		line[m] = i; //从第一个位置开始试 
    		if (place(m,i)) //判断第 m 行皇后能否放在第 i 列
    		{ 
    			if (m == n)  output(n); //如果最后一个皇后也放置完毕，则输出结果
    			else  nqueen(m + 1); //否则，进行下一个皇后的放置
    		}
    	}
    	//return 
    }
    
    int main()
    { 
    	cin >> n;
    	nqueen(1); //求第 m 行皇后放置的位置
    	return 0;
    }

[70]: https://img-blog.csdn.net/20180706222353941?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhbmN5X3RyYWNr/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 1]: https://img-blog.csdn.net/20180708200300364?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhbmN5X3RyYWNr/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70