时间戳

首页 > 解决方案 > 为 N Queen 问题 C++ 制定对角约束

c++ - 为 N Queen 问题 C++ 制定对角约束

问题描述

我遇到了 N Queens 问题。我尝试实施一个限制，即不能将皇后放在对角线上。该程序嵌入在 CPLEX 中。

这是我对列约束的最大限制。每列放置一个皇后：

    for (rr = 0; rr < ROWS; rr++)
{
    IloExpr constraint2(env);
    for (rr=0;rr<ROWS;rr++)
        constraint2 += x[rr][cc];
    mod.add(constraint2 == 1);
    constraint2.end();
}

我试图为左上角对角线实现这个：

    for (d = rr - 1; d < (ROWS - 2); d++)
{
    IloExpr constraint3(env);
    for (d = cc - 1; d < (ROWS - 2); d++)
        constraint3 += x[d][d];
    mod.add(constraint3 >= 1);
    constraint3.end();
}

但这不起作用。有人可以帮我吗？

标签： c++cplex

解决方案

在 CPLEX 中，您可以依赖 MIP。

使用 OPL，您可以编写

int Dim=400;
range Bord=1..Dim;

dvar boolean x[Bord][Bord];

subject to
{
  forall(i in Bord) sum(j in Bord) x[i][j]==1;
  forall(i in Bord) sum(j in Bord) x[j][i]==1;
  forall(k in 2..2*Dim) sum(i,j in Bord:i+j==k) x[i][j]<=1;
  forall(k in 1-Dim..Dim-1) sum(i,j in Bord:i-j==k) x[i][j]<=1;
  
}

但是在我的笔记本电脑上使用 Dim=400 需要 15 秒，而在 CPLEX 中使用 CPOptimizer 需要不到 1 秒

using CP;
int Dim=400;
range Bord=1..Dim;
dvar int queen[Bord] in Bord;
dvar int d1[Bord];
dvar int d2[Bord];

constraints {
forall(ind in Bord) {
d1[ind]== queen[ind]+ind;
d2[ind ]== queen[ind]-ind;
};

allDifferent(queen); // One queen max per line
allDifferent(d1);    // One queen max per diagonal 1
allDifferent(d2);  // One queen max per diagonal 2
};

推荐阅读