#include <iostream>using namespace std; #define N 4 char board[N][N];int col[N];               //存储第i行对应的列的值，这样的(i,j)值满足当前棋盘上的皇后不能互相攻击。 bool safetyPlace(int x,int y)  //(x,y)位置是否安全{     for (int i = 0; i < x; i++)     {         int j = col[i];                  if (x == i || y == j)return false;     //同一行或同一列                  if (x-y == i-j || x+y == i+j)return false;  //左，右对角线     }     return true;} void queen(int i)    //处在第i行时状态{     if (i == N)           //输出棋盘       {for (int w = 0;w < N; w++)           {              cout << "--------------" << endl;              for (int j = 0; j < N; j++)                cout << '|' << " " << board[w][j];              cout << '|' << endl;           }        cout << endl;      }     else     {         int u;         for (u = 0; u < N; u++)         {            if (safetyPlace(i,u) == true)           {               col[i] = u;           //记录下第i行可行的列的位置                     arr[i][u] = 'Q';    //放置皇后               queen(i+1);    //转换到下一个状态，即下一行               col[i] = 0;        //回溯到当前状态，重置列和棋盘的值               board[i][u] = 0;           }         }     }}int main(){    queen(0);    system("pause");    return 0;}    不足之处多多指教。：）   解决了N皇后问题，又想了想， 原来树的前序，后序，中序递归遍历也是回溯法的应用。恩，确实让人觉得很 兴奋。对于回溯法的理解，让我一下子觉得豁然开朗了，迷宫，马踏棋盘等等，都可以试着去解决了。。。 以前虽然写过迷宫，用的也是回溯法，只不过不是递归法，方法现在觉得好不流畅。。。看来，还是递归让人觉得 舒服，代码易懂。。

评论