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.
I would be shocked if a good recursive backtracker could beat a good SAT solver for large problems. I mean, if you could solve SAT with recursive backtracking people would. That is the core of a SAT or CP solver, with the all the extra clever stuff.
I've spent significant chunks of my career help people throw away backtracking searchers people polished over years with a CP-SAT model I threw together in 30 minutes, often much to their upset.
You can for Sudoku often beat a CP-SAT solver, but that's because the problems are trivial and take milliseconds. If you look at more difficult Sudoku variants, or 16x16 grids, backtracking solvers start to fall behind.
I'm new to solvers and have only used them in anger exactly once, but during my research it seemed that the received wisdom is that hand-rolled solutions were typically faster, so this is a surprise to me. I suppose in the same sense that 'you can write assembly better than the compiler if you really want', which is probably also mostly false these days.
Do you have examples that are public or that you can talk about?
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.
CJefferson · · focus · HN ↗
I've spent significant chunks of my career help people throw away backtracking searchers people polished over years with a CP-SAT model I threw together in 30 minutes, often much to their upset.
You can for Sudoku often beat a CP-SAT solver, but that's because the problems are trivial and take milliseconds. If you look at more difficult Sudoku variants, or 16x16 grids, backtracking solvers start to fall behind.
anitil · · focus · HN ↗
Do you have examples that are public or that you can talk about?