怎样用随机法求出八皇后问题的一个解

Question

这是我们的老师提出来的问题，具体要求如下
八皇后问题在以前的上机题中已经实现过一次，但是很多同学都是在回溯法思想上用确定法求解的。用确定法求解能够完整地将92个解全部求出，但是在求解其中地任意一个解时，性能还是差了些。
现在请同学们用概率法求解八皇后问题的一个解。用到的基本思想还是回溯法，但是在将下一个皇后放入某一个格子时，不是按照从左到右的次序来，而是随机放入某一个位置中。如果这个位置不合适，再随机生成另一个位置放入皇后。
我现在的问题是用随机函数真的能碰巧求出一个解吗，虽然理论上可行，但是实际上rand函数很多时候产生的数都相同，不能把1到8的数都随机产生一遍，我试了一下，产生不出来（我是在我以前写的求出92个解的程序上改动的），有高手能提点一下吗

Answer 1

我用随机法的c++程序如下
#include<iostream.h>
#include<stdlib.h>
#include<windows.h>
#include<time.h>
 int x[9];
 bool a[9],b[17],c[15];
 int index(1);
 int i;
 DWORD t;
DWORD Tstart;
DWORD Tend;void print()
{
int k;
cout<<index;
for(k=1;k<=8;k++)

cout<<'('<<k<<','<<x[k]<<')';
    cout<<endl;
index++;}
/*void FindPos(int i)
{
  int j;
  for (j=1;j<=8;j++)
  {
    t=i-j;
if (t<0)
t=7-t;
  if (a[j]&&b[i+j]&&c[t])
  {
  x[i]=j;
  a[j]=false;
  b[i+j]=false;
  c[t]=false;
   if (i<8)
   FindPos(i+1);
   else
   print();
  a[j]=true;
  b[i+j]=true;
          t=i-j;
if (t<0)
t=7-t;
  c[t]=true;
  }//end if  }   */
  void RandomFindPos(int i)
{
  int t;
  int j;
  int temp;
 temp1: srand(time(NULL));
 // for (j=1;j<=8;j++)
 j=rand()%8+1;
 temp=j;
//  {
    t=i-j;
if (t<0)
t=7-t;
  if (a[j]&&b[i+j]&&c[t])
  {
  x[i]=j;
  a[j]=false;
  b[i+j]=false;
  c[t]=false;
   if (i<8)
   RandomFindPos(i+1);
   else
   {
   print();
   
   return;
   }
  a[j]=true;
  b[i+j]=true;
         if (t<0)
t=7-t;
  c[t]=true;
goto temp1;
  }//end if
//  }
      
}// end FindPos
void main()
{
for(int i=0;i<9;i++)
a[i]=true;
for(i=0;i<17;i++)
b[i]=true;
for(i=0;i<15;i++)
c[i]=true;
Tstart=GetTickCount();
  RandomFindPos(1);
Tend=GetTickCount();
 t=Tend-Tstart;
cout<<t<<endl;}
用/**/注释的是原来的回溯算法（已经运行是正确的），下面是随机算法，但是只能最多确定6个位置（用单步调试观察到），要确定八个位置很难，大家可以看看我的写法是否正确，给点意见。

Answer 2

>>回溯是性能最好的算法性能最好?回溯的时间,空间复杂度都很高,如何体现性能好?现实中的很多问题根本无法用回溯去求解.不过八皇后问题比较简单,回溯确实是最好的方法.如果由此扩展到N皇后,N远大于8,回溯就不一定好使了.其实模拟退火,遗传算法都是有导向性的随机算法,楼主可以很容易找到资料看看.示例程序的话,另一个经典问题TSP比较容易找到.不过很多时候只能做到以极高的效率趋近最优解,要绝对保证是全局最优解,多数情况也只能全局遍历.当然这其中也有其它一些一般技巧,比如利用Hash Table实现用空间换时间等等.