#include <bits/stdc++.h>

 using namespace std;

 const int MAX = ;

 const char *LINE32 = "--------------------------------";

 const bool PRINT_DETAILS = false;

 long long n, cnt = ;// n表示皇后数量，cnt表示方案数量

 int vis[][*MAX+];

 //v[0][]、v[1][]、v[2][]分别表示列、主对角线、副对角线是否存在皇后

 // 为0时表示无皇后，非0则表示有，且v[0][4]=2表示第四列第二行存在皇后 

 void print() {

     cout << LINE32 << endl;

     cout << "第" << cnt << "个方案: " << endl;

     for (int i = ; i <= n; i++) {

         if (i != ) {

             cout << ", ";

         }

         cout << "(" << vis[][i] << "," << i << ")";

     }

     cout << endl;

     for (int i = ; i <= n; i++) {

         for (int j = ; j <= n; j++) {

             if (vis[][j] != i) {

                 cout << 'x';

             } else {

                 cout << 'Q';

             }

         }

         cout << endl;

     }

 }

 bool check(int row, int col) {// 检查是否可以在（row，col）这个坐标放置皇后

     return !(vis[][col] || vis[][row-col+n] || vis[][row+col]);

 }

 void place(int x, int y, int *r2c) {// 在（x，y）的位置上放置皇后

     vis[][y] = x;

     vis[][x-y+n] = vis[][x+y] = ;

     r2c[x] = y;

 }

 void remove(int x, int y) {// 移除（x，y）位置上的皇后

     vis[][y] = vis[][x-y+n] = vis[][x+y] = ;

 }

 void solve(int n) {// 与非递归实现1的不同点在于，A.使用了vis[3][]加快了判断，B.回溯的具体操作是在vis[3][]上而不是r2c[]上

     int r2c[n+];// 存放各行所放位置的列数，其实类似于递归实现1和非递归实现1中使用的queen[]

     r2c[] = ;// 这里要初始化，否则最后要退出下面的循环时会数组越界，受影响的代码是63_42

     int row = , col = ;

     place(row, col, r2c);

     row = ;//在（1，1）的位置上放置一个皇后，然后进入循环，开始寻找第二行放置的位置

     while (row > ) {// row的值最后为0，因为所有情况都检查完时，第一行往上回溯，row值就为0

         if (row > n) {

             // 找到一个解，之后需要向上回溯：移除上一行的皇后，从上一行的下一列尝试放置皇后

             cnt++;

             if (PRINT_DETAILS) {

                 print();

             }

             row--;// row返回上一行

             remove(row, r2c[row]);// 移除上一行中的皇后

             col = r2c[row]+;// 此时的（row，col）为下一次尝试放置的位置

         } else if (col > n) {

             // 当前row行中的每一个位置都尝试并放置了，回溯

             row--;

             remove(row, r2c[row]);

             col = r2c[row]+;

         } else if (check(row, col)) {

             // 找到一个符合的位置

             place(row, col, r2c);// 放置皇后

             row++;// 查找下一行放置的位置

             col = ;// 并且是从第一列开始放置

         } else {

             // 这一列不符合，查找下一列

             col++;

         }

     }

 }

 int main() {

     // input

     cout << "输入皇后个数: ";

     cin >> n;

     // compute

     clock_t begin = clock();

     solve(n);

     clock_t end = clock();

     // output

     cout << LINE32 << endl;

     cout << n << "皇后问题一共有" << cnt << "种解决方案" << endl;

     cout << LINE32 << endl;

     cout << "回溯非递归算法实现2 解决" << n << "皇后问题耗时" << /*end-begin << "打点" <<*/(double)(end-begin)/CLOCKS_PER_SEC  << "s" << endl;

     return ;

 }

 // 14 3~5s