皇后问题（回溯法初学推荐）-向日葵屋

皇后问题（回溯法初学推荐）

水深无声 2023-07-13 15:10 3阅读 0赞

皇后问题

First question：八皇后问题
在棋盘上放置8个皇后，使得它们互不攻击，此时每个皇后的攻击范围为同行同列和同对角线，要求找出所有解，如图所示。
皇后攻击范围
先上代码：

#include<bits/stdc++.h>
using namespace std;
int tot=0, n, C[5];
void search(int cur)
{ 
  if(cur==n) 
  { 
      tot++;
      return;
  }
  //每行每列只有一个皇后 
  for(int i=0; i<n; i++)
  { 
      int ok=1;
      C[cur]=i;    //尝试把第cur行的皇后放在第i列 C[y]=x
      for(int j=0; j<cur; j++)    //检查是否和前面的皇后冲突 
      {         //检查纵向 检查斜向 巧妙 
              //不用检查横向，因为皇后是逐行放置
          if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j])
          {                  //y-x x+y
              ok=0;
              break;
          }
      }
      if(ok)
      search(cur+1);    //如果合法，则继续递归 
  }
}
int main()
{ 
  n=5;
  search(0);
  cout<<tot<<endl;
  return 0;
}

注意：皇后是逐行放置的，皇后肯定不会横向攻击（因为横向不可能有皇后），因此只需检查是否纵向和斜向攻击即可。
条件“cur-C[cur]==j-C[j] || cur+C[cur]==j+C[j]”用来判断皇后（cur,C[cur]）和（j,C[j]）是否在同一条对角线上。
（神秘的操作）其原理可以用下图解释。

（a）格子（x,y）的y-x值标识了主对角线

（b）格子（x,y）的x+y值标识了副对角线
在“八皇后”代码中并没有用到回溯的方法，但是我们可以模仿“八皇后”的代码，写出接下来的这道题——2n皇后问题

Second question：2n皇后问题
问题描述
　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
输入格式
　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。
输出格式
　　输出一个整数，表示总共有多少种放法。

样例输入
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
样例输出
2

我采用的方法是用一个类似棋盘的二维数组qp[10][10]来模拟全局的状态。在棋盘上，任意同色的皇后任都不在同一行、同一列或同一条对角线上。
换句话说，黑白皇后之间没有影响，要考虑2个问题：
1、该位置有没有被占或不能下？
2、会不会与同色皇后冲突？
如果你有做过八皇后的题目，那你可以直接套用在这个2n皇后的题目，只要添加回溯即可。

如何添加回溯？
想象一下，你要下一步棋，现在你有很多个下棋位置可以选择。
第一种情况：你下了几步后发现输了，你想悔棋。于是你就把棋局回到你一开始要下的棋局，选择其他可能赢的下棋位置。
第二种情况：你下了几步后发现赢了，你获胜的可能多了一种，但是你觉得赢的方式有很多种。于是你就把棋局回到你一开始要下的棋局，选择其他可能赢的下棋位置。

#include<bits/stdc++.h>
using namespace std;
long long tot=0, n, tot1=0;
int C[10], C1[10], qp[10][10];
void black(int cur)
{ 
    if(cur==n) //放好黑皇后、白皇后 
    { 
        tot++;
        return;
    }
    for(int i=0; i<n; i++)
    { 
        int ok=1, j;
        C1[cur]=i;
        for(j=0; j<cur; j++)
        { 
            if(C1[cur]==C1[j]||cur-C1[cur]==j-C1[j]||cur+C1[cur]==j+C1[j])
            {         
                ok=0;
                break;
            }
        }
        if(ok&&qp[cur][i]==1)
        { 
            qp[cur][i]=2;
            black(cur+1);    
            qp[cur][i]=1;
        }
    }
}
void white(int cur)
{ 
    if(cur==n)     //白皇后放置完毕 
    { 
        black(0);//开始放黑皇后 
        for(int i=0; i<n; i++)
        cout<<C[i]<<" ";
        return;
    }
    for(int i=0; i<n; i++)
    { 
        int ok=1, j;
        C[cur]=i;    //尝试把第cur行的皇后放在第i列 （对应讲解图C[y]=x） 
        for(j=0; j<cur; j++)
        { 
            //不得不说这里的一维数组用得很巧妙，甚至有点神秘
            //判断同列有没有同色皇后、斜边有没有同色皇后
            //由于该判断有点抽象，具体请看上面原理图 
            if(C[cur]==C[j]||cur-C[cur]==j-C[j]||cur+C[cur]==j+C[j])
            {         
                ok=0;
                break;
            }
        }
        if(ok&&qp[cur][i]==1)//判断该位置是否符合条件、是否为空 
        { 
            qp[cur][i]=2;
            white(cur+1);    
            qp[cur][i]=1;    //回溯： 
        }                    //想象一下，你要下一步棋，现在你有很多个选择 
    }                        //你下了几步后发现输了，你想悔棋 
}                            //于是你就把棋局回到你一开始要下的棋局 
                            //选择其他可能赢的选择 
int main()
{ 
    cin>>n;
    for(int i=0; i<n; i++)
    for(int j=0; j<n; j++)
    cin>>qp[i][j];
    white(0);        //先放白皇后 
    cout<<tot<<endl;
    return 0;
}