N皇后问题

[编程题]N皇后问题

热度指数：39979 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

N 皇后问题是指在 n * n 的棋盘上要摆 n 个皇后，
要求：任何两个皇后不同行，不同列也不在同一条斜线上，
求给一个整数 n ，返回 n 皇后的摆法数。

数据范围: $1 \le n \le 9$

要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n!)$

例如当输入4时，对应的返回值为2，

对应的两种四皇后摆位如下图所示：

示例1

输入

输出

示例2

输入

输出

算法知识视频讲解

牛客519059190号

bool isLegal(int n, int* POS, int k) { //判断第k行是否合法
    for (int row = 0; row < k; row++)
        if (POS[k] == POS[row] || POS[k] == POS[row] - (row - k) || POS[k] == POS[row] + (row - k))
            return false;
    return true;
}
int TotalCase(int n, int* POS, int k) { //返回0~k-1行给定时的可能数
    if (k == n)
        return 1;
    int ans = 0;
    for (int i = 0; i < n; i++) {
        POS[k] = i;
        if (isLegal(n, POS, k))
            ans += TotalCase(n, POS, k + 1);
    }
    return ans;
}
int Nqueen(int n ) {
    int POS[n]; // POS[k]表示第k行的皇后所在列数
    return TotalCase(n, POS, 0);
}

发表于 2022-10-06 19:01:39 回复(0)

16226

怎么有人玩赖的阿

发表于 2022-07-09 11:21:30 回复(0)

勇敢牛牛，不怕困难！

int available(int n, int x, int y, int cols, int diag1, int diag2) {
  return !(cols & 1 << x || diag1 & 1 << (x + y) || diag2 & 1 << (n - 1 + x - y));
}

void dfs(int n, int y, int cols, int diag1, int diag2, int* ans) {
  if (y > n) {
    ++(*ans);
    return;
  }
  for (int x = 1; x <= n; ++x) {
    if (!available(n, x, y, cols, diag1, diag2)) continue;
    
    cols  |= 1 << x;
    diag1 |= 1 << (x + y);
    diag2 |= 1 << (n - 1 + x - y);
    
    dfs(n, y + 1, cols, diag1, diag2, ans);
    
    cols  -= 1 << x;
    diag1 -= 1 << (x + y);
    diag2 -= 1 << (n - 1 + x - y);
  }
}

int Nqueen(int n) {
  int ans = 0, cols = 0, diag1 = 0, diag2 = 0;
  dfs(n, 1, cols, diag1, diag2, &ans);
  return ans;
}

发表于 2021-08-12 12:29:39 回复(0)