Ok, in this specific case, a puzzle with what 10 pieces, a recursive backtracker will be just as fast and more importantly, be far easier to reason about and implement.
If this was a thousand piece puzzle, I would still venture recursive backtracker with good heuristics will beat CP-SAT, even in the sudoku case some good heuristics with backtracking beats CP-SAT. Not sure why Claude immediately jumped to using CP-SAT.
Would writing a recursive backtracker really be easier to reason about and implement?
With one of these solver-based approaches, you encode the problem with decision variables in some fashion, state all the constraints & call solve. There's some art & experience in how to encode & model the problem, but the specification of the model & the problem is fairly declarative.
What's great about general purpose solver-based approaches is that its usually faster (in terms of implementation time & effort) to start getting solutions & they're also much more robust to changes in requirements & the problem statement. That's less of a concern in this toy example, where the problem is small, well-defined & unambiguous, but in a real business/industrial application, the problem statement often changes considerably over time.
I agree that the performance & behaviour of a black box solver may be much harder to reason about than something you custom build by hand & know inside out, but if the general purpose black box solver is 'good enough' for the distributions of problem instances it needs to process, then there's no need to custom-build anything. Throw the black box solver at it -- job's done, and you're left with something that's both quite readable (declarative modelling of the problem, particularly if someone documents the formulation - the meaning of all the decision variables, index sets, constraints, objective terms etc) & flexible to future change.
Custom solvers & heuristics can sometimes be much, much more effective in being able to scale and solve industrial-scale problems, but usually at the expense of being much more effort to set up in the first place, and very fragile to changes in requirements -- if you learn something a few weeks into a project that perturbs the problem statement, maybe it wrecks the particular mathematical structure you were relying upon for a custom solver/heuristic, so you need to chuck out all your work & go back to the drawing board.
sashank_1509 · · focus · HN ↗
If this was a thousand piece puzzle, I would still venture recursive backtracker with good heuristics will beat CP-SAT, even in the sudoku case some good heuristics with backtracking beats CP-SAT. Not sure why Claude immediately jumped to using CP-SAT.
shoo · · focus · HN ↗
With one of these solver-based approaches, you encode the problem with decision variables in some fashion, state all the constraints & call solve. There's some art & experience in how to encode & model the problem, but the specification of the model & the problem is fairly declarative.
What's great about general purpose solver-based approaches is that its usually faster (in terms of implementation time & effort) to start getting solutions & they're also much more robust to changes in requirements & the problem statement. That's less of a concern in this toy example, where the problem is small, well-defined & unambiguous, but in a real business/industrial application, the problem statement often changes considerably over time.
I agree that the performance & behaviour of a black box solver may be much harder to reason about than something you custom build by hand & know inside out, but if the general purpose black box solver is 'good enough' for the distributions of problem instances it needs to process, then there's no need to custom-build anything. Throw the black box solver at it -- job's done, and you're left with something that's both quite readable (declarative modelling of the problem, particularly if someone documents the formulation - the meaning of all the decision variables, index sets, constraints, objective terms etc) & flexible to future change.
Custom solvers & heuristics can sometimes be much, much more effective in being able to scale and solve industrial-scale problems, but usually at the expense of being much more effort to set up in the first place, and very fragile to changes in requirements -- if you learn something a few weeks into a project that perturbs the problem statement, maybe it wrecks the particular mathematical structure you were relying upon for a custom solver/heuristic, so you need to chuck out all your work & go back to the drawing board.