棋盘挑战

原题链接

思路：

• 使用 DFS 深度优先搜索。
  • 注意棋盘的每一行、每一列，以及棋子所在的对角线的平行线上，都只能有一个棋子。
  • 采用递归处理，每一层递归对应棋盘的一行（即递归的深度对应棋盘的行数），每层只放置一个棋子。
  • 对于递归的每一行，遍历该行的所有格子，判断该格子所在的列及两条对角线上是否已有棋子：
    • 若没有棋子，则直接放置，标记并递归进入下一层，这种方法可以保证得到最小字典序的方案。
    • 放置棋子后，需要对所在列及两条对角线进行标记。
  • 递归处理上述过程，直到所有棋子放置完毕，记录 res 为方案总数。当 res <= 3 时，输出当前方案。
  • 对于对角线的处理，利用数学关系，将对角线的判断转换为对截距的判断，即所有已放置棋子的截距必须各不相同。截距可以通过公式 k = i + u 或 k = i - u 得到。此外，由于 i - u 可能为负数，因此考虑增加偏移量 k = i - u + n 来保证下标合法。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 110;

bool y[N], l[N], r[N];

int n, res;

int ans[N];

void dfs(int u){
    if(u == n){  // 说明放满了棋子
        res ++;  // 记录答案 res + 1
        if(res <= 3){  // res <= 3 输出方案
           for(int i = 0; i < n; i ++) cout << ans[i] << ' ';
           cout << endl;
        }
        return ;
    }

for(int i = 0; i < n; i ++){
        if(!y[i] && !l[u + n + i] && !r[u + n - i]){
            y[i] = l[u + n + i] = r[u + n - i] = 1;  // 标记
            ans[u] = i + 1;  // 存入答案数组
            dfs(u + 1);  // 递归到下一层
            y[i] = l[u + n + i] = r[u + n - i] = 0;  // 恢复现场
        }
    }
}

void solve(){
    cin >> n;
    dfs(0);
    cout << res << endl;
}

int main(){
    solve();
    return 0;
}