[回溯法]从蛮力算法起步,谈八皇后问题的求解:
[回溯法]从蛮力算法起步,谈八皇后问题的求解:
By EmilMatthew
05/9/15
八皇后是一个相当著名的算法问题：题目说是在8*8国际象棋棋盘上，要求在第一行放置一个皇后，且能做到在竖方向，斜方向都没有冲突。
这里首先谈一下解集合的选取方式，如果用一个二维数组来存放八皇后的位置，难免比较浪费，注意到八个皇后不可能位于同一行，所以只要存放各个皇后在竖方向的位置即可。所以存放解集仅需要一个长度为8的整型数组即可.
首先看到这个问题，最容易想到的想法就是穷举法,每次在当前行中的第一列起摆当前这个皇后的位置，发现有冲突时则终止当前的次的搜索，当发现当前的这个行的皇后与前面的皇后没有冲突时，则跳到下一行，继续从第一列起摆放皇后的位置.如果当前行的皇后已摆至最后一列了，则应跳到上一行.
由于行数已经不可能相同了，所以了不起也就是做一个8!的次运行次数的算法便可以得到最终解了.不过，很快，这种自然的一蹋糊涂的想法便要被打住了，如果不是8皇后呢，如果是20皇后呢？效率低不说，光是要修改源程序这一个不足点便可以将这种想法否决掉了.
优化的出路在哪里呢，其实，改进的工作也没有动啥”大手术”,主要是做到下面两件事情：
1) 一旦当前的集不满足条件时,便终止当前的搜索树的分枝,并回退到前一层继续搜索.
(其实，前面的蛮力法退出是满足的，就是这个回退做不了。)
2 如果当前的解满足部分解的条件时，则继续跳到下一行搜索，发现有全解时终止搜索.
(前面的蛮力法做这个也是没问题的)
关于搜索树的最基本的想法，可以参考我前面的一篇愚作---http://blog.csdn.net/emilmatthew/archive/2005/08/03/445132.aspx
所以，从蛮力法跳到相对“高级”的回溯法我们就提高了一步----能回退到上一层.
而这个动作，可以通过递归和非递归两种方式来实现,递归的会相对好理解些，另一种非递归的也不难理解的.
而一旦使用回溯法，则程序的柔韧性得到了极大的提高，可以求解N皇后问题.
在展示最后的实现版本之前，先来看几个输助的函数，判定是否有冲突和是否局部完成位置的函数。
由于我们的结果数组存放的仅仅是列中的位置，而行中的位置肯定是相异的，所以，只需要判定斜方向是否有冲突和竖直方向是否有冲突就可以了：
//判定当前结点在斜方向和另一个结点是否有冲突:
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;
}
//判定是完成了一个N皇后的排列，用的还是partFinished,但在算法的表达上更为贴切.
int fullFinished(int* arr,int len)
{
assertF(arr!=NULL,"in fullFinished,arr is null\n");
eturn partFinished(arr,len);
}
好了，有了这些底层的函数作为铺垫，那么再来实现我们上层的算法那就要清楚和明朗多了.
1） 首先看一下递归版本的实现: (相当的简洁和好懂)
//NqueensProblems Solution Recursive1 Search and Print out all the answers.
void NQueensProblem2(int* arr,int depth,int size,int* count,FILE* outputFile)
{ /*default:a[1..n]=0 , 0 , size, 1, outputFile*/
//nowSize,finished rows. [1..n]
//size,total problem size. [n]
int i=0;
assertF(outputFile!=NULL,"in NQueensProblems2 outputFile is null\n");
assertF(count!=NULL,"in NQueensProblems2 count is null\n");
if(!partFinished(arr,depth+1))return;
//如果当前的结点和前面的结点有冲突,则终断当前搜索的子分支.
else if(fullFinished(arr,size)&&depth+1==size)/*如果全部完成了，则同样终断当前搜支，并打印出当前的结集.*/
{
fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,*count);
(*count)++;//结果数目加1
}
else //partFinished ，部分解
{
depth++; //branch to a deeper levels,展开搜索树到下一个深度搜索
for(i=0;i<size;i++)
{
arr[depth]=i+1;//搜索下一个深度的所有结点
//because it is a depth first search ,it will not affect another search branch.
NQueensProblem2(arr,depth,size,count,outputFile);
}
}
}
这个递归的版本有一个不足之处在于，第一层树的展开工作要手工来做:
即:
for(i=0;i<problemSize;i++)
{
ansCol[0]=i+1;//first level branch. node the col pos is between [1..n]
NQueensProblem2(ansCol,0,problemSize,count,outputFile2);
}
2有了递归版本作铺垫，再来看这个非递归版本也不会有太大的困难了:
//Nqueens Problem Solution1 Unrecursive,could get the full or only one answer set.
void NQueensProblem1(int size,int mode)
{
//attention ,the output position use 1...n.
int* arr;
int i=0,k=0;
int count=0;
FILE* outputFile;
outputFile=createFile('w',"NQueensAns.txt");
arr=(int*)malloc(sizeof(int)*size);
for(i=0;i<size;i++)
arr[i]=0;
k=0;
count=1;
while(k>=0)//k: stands for the branch tree's levels,which start from 0 to size-1
{
while(arr[k]<=size-1)//arr[0..size-1]: stands for the v position of the queens.from(1 to size).
{
arr[k]++;//search the parallel level's next possible position.
if(fullFinished(arr,k+1)&&(k+1==size))//full answer check.
{
fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,count);
outputListArrInt(arr,0,size,outputFile);
outputQueensAns(arr,size,outputFile);
count++;
if(!mode)/*no need all resolved.根据参数调节是否要输出全部解集，如果/。要，则从这里跳出.*/
goto out;
}
else if(partFinished(arr,k+1))//if only part finished. Branching to a deeper level.
{
k++;//move to a deeper level---branching new search child tree.
}
}
/*If current search has no solution ,roll back to the up level*/
arr[k]=0;//set current node to unUsed.
k--;//roll back to the pre level.
}
out:
free(arr);
}
3这里给出第三个版本，同样是一个递归的版本，这个版本只能打到第一组解，但是比较好的地方在于可以不用在外部调用层把第一层的情况给展开:
void NQueensProblem3(int* arr,int depth,int size,int* count,FILE* outputFile)
{ //arrValue=1..n 0 .. size-1
assertF(outputFile!=NULL,"in NQueensProblems2 outputFile is null\n");
assertF(count!=NULL,"in NQueensProblems2 count is null\n");
if(depth>=size-1&&partFinished(arr,depth+1))
{
fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,*count);
outputListArrInt(arr,0,size,outputFile);
outputQueensAns(arr,size,outputFile);
(*count)++;
}
else if(!partFinished(arr,depth+1)||arr[depth]>size)//have chong tu
{
if(arr[depth]>=size)//roll back to the pre level
{
arr[depth]=1;
depth--;
arr[depth]++;
NQueensProblem3(arr,depth,size,count,outputFile);
}
else{ //search for the parallel row's next possible position
arr[depth]++;
NQueensProblem3(arr,depth,size,count,outputFile);
}
}
else //part answer is ok ,branch to a deeper level for search.
{
depth++;
arr[depth]=1;//here,at first you use 0 as start pos,wrong!
NQueensProblem3(arr,depth,size,count,outputFile);
}
}
插一句：关于第三个版本的调试.
现在看看上面这个递归版本也是相当清楚的，但我调试时却调了半天。下面把我调试记录文件中最后的比较重要的几步贴出来，和大家共同分享程序设计过程中所遇到的点点滴滴。可能有些乱的话.
debug1
else //part answer is ok ,branch to a deeper level for search.
{
//printf("%d-",arr[1]);
//push_Seq(myStack,arr[depth]);//storage current level's col pos
depth++;
arr[depth]=1;//here,at first you use 0 as start pos,wrong!
fprintf(outputFile,"brahch to deeper to %dlevel\r\n",depth);
fprintf(outputFile,"pre level node val:%d\r\n",arr[depth-1]);
outputListArrInt(arr,(int)0,(int)size,outputFile);
NQueensProblem3(arr,depth,size,count,outputFile);
}
brahch to deeper to 1level
pre level node val:1
1 1 1 1
brahch to deeper to 2level
pre level node val:3
1 3 1 1
brahch to deeper to 3level
pre level node val:5
1 3 5 1
从这个错误中,可以看出,由于没有对partResolve的上限加以限定,导致部分解没有上限~~~
debug2
试图将成功的条件上移,但是对上面的BUG是无效的.
if(depth>=size-1&&partFinished(arr,depth+1))
{
fprintf(outputFile,"Answer of%dQueens Problem No.%d:\r\n",size,*count);
outputListArrInt(arr,0,size,outputFile);
outputQueensAns(arr,size,outputFile);
(*count)++;
}
将部分不成功解中,回到上层的判定条件改成>=size
if(arr[depth]>=size)//roll back to the pre level
brahch to deeper to 3level
pre level node val:2
1 4 2 1
roll back to 2level
roll back to 1level
brahch to deeper to 2level
pre level node val:4
1 4 1 1
brahch to deeper to 3level
pre level node val:2
1 4 2 1
roll back to 2level
roll back to 1level
brahch to deeper to 2level
pre level node val:4
1 4 1 1
在第一个主分叉中的最后一棵子树中出现的死循环,原因在于当本层与先前没有冲突但已到最后一个位置时,会新生成一棵子树,然后,子树不成功,退上来,再生成,再退...
3解决方案,在不成功处加一个判定:
!partFinished(arr,depth+1)||arr[depth]>size)
if(arr[depth]>=size)//roll back to the pre level
{
arr[depth]=1;
depth--;
fprintf(outputFile,"roll back to %dlevel\r\n",depth);
arr[depth]++;//加了这一句~~~,好~~
//本来写的是if(arr[depth]<size)arr[depth]++;
//虽然看到了有多余位置的BUG,但是没挑准地方.
NQueensProblem3(arr,depth,size,count,outputFile);
}
BUG找到了，第三个版本的递归Version也实现了，呵呵~~~
算法效率的简单测试.
size=10,not all answer
version:1 time:0.0000s
version:3 time:0.0000s
Answer of10Queens Problem No.1:
1 3 6 8 10 5 9 2 4 7
(o代表皇后,*代表空余位)
o * * * * * * * * *
* * o * * * * * * *
* * * * * o * * * *
* * * * * * * o * *
* * * * * * * * * o
* * * * o * * * * *
* * * * * * * * o *
* o * * * * * * * *
* * * o * * * * * *
* * * * * * o * * *
================================================
size=15,not all answer
version:1 time:0.0930s
version:3 失效了,估计程序有错误.
size=10, all answer.(包括打出程序的结果)
version:1 time:0.89100s
version:2 time:0.53100s
当size变得更大时，程序的运行就有些长了，size=20时，第一个版本的竟然在南海诸求一组解时用了32秒,而第二个版本在一分钟内已经算不出来了~~~~
所以，求解更大规模的皇后问题,这样的程序和算法还是扛不住~~~，继续学习~~~~
源码下载，欢迎提出批评意见:
http://free5.e-168.cn/hhucskx/download/EightQueens.rar
如果直接点击无效的话，请把上面这个地址直接粘贴到IE地址栏中下载.
