n皇后问题

方法1：递归

回溯法，效率极低

#include <iostream>
#include <cstring>

using namespace std;

void dfs(int row);

int n,sum=0;
int sol[100];

int main() {
    cin>>n;
    memset(sol,0,sizeof(sol));
    dfs(0);
    cout<<sum<<endl;
    return 0;
}

void dfs(int row){
    for (int col=0;col<n;col++){
        bool ok = true;
        for (int i=0;i<row;i++) {
            if (col==sol[i]||col-sol[i]==row-i||sol[i]-col==row-i){
                ok = false;
                break;
            }
        }
        if(ok){
            sol[row] = col;
            if(row==n-1){
                sum++;
            }
            else{
                dfs(row+1);
            }
        }
    }
}

本行不能摆放皇后的条件：

1. 与上面任意行的皇后处在同一列上

   col==sol[i]

2. 与上面任意行的皇后处在任意“撇（从右上到左下的对角线）“上

   sol[i]-col==row-i   
   //上面第i行皇后所在列-本行皇后所在列 == 本行行数-第i行行数
   /*
   由于在棋盘的斜线处，所以两点若处于同一条斜线上，那么这两点横坐标相减
   的绝对值一定等于纵坐标相减的绝对值。由于是右上到左下，所以sol[i]-col
   为正值。
   */

3. 与上面任意行的皇后处在任意“捺（从左上到右下的对角线）“上

   col-sol[i]==row-i
   //由于是左上到右下，所以col-sol[i]为正值。

sol[i]数组存储第i行的皇后摆放在第几列。

方法二：改进递归

删去遍历sol[]数组，改为直接表示出与列、撇、捺是否有有皇后直接有关的数组。检查冲突的时间复杂度由方法一的O(n)变为O(1)了。

#include <iostream>
#include <cstring>

using namespace std;

void dfs(int row);

int n,sum=0;
bool shu[100],pie[199],na[199];

int main() {
    cin>>n;
    memset(shu,0, sizeof(shu));
    memset(pie,0, sizeof(pie));
    memset(na,0, sizeof(na));
    dfs(0);
    cout<<sum<<endl;
    return 0;
}

void dfs(int row){
    for (int col=0;col<n;col++){
        if((shu[col] || pie[col+row] || na[n-row+col-1]) == true){
            continue;
        }
        if(row==n-1){
            sum++;
        }
        else{
            shu[col]=true;
            pie[col+row]=true;
            na[n-row+col-1]=true;
            dfs(row+1);
            shu[col]=false;
            pie[col+row]=false;
            na[n-row+col-1]=false;
        }
    }
}

可以画图，找规律推导出这个式子。

方法三：用位运算，省空间

思想：用一个32位整数代替一个长度为32的布尔数组

基本运算：

• 与：5 & 6 = 4 (101&110=100)

• 或：5 | 6 = 7 (101|110=111)

• 异或：5 ^ 6 = 3 (101^110=011)

• 取反：~5 = -6 (~00000101=11111010)

• 左移：5 << 2 = 20 (101<<2=10100)

• 右移：5 >> 2 = 1 (101>>2=1)

模拟数组操作（bit array）：

• 把第i位置1：a |= (1<<i)

• 把第i位置0：a &= ~(1<<i)

• 把第i位取反：a ^= (1<<i)

• 读取第i位的值：(a>>i) & 1

#include <iostream>
#include <cstring>

using namespace std;

void dfs(int row);

int n,sum=0;
int shu,pie,na;   //数组变成int变量

int main() {
    cin>>n;
    dfs(0);
    cout<<sum<<endl;
    return 0;
}

void dfs(int row){
    for (int col=0;col<n;col++){
        int j = col+row;
        int k = n-row+col-1;
        if((((shu>>col)|(pie>>j)|(na>>k))&1)!=0){  //位运算
        //或将!=0改为==1
            continue;
        }
        if(row==n-1){
            sum++;
        }
        else{
            shu^=(1<<col);
            pie^=(1<<j);
            na^=(1<<k);

            dfs(row+1);
            
            shu^=(1<<col);
            pie^=(1<<j);
            na^=(1<<k);
        }
    }
}