int  x[SIZE];   // 某一行上皇后的放置位置
int  up_free[2*SIZE-1]; // 斜列是否空闲
int  down_free[2*SIZE-1];// 斜行是否空闲
int  col_free[SIZE];  // 列是否空闲

// 求解（国际象棋）皇后问题
// i － 当前的行号
// n － 总的皇后数
void Queen(int n)
{
 int   i, j;
 Stack st;
 Element elem;

 InitStack(&st);
 
 // 初始位置入栈
 elem.x = 0;
 elem.y = -1; 
 Push(&st, elem);
 
 while(!IsStackEmpty(st))
 {
  Pop(&st, &elem); // 弹出上一行的皇后位置
  i = elem.x;
  j = elem.y;
  /* 恢复原状 */
  if(j != -1)
  {
   x[i] = 0;
   col_free[j] = TRUE;
   up_free[i+j] = TRUE; /* 向上的斜列 */
   down_free[i-j+n-1] = TRUE; /* 向下的斜列 */     
  } 
  
  // 考察第i行所有列
  for(j=elem.y+1; j<n; j++)
  {
   if(IsLegal(i, j, n))
   {
    // 如果可以放在当前位置
    // 则设置当前位置的状态
    x[i] = j;
    col_free[j] = FALSE; /* 第j列 */
    up_free[i+j] = FALSE; /* 向上的斜列 */
    down_free[i-j+n-1] = FALSE; /* 向下的斜列 */
    // 当前位置入栈
    elem.x = i;
    elem.y = j;
    Push(&st, elem);
    // 进入下一行，并且进入下一行时
    // 列的初始位置应为0
    ++i;
    j = -1; 

    if(i >= n)
    {
     ++nTotal;
     Output(n, nTotal);
    }
   } 
  }
 } 
 
 DestroyStack(&st);
} 

// n－皇后个数
int IsLegal(int i, int j, int n)
{
 return col_free[j] && up_free[i+j]
   && down_free[i-j+n-1];
} 

评论