I can't resolve a sudoku with OptaPlanner

Question

I love constraint programming. I've been studying and modeling in other frameworks and I recently discovered OptaPlanner. I thought I had mastered it because I was able to model a few problems, even with multiple entities, but I completely lost against the Sudoku problem.

First of all, I modeled the problem with a planning entity class 'Cell', and the planning solution class '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;

    ...
}

Then, I wrote the constraints, which was perhaps the most challenging process.

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);
    }
}

At last, I created the main class, 'Sudoku', that inicialize the problem, the solver, and looks for a solution.

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);
    }

    ...
}

I tried several solver configurations: with and without construction heuristics; multiple phases, looking to divide the resolution; I made three custom moves, to change (or swap) values in an advantageous way; I let the solver run for minutes and days, I tried almost every local search algorith and I still have no feasible solution.

The best solution score I got is -2hard/0soft, but that try is not even close to the real solution. Is there anything I'm not seeing?

Thanks for the help.

Answer 1

Your implementation looks comprehensive, but debugging complex optimization problems can be challenging.

Certainly, let's consider a specific example to illustrate some of the suggestions:

Example: Adjusting Initial Solution Quality

public class Sudoku {
    public static void main(String[] args) {
        SolverConfig solverConfig = 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
}

In this example, I modified the initialization strategy using setConstructionHeuristicType. Try experimenting with different strategies like FIRST_FIT, FIRST_FIT_DECREASING, or others to observe the impact on the quality of the initial solution. Adjusting this aspect might influence the solver's ability to find better solutions during the search process. Remember to iterate and experiment with various configurations based on the specific characteristics of your problem.