问题 D: 【递归入门】n皇后 问题(原始的8皇后问题)
时间限制: 1 Sec 内存限制: 128 MB
提交: 84 解决: 53
题目描述
会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 * 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。
输入
一个整数n( 1 < = n < = 10 )
输出
每行输出对应一种方案,按字典序输出所有方案。每种方案顺序输出皇后所在的列号,相邻两数之间用空格隔开。如果一组可行方案都没有,输出“no solute!”
样例输入
4
样例输出
2 4 1 3
3 1 4 2
经验总结
n皇后是个经典问题,关键,还是要理清楚思路,将构思实现在递归和非递归不同的框架中,需要注意实现点的不同
递归要思考:1,如何在一个分支结束之后进入另一个分支
2,满足什么条件时开始返回
3,用什么数据结构存储所需数据
非递归要思考:1,用什么来表示层次的递进?(一般是栈)
2,在递归中达到条件时进行返回,用非递归应该如何对层次栈和数据栈进行操作?
3,如何在循环实现选择另一个分支?
4,出栈时,数据栈还有其他的操作变量应该如何改变?
思考完这些问题,并且可以正确实现,那应该就没什么问题啦~ 总结完毕(●′ω`●) ~~
#include <cstdio>
int n,result[15],count;
void n_queen(int index)
{
if(index==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",result[i]+1);
}
printf("\n");
count++;
return;
}
bool flag[15]={false};
for(int i=0;i<index;i++)
{
flag[result[i]]=true;
int lower_right=i+result[i]-index;
int top_right=-i+result[i]+index;
if(lower_right>=0)
flag[lower_right]=true;
if(top_right<=n-1)
flag[top_right]=true;
}
for(int i=0;i<n;i++)
{
if(flag[i]==false)
{
result[index]=i;
n_queen(index+1);
}
}
}
int main()
{
while(~scanf("%d",&n))
{
count=0;
n_queen(0);
if(count==0)
printf("no solute!\n");
}
return 0;
}
#include <cstdio>
#include <stack>
#include <vector>
using namespace std;
int n,count;
void n_queen()
{
vector<int> result;
vector<vector <int> move;
bool pop=false;
int top;
result.push_back(0);
vector<int> temp;
for(int i=1;i<n;i++)
{
temp.push_back(i);
}
move.push_back(temp);
while(!result.empty())
{
if(result.size()==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",result[i]+1);
}
printf("\n");
count++;
pop=true;
}
if(pop)
{
result.pop_back();
pop=false;
}
top=result.size();
if(top<n)
{
if(move.size()<=top)
{
bool flag[15]={false};
int index=result.size();
for(int i=0;i<index;i++)
{
flag[result[i]]=true;
int lower_right=i+result[i]-index;
int top_right=-i+result[i]+index;
if(lower_right>=0)
flag[lower_right]=true;
if(top_right<=n-1)
flag[top_right]=true;
}
vector<int> temp1;
for(int i=0;i<n;i++)
{
if(flag[i]==false)
{
temp1.push_back(i);
}
}
if(temp1.size()==0)
{
pop=true;
}
else
{
move.push_back(temp1);
result.push_back(move[top][0]);
move[top].erase(move[top].begin());
}
}
else
{
if(move[top].size()==0)
{
move.erase(move.begin()+top);
pop=true;
}
else
{
result.push_back(move[top][0]);
move[top].erase(move[top].begin());
}
}
}
}
}
int main()
{
while(~scanf("%d",&n))
{
count=0;
n_queen();
if(count==0)
printf("no solute!\n");
}
return 0;
}