I want to implement OptaPlanner in my SpringBoot/Java app for solving NQueen problem. Implementation that I already have is from OptaPlanner documentation and it works perfectly for exact number of queens necessary for chess board, it is not copied from documentation, I used documentation instruction to make my own solution.
Now I want to make a solution so that when I pass more queens than necessary, excess queen/queens will not be assigned position.
My solution is available here on github. It is still work in progress because I could not get result similar to result mentioned bellow.
This is code for managing queens on chess board filed (functionality for excess and non excess queens),
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");
}
}
Example result for chess board size 4x4, number of queens 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
}
]
}
As you can see, one queen is not assigned to position.
My environment: Laptop: Dell Vostro 5625 OS: Win11 Processor: Ryzen 7 5xxx Ram: 32GB
I thank everyone for their time.
Edit 1, solution:
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");
}
}
Now I get this result:
{
"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
}
]
}
What you're looking for is called over-constrained planning. You need to tell the solver that it is OK not to assign some entities.