我想在我的 SpringBoot/Java 应用程序中实现 OptaPlanner 来解决 NQueen 问题。我已经拥有的实现来自 OptaPlanner 文档，它非常适合棋盘所需的确切皇后数量，它不是从文档中复制的，我使用文档说明来制作我自己的解决方案。
现在我想做一个解决方案，当我通过超过必要的皇后时，多余的皇后/皇后将不会被分配位置。
我的解决方案在这里在github上可用。它仍在进行中，因为我无法获得类似于下面提到的结果的结果。
这是在棋盘上管理皇后的代码（多余和非多余皇后的功能），
public class ChessTableConstraintProvider implements ConstraintProvider {
@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
return new Constraint[]{oneQueenInTheField(constraintFactory), rowConflict(constraintFactory),
columnConflict(constraintFactory), diagonalConflict(constraintFactory),
onePositionNotNullOtherNull(constraintFactory), positionNotNull(constraintFactory)};
}
Constraint oneQueenInTheField(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.equal(Queen::getRowIndex),
Joiners.equal(Queen::getColumnIndex), Joiners.lessThan(Queen::getId))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("One queen at most in the field");
}
Constraint rowConflict(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.equal(Queen::getRowIndex), Joiners.lessThan(Queen::getId))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Queens on same row");
}
Constraint columnConflict(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.equal(Queen::getColumnIndex), Joiners.lessThan(Queen::getId))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Queens on same column");
}
Constraint diagonalConflict(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.lessThan(Queen::getId))
.filter((queen1, queen2) -> queen1.getRowIndex() != null &&
queen1.getColumnIndex() != null &&
queen2.getRowIndex() != null &&
queen2.getColumnIndex() != null)
.filter((queen1, queen2) -> Math.abs(queen1.getRowIndex() - queen2.getRowIndex()) ==
Math.abs(queen1.getColumnIndex() - queen2.getColumnIndex()))
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Queens on same diagonal");
}
Constraint positionNotNull(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.filter(queen -> queen.getRowIndex() == null && queen.getColumnIndex() == null)
.penalize(HardSoftScore.ONE_HARD)
.asConstraint("Position must not be null");
}
Constraint onePositionNotNullOtherNull(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class).filter(queen -> {
if (queen.getColumnIndex() == null && queen.getRowIndex() == null) {
return false;
}
return queen.getRowIndex() == null || queen.getColumnIndex() == null;
}).penalize(HardSoftScore.ONE_HARD).asConstraint("Only one position is null");
}
}
棋盘大小为 4x4，皇后数为 5 的示例结果：
{
"queenList":[
{
"id":0,
"columnIndex":null,
"rowIndex":null
},
{
"id":1,
"columnIndex":2,
"rowIndex":0
},
{
"id":2,
"columnIndex":0,
"rowIndex":1
},
{
"id":3,
"columnIndex":3,
"rowIndex":2
},
{
"id":4,
"columnIndex":1,
"rowIndex":3
}
]
}
如你所见，一位皇后没有分配到位置。
我的环境： 笔记本电脑：戴尔 Vostro 5625 操作系统：Win11 处理器：锐龙 7 5xxx 内存：32GB
我感谢大家的时间。
编辑1，解决方案：
public class ChessTableConstraintProvider implements ConstraintProvider {
@Override
public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
return new Constraint[]{oneQueenInTheField(constraintFactory), rowConflict(constraintFactory),
columnConflict(constraintFactory), diagonalConflict(constraintFactory),
rewardAssignedQueens(constraintFactory), anyPositionAssignedWithNull(constraintFactory)};
}
Constraint oneQueenInTheField(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.equal(Queen::getRowIndex),
Joiners.equal(Queen::getColumnIndex), Joiners.lessThan(Queen::getId))
.filter((queen1, queen2) -> queen1.getRowIndex() != null &&
queen1.getColumnIndex() != null &&
queen2.getRowIndex() != null &&
queen2.getColumnIndex() != null)
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("One queen at most in the field");
}
Constraint rowConflict(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.equal(Queen::getRowIndex), Joiners.lessThan(Queen::getId))
.filter((queen, queen2) -> queen.getRowIndex() != null && queen2.getRowIndex() != null)
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Queens on same row");
}
Constraint columnConflict(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.equal(Queen::getColumnIndex), Joiners.lessThan(Queen::getId))
.filter((queen, queen2) -> queen.getColumnIndex() != null &&
queen2.getColumnIndex() != null)
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Queens on same column");
}
Constraint diagonalConflict(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.join(Queen.class, Joiners.lessThan(Queen::getId))
.filter((queen1, queen2) -> queen1.getRowIndex() != null &&
queen1.getColumnIndex() != null &&
queen2.getRowIndex() != null &&
queen2.getColumnIndex() != null)
.filter((queen1, queen2) -> Math.abs(queen1.getRowIndex() - queen2.getRowIndex()) ==
Math.abs(queen1.getColumnIndex() - queen2.getColumnIndex()))
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Queens on same diagonal");
}
Constraint rewardAssignedQueens(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.filter((queen1) -> queen1.getRowIndex() != null && queen1.getColumnIndex() != null)
.reward(HardMediumSoftScore.ONE_MEDIUM)
.asConstraint("Reward Assigned Queens");
}
Constraint anyPositionAssignedWithNull(ConstraintFactory constraintFactory) {
return constraintFactory.forEach(Queen.class)
.filter(queen -> queen.getRowIndex() == null || queen.getColumnIndex() == null)
.penalize(HardMediumSoftScore.ONE_HARD)
.asConstraint("Any Position Assigned With Null");
}
}
现在我得到这个结果：
{
"queenList": [
{
"id": 0,
"rowIndex": 1,
"columnIndex": 3
},
{
"id": 1,
"rowIndex": 3,
"columnIndex": 2
},
{
"id": 2,
"rowIndex": 0,
"columnIndex": 1
},
{
"id": 3,
"rowIndex": 2,
"columnIndex": 0
},
{
"id": 4,
"rowIndex": null,
"columnIndex": 2
}
]
}
你要找的是过度约束规划。 您需要告诉求解器可以不分配某些实体。