[color=FF0000]3楼有更新的栈实现[/color]

有了递归的算法之后我们就可以考虑如何去掉递归来提高效率，我用的是栈。我将逻辑上的栈帧包含为3个元素，分别是行值、列值以及前进方向，依此来保持回溯后的状态，在回溯后将前进方向+1接着进行遍历。还有一个问题要考虑，就是应该回溯到什么位置？注意到两点：第一，当处于最后一行并摆法合法时，不可入栈，否则输出后无法回溯到正确位置；第二，当前行所有的前进方向都尝试后，必须要回溯到上一行。

下面是我利用栈来代替递归进行求解的实现：

#include <stdlib.h>

#define TRUE   ( 1 )
#define FALSE  ( 0 )

int IsIllegal(int row, int column, const int* position);
//判断在第row行第column列摆放皇后是否非法

void Queens(int n, void (* Visit)(const int* position))
{//对n皇后的结果逐个调用Visit
 //position[n]数组:position[0]为棋盘大小，即n
 //position[1]~position[n]：下标为行坐标，值为列坐标

     int* position = NULL;    //皇后位置数组
     int* stack = NULL;       //栈
     int top;                 //栈顶
     int row;                 //行
     int column;              //列
     int direction;           //前进方向
     int i;

     position = (int*)malloc((n + 1) * sizeof(int));
     stack = (int*)malloc(3 * (n + 1) * sizeof(int));
     //内存溢出处理省去
     top = -1;
     position[0] = n;

     for (i=1; i <= n; ++i)
     {
          top = 2;      //压入3个空元素
          row = 1;
          column = i;
          direction = 1;
          while(top >= 0)
          {
               if (row > n)
               {
                    (* Visit)(position);
                    direction = stack[top--];
                    column = stack[top--];
                    row = stack[top--];
                    ++direction;
               }
               else
               {
                    if ((direction > n) || IsIllegal(row, column, position))
                    {
                         direction = stack[top--];
                         column = stack[top--];
                         row = stack[top--];
                         ++direction;
                    }
                    else
                    {
                         position[row] = column;
                         if (row != n)
                         {
                              stack[++top] = row;
                              stack[++top] = column;
                              stack[++top] = direction;
                         }
                         ++row;
                         column = direction;
                         direction = 1;
                    }
               }
          }//end while
     }//end for

     free(position);
     free(stack);
     return;
}

int IsIllegal(int row, int column, const int* position)
{//判断在第row行第column列摆放皇后是否非法
     int i;

     for (i=1; i < row; ++i)
     {
          if ((position[i] == column)
               || (row - i == column - position[i])
               || (row - i == position[i] - column))
          {
               return TRUE;
          }
     }
     return FALSE;
}

最后帖一个简单的测试程序：

#include <stdio.h>
#include <stdlib.h>

void output(const int* position);
void Queens(int n, void (* Visit)(const int* position));

int main(int argc, char *argv[])
{
     Queens(8, output);

     system("pause");
     return 0;
}

void output(const int* position)
{//输出棋盘上皇后的摆放位置
     int i, j;
     static s_how_many=0;

     printf("\n##%d", ++s_how_many);
     printf("\n ABCDEFGH");

     for (i=1; i <= position[0]; ++i)
     {
          printf("\n%d", i);
          for (j=1; j <= position[0]; ++j)
          {
               if (position[i] == j)
               {
                    printf("*");
               }
               else
               {
                    printf(" ");
               }
          }

     }
     printf("\n");
     return;
}

睡觉前google了一下“eight quuens backtracking”，找到一个比较有趣的网址
[url=http://gaia.ecs.csus.edu/~wang/backtrack/queens/queen1/eightqueens.html]http://gaia.ecs.csus.edu/~wang/backtrack/queens/queen1/eightqueens.html[/url]
看了一下动画的内容，回味了一下，觉得自己上面那个用栈解八皇后编写的一塌糊涂。重新想了一下，按照网页上的思想，我采用定行尝试列的方法（网页上是定列）来遍历，记录皇后位置的数组可以和栈数组合二为一，而栈顶指针也可以和行坐标合二为一，这样一来栈帧只要一个列坐标就可以了。

1.伪代码：

while(栈不空）
{
     if ( 行(即栈顶) <= n && 列 <= n )
     {
          if ( 当前位置不能放皇后 )
          {
               列++;
          }
          else
          {
               列入栈(隐含着"行++");
               列 = 1;
          }
     }
     else
     {
          if ( 行(即栈顶) > n )
          {
               输出位置数组(即栈数组);
          }
          列退栈(隐含着"行--");
          列++;
     }
}//end while

-------------------------------------------------------------

2.实现代码:

#include <stdlib.h>

#define TRUE   ( 1 )
#define FALSE  ( 0 )

int IsIllegal(int row, int column, const int* position);
//判断在第row行第column列摆放皇后是否非法

void Queens(int n, void (* Visit)(const int* position))
{//对n皇后的结果逐个调用Visit
 //position[n]数组:position[0]为棋盘大小，即n
 //position[1]~position[n]：下标为行坐标，值为列坐标

     int* stack = NULL;       //栈
     int top;                 //栈顶
     int column;              //列

     stack = (int*)malloc((n + 1) * sizeof(int));
     //内存溢出处理省去
     stack[0] = n;
     top = column = 1;
     while(top > 0)
     {
          if ((top <= n) && (column <= n))
          {
               if (IsIllegal(top, column, stack))
               {
                    ++column;
               }
               else
               {
                    stack[top++] = column;
                    column = 1;
               }
          }
          else
          {
               if (top > n)
               {
                    (* Visit)(stack);
               }
               column = stack[--top];
               ++column;
          }
     }//end while

     free(stack);
     return;
}

int IsIllegal(int row, int column, const int* position)
{//判断在第row行第column列摆放皇后是否非法
     int i;

     for (i=1; i < row; ++i)
     {
          if ((position[i] == column)
               || (row - i == column - position[i])
               || (row - i == position[i] - column))
          {
               return TRUE;
          }
     }
     return FALSE;
}


测试程序还是2楼那个程序

哇,真够详细的.
八皇后我也曾研究过,下面这个程序用二维数组,似乎要快点.有个号称世界上最快的八皇后程序,我到现在还没有看懂.

#include<stdio.h>
#include<time.h>

#define N 12

void printResult(int *,int );
void Nqueen(void);


int main(void)
{
    clock_t t1,t2;

    t1=clock();
    Nqueen();
    t2=clock();
    printf("Using time : %.3f seconds\n",(float)(t2-t1)/1000);
   
    system("pause");
    return 0;
}
void Nqueen()
{
    int a[20]={0},board[20][20]={0};  //最大就算到20皇后
    register int i,j; //为了提高速度,不用白不用.//用了也几乎没有提高//重要的还是想不通的算法.
    int boardSize=N,nResult=0,n;

    n=boardSize>>1;

    for(i=0; ; )  //给i一个起点,开始吧!
    {
        while(board[a[i]][i]!=0&&a[i]<boardSize)
            ++a[i];
        if(a[i]==boardSize) //到这一列末尾
        {
            a[i]=0;
            --i;
            for(j=0;i+j<boardSize;++j)
            {
                if(a[i]-j>=0)
                    --board[a[i]-j][i+j];
                --board[a[i]][i+j];
                if(a[i]+j<boardSize)
                    --board[a[i]+j][i+j];
            }
            ++a[i];
        }
        else
        {
            if(i==boardSize-1) //在最后一列停住
            {
                //printResult(a,boardSize);
                nResult+=2;
                a[i]=0;
                --i;
                board[a[i]][i]-=3;
                board[a[i]][i+1]--;
                board[a[i]-1][i+1]--;
                board[a[i]+1][i+1]--;
                ++a[i];
            }
            else{  //此点可行,看下一列
                for(j=0;i+j<boardSize;++j)
                {
                    if(a[i]-j>=0)
                        ++board[a[i]-j][i+j];
                    ++board[a[i]][i+j];
                      if(a[i]+j<boardSize)
                          ++board[a[i]+j][i+j];
                }
                ++i;
            }
        }
        if(a[0]==n)
        {
            if((boardSize&1)==0)
                break;
            else if(a[1]>n)
                break;
        }
    }
    printf("\n\nThere are %d results.\n",nResult);
}

void printResult(int *a,int boardSize)
{
    int i;

    for(i=0;i<boardSize;++i)
        printf("%d",a[i]+1);
    printf("  ");  
    for(i=0;i<boardSize;++i) //利用对称性
        printf("%d",boardSize-a[i]);
    printf("  ");
    
}

搜索时看到过一个文章：若是只求次数的话
可以利用棋盘的旋转性和对称性，想了一下，有点复杂，因为旋转和对称有可能出现重复的情况而我不知该如何处理。这应该是大幅提高速度的方法。

我也发一个，16皇后的
#include <iostream.h>
#include <stdio.h>
//十六皇后问题
#include <math.h>

const int k = 7;
int j[k + 1] = {0};
int count;

bool valid(int i)//检验第i行的j[i]列是否合法
{
    int m;
    for(m = k; m > i; m--)
        if(j[m] == j[i] || abs(m - i) == abs(j[m] - j[i]))
            return false;//不合法
    return true;
}

void NQ(int i)
{
    if(i > 0)
    {
        for(j[i] = 0; j[i] <= k; j[i]++)
        {
            if(valid(i))
            {
                NQ(i - 1);
            }
        }
    }
    else
    {
        for(j[i] = 0; j[i] <= k; j[i]++)
        {                
            if(valid(i))
            {
                count++;
                if(count <= 8)
                {
                    int x = k;
                    for(; x >= 0; x--)
                    {
                        cout << x << "," << j[x] << "  " ;
                    }
                    cout << endl;
                }
            }
        }
    }
}

int NQence()
{
    count = 0;
    NQ(k);
    return count;
}


int main()
{
    cout << k + 1 << "皇后问题的解：" << NQence() << endl;

    getchar();

    return 0;
}

我写的这个代码更简单：
#include<iostream>
using namespace std;
const int N=5;
int count=0;
char array[N+1][N+1];

void print()
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=N;j++)
            cout<<array[i][j]<<" ";
        cout<<endl;
    }
}

bool comput(int x,int y)
{
    bool b=true;
    int i,j,c=0;
    for(i=1;i<=N;i++)if(array[x][i]=='*')c++;
    if(c>=2)b=false;c=0;
    for(i=1;i<=N;i++)if(array[i][y]=='*')c++;
    if(c>=2)b=false;c=0;

    i=x;j=y;
    while(i>=1 && j>=1)
    {
        i--;j--;
    }
    while(i<=N && j<=N)
    {
        if(array[i][j]=='*')c++;
        if(c>=2)b=false;
        i++;j++;
    }c=0;

    i=x;j=y;
    while(i>=1 && j<=N)
    {
        i--;j++;
    }
    while(i<=N && j>=1)
    {
        if(array[i][j]=='*')c++;
        if(c>=2)b=false;
        i++;j--;
    }c=0;

    return b;
}

void swap(int n,int m,int num)
{
    if(num>N){count++;cout<<"***********"<<count<<"***********\n";print();}
    for(int i=n;i<=N;i++)
    {
        for(int j=m;j<=N;j++)
        {
            if(array[i][j]=='o')
            {
                array[i][j]='*';
                if(comput(i,j)){swap(i+1,1,num+1);}
                array[i][j]='o';
            }
        }
    }
}

void main()
{
    for(int i=1;i<=N;i++)
        for(int j=1;j<=N;j++)
            array[i][j]='o';
    swap(1,1,1);
}