N皇后问题,,回溯与迭代
穷举法的例子,每行只能有一个,每列也只能有一个,整个棋盘共n个,可以以行为单位遍历。从第一行开始,对行的每一列都进行判定,如果当前位置可以,则将其坐标进栈,然后判断下一行(因为一行只能有一个,当前行已经放置了),仍从第一列开始。当判断到最后一行时,若有位置满足,则一条路径已经找到,输出。否则,若最后一行所有列都遍历完后仍不满足,需要改变上一行的位置,寻找上一行中后面的可满足的,更新棋盘,重点理解回溯的过程,queen(row+1)是在判断第row行有一个合适位置(row,k)之后调用的,是在找k的for()循环中的。如一共有4行4列,当进行到queen(4)时,函数结束递归,输出一个结果,删除栈顶元素(最后一行的位置)此时queen(4)执行完成,返回到调用她的地方,即判断第三行的(3,k),然后执行k++,继续寻找第三行后面的可行位置。整个第三行找完以后,返回到(2,k'),进行k'++.....如此回溯,便可找到所有路径。
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10
#define max 10
#define overflow -1
#define error -1
typedef struct{
int row;
int col;
}ElemType;
int tag=1;
typedef struct{
ElemType * base;
ElemType * top;
int stacksize;
int len;
}SqStack;//栈用于存放路径
//栈的基本操作
void InitStack(SqStack * S){//问题:define int Status 函数返回OK(1) 前面关于int会错误,,写返回void 会有没有影响?
(*S).base=(ElemType *)malloc( STACK_INIT_SIZE*sizeof(ElemType));
if(!(*S).base) exit(overflow);
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
(*S).len=0;
}
void Push(int row,int col,SqStack * S){
ElemType e;
e.row=row; e.col=col;
if((*S).top-(*S).base>=(*S).stacksize){
(*S).base=(ElemType *)realloc((*S).base,((*S).stacksize+STACK_INCREMENT)*sizeof(ElemType));
if(!(*S).base) exit(overflow);
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACK_INCREMENT;
}
*(*S).top++=e;
(*S).len++;
}
int Pop(SqStack *S){
ElemType e;
if((*S).len==0)
return error;
e = *(--(*S).top);
(*S).len--;
}
void print_result(SqStack S){
ElemType * p=S.base;
printf("%d: ",tag);
for(;p<S.top;p++){
printf("(%d,%d) ",(*p).row+1,(*p).col+1);
}
printf("\n");
tag++;
}
int can_place(int row,int col,SqStack S){
ElemType * s=S.base;
while(s<S.top){
if((*s).col==col)
return 0;
else if(abs(row-(*s).row)==abs(col-(*s).col))//开始写成行减=1,是全部的上下对角线啊,不是紧邻的
return 0;
s++;
}
return 1;
}
void queen(int row,int n,SqStack *S){
int k;
if(row==n)
{
print_result(*S);
Pop(S);
}
else{
for(k=0;k<n;k++){
if(can_place(row,k,(*S))){
Push(row,k,S);
queen(row+1,n,S);
}
}//for
if(k==n)
Pop(S); //这一行没有,删除栈顶元素
}//else
}
int main(){
int n;
SqStack S;
InitStack(&S);
scanf("%d",&n);
queen(0,n,&S);
return 0;
}