我无法使用 OptaPlanner 解决数独问题

Question

我喜欢约束编程。我一直在其他框架中进行研究和建模，最近发现了 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，但该尝试与真正的解决方案相差甚远。 有什么我没看到的吗？

感谢您的帮助。

Answer 1

您的实现看起来很全面，但调试复杂的优化问题可能具有挑战性。

当然，让我们考虑一个具体的例子来说明一些建议：

示例：调整初始解决方案质量

公开课数独{ 公共静态无效主（字符串[] args）{ SolverConfigsolverConfig = SolverConfig.createFromXmlResource("scheduleSolverConfig.xml") .withSolutionClass(Board.class) .withEntityClasses(Cell.class) .withConstraintProviderClass(SudokuConstraintProvider.class);

    // Experiment with different initialization strategies
    solverConfig.setConstructionHeuristicType(ConstructionHeuristicType.FIRST_FIT);

    // Rest of your code remains unchanged
    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));
}

// Rest of your Sudoku class remains unchanged

}

在这个例子中，我使用setConstructionHeuristicType修改了初始化策略。尝试尝试不同的策略，例如 FIRST_FIT、FIRST_FIT_DECREASING 或其他策略，以观察对初始解决方案质量的影响。调整这方面可能会影响求解器在搜索过程中找到更好解决方案的能力。请记住根据问题的具体特征迭代和试验各种配置。