[回溯法_八皇后]堆栈实现的非递归版本
By EmilMatthew
05/11/9
其实,用递归或while循环实现N皇后问题效果挺好的(请参考: http://blog.csdn.net/EmilMatthew/archive/2005/09/15/481411.aspx ),而且思路也很清楚,为什么还要去多加一个栈呢?原因在于,为了更好的训练算法及数据结构的应用,达到融会贯通的目的.做些递归与非递归程序间的转换是起码的要求.(水平菜就得这样来)
算法陈述:
用一个数组arr来表示皇后在行间或位置
depth表示下一步探索的深度
Stack作为上层跳转下来时上层位置的中间纪录.*
Size表示问题的规模.
NQueensProblem Stack Version
压首行首列元素0进栈.
depth置1
do
{
If depth达到size
则跳出并输出结果
Else
{
If(当前层[depth-1]达到了底部)
将搜索层上跳一层并压栈*
Else
{
搜索层(depth)试探同层的下一个位置i
if这个位置有冲突并且i没有超出问题规模
{
将i置于同层的下一个位置.
}
else if 这个位置有冲突并且i已超出问题规模
{
返回到上层的跳下来的位置,借助堆栈(先弹出,然后压新位置)*
探索层仍为depth
}
Else 当前位置没有冲突
{
当前位置压栈
Depth下跳一层(depth++)
}
}
}
}
下面给出算法的C程序实现:
void NQueensProblemStack(int size,FILE* outputFile)
{
//extern int partFinished(int* arr,int len);
int depth;
int i;
int* arr;
PSeqStack myStack;
int flag;
assertF(outputFile!=NULL,"in NQueensProblemStack, outputFile is null\n");
myStack=createNullSeqStack();
arr=(int*)malloc(sizeof(int)*size);
assertF(arr!=NULL,"in NQueensProblemStack,mem apply failure\n");
//data init
seqPush(myStack,0);
i=0;
depth=1;
arr[0]=0;
flag=0;
while(!isNullSeqStack(myStack))
{
if(depth==size)
{
fprintf(outputFile,"Answer of%dQueens Problem:\r\n",size);
outputListArrInt(arr,0,size,outputFile);
outputQueensAns0(arr,size,outputFile);
flag=1;
break;
}
else
{
if(arr[depth-1]==size)//previous has reach to end.
{
seqPop(myStack);
depth-=2;//return to previous level
arr[depth]=seqPop(myStack)+1;
seqPush(myStack,arr[depth]);
depth++;//set current search level
i=0;
}
else
{
arr[depth]=i;//next level's possible pos
printf("%d\t",arr[depth]);
if(!partFinished(arr,depth+1)&&i<size-1)
//collide: next level parallel search
i++;
else if(!partFinished(arr,depth+1)&&i==size-1)
//collide: return to the pre level
{
depth--;//return to previous level
arr[depth]=seqPop(myStack)+1;
seqPush(myStack,arr[depth]);
depth++;//set current search level
i=0;
}
else//no collide,branching to next level
{
seqPush(myStack,arr[depth]);//save current
depth++;
i=0;
}
}
}
}
printf("\ndepth%d\n",depth);
if(flag==1)
printf("resolve successfully\n");
else
printf("no resolve\n");
}
/*aid fun*/
int checkXiePos(int r1,int r2,int c1,int c2)
{
return !(fabs(r1-r2)==fabs(c1-c2));
}
int checkVPos(int* arr,int len)
{
int flag=1;
int i,j;
assertF(arr!=NULL,"in checkVPos,arr is null\n");
for(i=0;i<len-1;i++)
for(j=i+1;j<len;j++)
if(arr[i]==arr[j])
{
flag=0;
break;
}
return flag;
}
int partFinished(int* arr,int len)
{
int flag=1;
int i,j;
assertF(arr!=NULL,"in partFinished,arr is null\n");
flag=flag&&checkVPos(arr,len);
for(i=0;i<len-1;i++)
for(j=i+1;j<len;j++)
{
flag=flag&&checkXiePos(i,j,arr[i],arr[j]);
if(!flag)goto out;
}
out:
return flag;
}