OptaPlanner数独求解失败，请求技术排查指导

我热爱约束编程，此前在其他框架中学习建模，近期接触OptaPlanner。本以为已掌握其用法——能完成多实体问题建模，但在数独问题上遭遇瓶颈。

我首先将问题建模为规划实体类Cell与规划解决方案类Board，代码如下：

@PlanningEntity
public class Cell {
    @PlanningId
    private Long id;
    private Long row;
    private Long column;
    private Long block;
    @PlanningVariable(valueRangeProviderRefs = "cellsRange")
    private Long value;
    @PlanningPin
    private boolean pinned;

    ...
}

@PlanningSolution
public class Board {
    @PlanningEntityCollectionProperty
    private List<Cell> cells;
    @ProblemFactCollectionProperty
    @ValueRangeProvider(id = "cellsRange")
    private List<Long> numbers;
    @PlanningScore
    private HardSoftScore score;

    ...
}

随后编写约束条件，这也是最具挑战性的环节，代码如下：

public class SudokuConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[] {
            correctRows(constraintFactory),
            correctColumns(constraintFactory),
            conflictingCellsInBlock(constraintFactory)
        };
    }

    Constraint conflictingCellsInBlock(ConstraintFactory constraintFactory) {
        return constraintFactory
            .forEachUniquePair(Cell.class, Joiners.equal(Cell::getBlock))
            .filter((c1, c2) -> c1.getValue() == c2.getValue() && c1.getId() != c2.getId())
            .penalize("Value is repeated in the block", HardSoftScore.ONE_HARD);
    }

    Constraint correctRows(ConstraintFactory constraintFactory) {
        return constraintFactory
            .forEachUniquePair(Cell.class, Joiners.equal(Cell::getRow))
            .filter((c1,c2) -> c1.getValue() == c2.getValue() && c1.getId() != c2.getId())
            .penalize("Conflicting value in row", HardSoftScore.ONE_HARD);
    }

    Constraint correctColumns(ConstraintFactory constraintFactory) {
        return constraintFactory
            .forEachUniquePair(Cell.class, Joiners.equal(Cell::getColumn))
            .filter((c1,c2) -> c1.getValue() == c2.getValue() && c1.getId() != c2.getId())
            .penalize("Conflicting value in column", HardSoftScore.ONE_HARD);
    }
}

最后创建主类Sudoku，用于初始化问题、求解器并寻找解，代码如下：

public class Sudoku {
    public static void main(String[] args) {
        SolverConfig solverConfig = SolverConfig.createFromXmlResource("scheduleSolverConfig.xml")
            .withSolutionClass(Board.class)
            .withEntityClasses(Cell.class)
            .withConstraintProviderClass(SudokuConstraintProvider.class);

        SolverFactory<Board> solverFactory = SolverFactory.create(solverConfig);
        Solver<Board> solver = solverFactory.buildSolver();

        Board solution = solver.solve(generateBoard());
        printSudokuBoard(solution);

        ScoreManager<Board, HardSoftScore> scoreManager = ScoreManager.create(solverFactory);
        System.out.println(scoreManager.explainScore(solution));
    }

    public static Board generateBoard() {
        Long[][] customProblem = {
            {8L, 0L, 0L, 0L, 0L, 0L, 0L, 0L, 0L},
            {0L, 0L, 3L, 6L, 0L, 0L, 0L, 0L, 0L},
            {0L, 7L, 0L, 0L, 9L, 0L, 2L, 0L, 0L},
            {0L, 5L, 0L, 0L, 0L, 7L, 0L, 0L, 0L},
            {0L, 0L, 0L, 0L, 4L, 5L, 7L, 0L, 0L},
            {0L, 0L, 0L, 1L, 0L, 0L, 0L, 3L, 0L},
            {0L, 0L, 1L, 0L, 0L, 0L, 0L, 6L, 8L},
            {0L, 0L, 8L, 5L, 0L, 0L, 0L, 1L, 0L},
            {0L, 9L, 0L, 0L, 0L, 0L, 4L, 0L, 0L}
        };

        List<Cell> cells = new ArrayList<>();
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                int blockCol = j/3;
                int blockRow = i/3;
                Long blockId = (long) (blockRow * 10 + blockCol);
                if (customProblem[i][j] != 0L) {
                    cells.add(new Cell((long) i + 1 + j * 9, (long) i, (long) j, customProblem[i][j], blockId,  true));
                } else {
                    cells.add(new Cell((long) i + 1 + j * 9, (long) i, (long) j, customProblem[i][j], blockId,  false));
                }
            }
        }

        Long[] n = {1L,2L,3L,4L,5L,6L,7L,8L,9L};
        List<Long> numbers = new ArrayList<>(List.of(n));
        return new Board(cells, numbers);
    }

    ...
}

我尝试了多种求解器配置：有无构造启发式算法、多阶段拆分求解、自定义三种移动策略、长时间运行求解器、几乎所有局部搜索算法，但始终无法得到可行解。目前最佳解得分为-2hard/0soft，与正确解相去甚远。请问是否存在我忽略的问题？

1. 初始值设置错误 #

在generateBoard方法中，未填的单元格（值为0的）被设置value = 0L，但你的cellsRange只包含1-9的数字。OptaPlanner的规划变量初始值必须属于其值域，否则会直接导致硬约束违反，而且后续求解可能无法正确替换这个非法值。

修复方案：将未填单元格的value设为null，而非0。OptaPlanner要求规划变量在未初始化时应为null，构造启发式会自动为其分配合法初始值。

修改generateBoard中的对应代码：

if (customProblem[i][j] != 0L) {
    cells.add(new Cell((long) i + 1 + j * 9, (long) i, (long) j, customProblem[i][j], blockId,  true));
} else {
    cells.add(new Cell((long) i + 1 + j * 9, (long) i, (long) j, null, blockId,  false));
}

2. 约束条件的重复惩罚与类型比较问题 #

当前的forEachUniquePair会对每一对冲突单元格进行两次惩罚（比如c1和c2、c2和c1都会被计数），同时用==比较Long类型值可能因对象引用不同导致判断错误。

优化约束示例：

Constraint conflictingCellsInBlock(ConstraintFactory constraintFactory) {
    return constraintFactory
        .forEachUniquePair(Cell.class, 
            Joiners.equal(Cell::getBlock),
            Joiners.lessThan(Cell::getId)) // 避免重复计数
        .filter((c1, c2) -> Objects.equals(c1.getValue(), c2.getValue()))
        .penalize("Value is repeated in the block", HardSoftScore.ONE_HARD);
}

对行、列约束做同样修改，用Objects.equals替代==，避免Long类型拆箱比较的潜在问题。

3. 求解器配置优化 #

• 构造启发式：必须启用构造启发式，推荐使用REGRET_MATCH或FIRST_FIT_DECREASING，快速生成接近可行的初始解，避免局部搜索从大量硬约束违反的状态起步。
• 局部搜索算法：数独适合用TABU_SEARCH或SIMULATED_ANNEALING，尤其是TABU_SEARCH能有效避免陷入局部最优。同时确保移动策略包含ChangeMove（修改单个单元格值）和SwapMove（交换两个单元格值），覆盖更多搜索空间。
• 终止条件：设置合理的终止时间，比如termination.spentLimit=30s，给求解器足够时间找到可行解。

4. 规划变量的nullable配置 #

显式声明@PlanningVariable的nullable = true（OptaPlanner 8+默认值，但显式声明更稳妥），允许变量初始为null，确保构造启发式正确初始化：

@PlanningVariable(valueRangeProviderRefs = "cellsRange", nullable = true)
private Long value;

内容的提问来源于stack exchange，提问作者Agustín Cano