You need to enable JavaScript to run this app.
优惠活动
大模型
产品
解决方案
定价
更多

SpringBoot/Java中OptaPlanner N皇后问题扩展：超量皇后未分配位置

avatar
算力阿峰
2026-7-26
超量皇后场景下的OptaPlanner N皇后问题求解错误

问题背景

我在SpringBoot/Java应用中基于OptaPlanner文档实现了N皇后问题求解，当前实现可完美处理皇后数量等于棋盘尺寸的场景，代码为参照文档自行编写，并非直接复制。现在需要扩展功能：当传入的皇后数量超过棋盘尺寸时，多余的皇后不分配位置（即rowIndex和columnIndex均为null）。目前解决方案仍在开发中，无法得到预期结果。

初始ConstraintProvider代码 

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
      }
   ]
}

可以看到，有一个皇后未被分配位置（rowIndex和columnIndex均为null），其余4个皇后在棋盘上无冲突。

修改后的ConstraintProvider代码 

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
        }
    ]
}

可以看到，第5个皇后出现了rowIndex为null但columnIndex不为null的情况，不符合预期（要么两者都有值，要么都为null）。

问题分析与解决方案

核心问题

  1. 修改后的anyPositionAssignedWithNull约束将任意一个位置为null的情况都标记为硬约束惩罚，但实际需求允许未分配皇后的两个位置都为null，该约束逻辑与需求冲突。
  2. 缺少对已分配皇后数量的限制：当皇后数量超过棋盘尺寸N时，算法会因rewardAssignedQueens的奖励逻辑试图分配更多皇后，进而出现违反约束的半分配状态。

修复方案

1. 调整非法状态约束逻辑

仅惩罚一个位置为null、另一个不为null的非法状态，允许**两个位置都为null（未分配）和两个位置都不为null（已分配）**的合法状态。

2. 添加硬约束限制已分配皇后数量

新增约束，确保已分配位置的皇后数量不超过棋盘尺寸N。

3. 优化分数模型

用硬约束处理冲突、非法分配和数量超限，用软约束奖励合法分配的皇后，确保算法优先满足硬约束，再尽可能多分配皇后。

修改后的ConstraintProvider代码示例 

public class ChessTableConstraintProvider implements ConstraintProvider {
    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[]{
                oneQueenInTheField(constraintFactory),
                rowConflict(constraintFactory),
                columnConflict(constraintFactory),
                diagonalConflict(constraintFactory),
                maxAssignedQueens(constraintFactory),
                invalidPartialAssignment(constraintFactory),
                rewardAssignedQueens(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)
                .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)
                .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)
                .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 maxAssignedQueens(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Queen.class)
                .filter(queen -> queen.getRowIndex() != null && queen.getColumnIndex() != null)
                .groupBy((queen) -> 1, ConstraintCollectors.count())
                .filter((key, count) -> count > getBoardSize(constraintFactory))
                .penalize(HardMediumSoftScore.ONE_HARD, (key, count) -> count - getBoardSize(constraintFactory))
                .asConstraint("Max assigned queens cannot exceed board size");
    }

    // 修改：仅惩罚部分位置为null的非法状态
    Constraint invalidPartialAssignment(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Queen.class)
                .filter(queen -> (queen.getRowIndex() == null && queen.getColumnIndex() != null)
                        || (queen.getRowIndex() != null && queen.getColumnIndex() == null))
                .penalize(HardMediumSoftScore.ONE_HARD)
                .asConstraint("Invalid partial assignment: one position null, the other not");
    }

    // 保留奖励逻辑，鼓励分配合法的皇后
    Constraint rewardAssignedQueens(ConstraintFactory constraintFactory) {
        return constraintFactory.forEach(Queen.class)
                .filter(queen -> queen.getRowIndex() != null && queen.getColumnIndex() != null)
                .reward(HardMediumSoftScore.ONE_SOFT)
                .asConstraint("Reward valid assigned queens");
    }

    // 从Solution对象中动态获取棋盘尺寸
    private int getBoardSize(ConstraintFactory constraintFactory) {
        // 假设你的Solution类为ChessTableSolution，包含getBoardSize方法
        return ((ChessTableSolution) constraintFactory.getSolution()).getBoardSize();
    }
}

补充说明

  • maxAssignedQueens约束通过constraintFactory.getSolution()从Solution对象中动态获取棋盘尺寸，需确保你的Solution类包含对应属性和方法。
  • 分数模型使用HardMediumSoftScore，硬约束优先级最高，确保冲突、非法状态和数量超限问题被优先解决；软约束用于奖励合法分配的皇后，让算法在满足硬约束的前提下尽可能多分配皇后。

内容的提问来源于stack exchange，提问作者jova5

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分)， 限时 9.9 元起

产品介绍相关文档
火山引擎 最新活动
全面开放
Doubao-Seedance-2.5全新模型升级

模型再升级,30秒超长叙事, 模态参考扩容

HOT
方舟Codingplan

模型自由，工具不限，最新支持 Deepseek-V4 系列、GLM-5.3 系列

HOT
方舟Agent plan

超全模态模型 × Harness 升级，最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列

HOT
新用户特惠专场

大模型19元起，Al应用9.9元畅享，新人首购爆款尽享优惠

最近更新时间：2026.07.26 18:19:53