如何使用回溯法求解 M<N 时的 M 个皇后

Question

这是N queens problem。我知道 N queens 问题及其解决方案，我使用回溯方法用 C++ 编程语言编写了代码：

#include <iostream>

using namespace std;

int col[100];
int n;
int m;

bool check(int i,int k){
    for(int j=1 ; j<k ; j++){
        if(col[j] == i || i-k == col[j] - j || i+k == col[j]+j)return false;
    }
    return true;
}

void queens(int k){
    for(int i=1 ; i<=n ; i++){
        if(check(i,k)){
            col[k] = i;
            if(k == n){
                for(int j=1 ; j<=n ; j++)cout<<col[j]<<" ";
                cout<<endl;
            }
            else queens(k+1);
        }
    }
}

int main(){
    n = 4;
    queens(1);
}

但是我的问题是如果我们有 m 个皇后而不是 n 哪个 m < n 我如何用回溯方法解决这个问题我认为我的代码中的一些更改可以解决问题，但我不确定。

我在谷歌上搜索了一下，但什么也没找到，请问是否有针对此问题的回溯解决方案？

Answer 1

您可以使函数 queens 有 2 个参数：

您当前达到的列索引(num_column)
放置在 table 上的皇后数 (num_queens)

现在您必须在 [num_column, n] 之间固定一列来放置女王。设 (i, j) 为第 i 行，j 列（1 <= i <= n 和 num_column <= j <= n）。

for j from num_column to n:
    for i from 1 to n:
        if check(i, j):
            col[j] = i
            queens(j + 1, num_queens + 1)
            //resetting the queen on j'th column
            col[j] = 0

达到num_queens == m即可停止该功能。

Answer 2

答案比您想象的要简单得多！在常规 N-queen 问题中，我们迭代 k、n 次。所以我们可以在第一列的任何位置（1 到 8 之间）添加我们的第一个皇后，其他皇后依此类推。

但是如果皇后数 (m) 小于我们的国际象棋大小 (n) 我们必须将那个皇后（我们的第一个皇后）不仅放在第一列而且放在任何地方 (从 1 到 64) 并为其他皇后做同样的事情。

所以您唯一需要做的就是迭代 k、n*n 次而不是 n 次。

如何使用回溯法求解 M<N 时的 M 个皇后

How to solve M queens when M<N using backtracking approach

algorithm

backtracking

n-queens