Rendered at 03:02:36 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
JoeAltmaier 5 hours ago [-]
Back in the day BYTE magazine had a puzzle contest - solve the 8-queens problem and find all the solutions.
As a kid, it seemed obvious to me that a good model was the digits 1 through 8, representing the row that a queen would be in. Doing a recursive backtracker on an ordering of the digits and testing each pair for diagonal (digit i minus digit j was equal to +/- i-j) and my BASIC program spit out the solutions in twenty minutes.
I didnt enter the contest because I figured everybody would do that. Turns out when the editor published the 'best' solutions, they all, every single one, modeled the board as an 8 by 8 array and ran around following diagonals iteratively. And took hours to complete.
Anyway, choosing a good solution model is most of the problem solved.
anitil 3 hours ago [-]
That's very cool. I don't quite understand your solution, are you saying that because you used the i:j relationship as a constant it meant you only needed to store positions rather than a whole board? I've never been interested in 8-queens but I'm keen to play with it now
IceDane 4 hours ago [-]
Can you tell us more stories about how much smarter you were than everyone else as a kid?
sashank_1509 1 days ago [-]
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.
CJefferson 1 days ago [-]
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.
taeric 1 days ago [-]
Agreed. I don't know if I would be shocked, but I would be surprised.
This is one that is hard for people to really internalize, I think? The SAT solvers many are likely to use today are not at all the same as the ones they would have used 20 years ago. They have made some amazing advances in how to approach those problems.
There are also probably some very poorly conceived models that people use to adapt a problem to some of these solvers.
anitil 3 hours ago [-]
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?
shoo 4 hours ago [-]
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.
emil-lp 1 days ago [-]
CP here being Constraint Problem, or CSP (Constraint Satisfaction Problem).
Reinventing the wheel is not always to be avoided. Finding an interesting wheel and trying to build your own equivalent can be an excellent way to improve your skills as a programmer [1].
"Feed it to SAT solver" is a super useful technique every seasoned programmer should have in their toolbelt.
If you want to improve your programming skill, I suggest implementing your own version of these two interesting, satisfying algorithms:
- DPLL, the classic general-purpose SAT solving algorithm [3].
- Algorithm X (aka Dancing Links), Knuth's super elegant search algorithm for solving exact cover problems [4] [5].
You're not going to build something that beats CaDiCaL [6] in an afternoon, but writing your own implementation of these algorithms will teach you a lot, and a reasonable time investment will get you to a pretty satisfying endpoint of having a practical solver for your favorite application (Sudoku, polyomino packing, etc.)
[1] Reinventing wheels is not a bad way to spend your days at a retreat focusing on one's personal growth as a programmer. "I think I'll learn a lot and get some good practice at programming and algorithmic thinking" is an easy bar to meet.
In a professional context, telling your company or client they should commit scarce, expensive engineering resources (e.g. your time) to creating and maintaining their own wheel design requires justification [2].
[2] "Don't reinvent wheels" is good general advice for junior developers. Senior developers know that sometimes there are specific situations where this general advice doesn't apply. For example, if no existing wheels meet your application's requirements, or if you have ideas for proprietary features that give you a competitive advantage. Even in a professional setting, reinventing the wheel isn't always a bad idea; you just need to meet a much higher bar to justify the commitment of resources.
Agreed; another useful technique is "Feed it to a heuristic solver". Heuristic solvers tend to be easier to program and reason about than a SAT solver, since you can use your existing domain model. Moreover, your scoring function look like a typical function that can call third party libraries (as heuristic solvers see the function as a black box usually). Heuristic solvers beat SAT solvers in cases like VRP, whereas SAT solvers are usually better at bin packing.
If you want to try to implement one yourself, a simple one is Simulated Annealing [1]. The core algorithm shouldn't be more than 30 lines of code; it is simple to implement.
If you want to try an existing library, you can try Timefold Solver [2] (disclosure: I work for Timefold).
CP-SAT is still a glorified and optimized recursive backtracking search. There's nothing better in the literature. They call it DPLL.
It just evaluates the data and constraints to search the more obvious paths first, and cut illegal paths earlier. And some integer tricks, and a cache of learned constraints. Which the Russians found, when trying to solve Chess efficiently. IBM/Ken Thompson just threw hardware at it, while the Russians made the algorithmic advances. Just as now with LLM's. The US folks just throw hardware at it, whilst the Chinese optimize their algos.
analog31 4 hours ago [-]
The first thing that came to my mind was: Tetris with periodic boundary conditions.
akoboldfrying 1 days ago [-]
> Instead of backtracking, Claude just imported an industrial-strength library made to solve these sorts of problems. OR-Tools CP-SAT is put out by Google and is made for solving constrained optimization problems, as well as satisfiability problems like this one.
I'm not familiar with CP-SAT, but TTBOMK all SAT solvers use a type of backtracking search underneath called DPLL. Modern ones are highly tuned in terms of which variable they choose to branch on next, and in what order to try its possible values; this can have an enormous impact on runtime. They probably use several tricks on top of that; the big one that I'm aware is conflict-driven clause learning, where the solver adds new constraints that it discovers as it goes along (e.g., it might be able to determine that x and y always have the same value in every solution), which can shrink the search space a lot.
taeric 1 days ago [-]
Yes, constraint learning is a huge deal. And there is a fun trick to solving sudoku that is basically this. Someone realized that you can essentially build an extra ring around the board that has the same constraints as elsewhere. Phistomefel Ring is the name, I believe. (This may be a different one, I just reached for the first thing a google search found for my vague description.)
> It was much better than I would have written myself, and I ended up learning from it.
Eventually shitting on LLM code will be seen by all as lazy cope. I too am aware of the existence of SAT but I really would struggle to immediately see through some problem i was having and interpret SAT unless I did it a bunch. Having agent suggest the "right thing" is clearly better. And hopefully would help my intuition in the future.
As a kid, it seemed obvious to me that a good model was the digits 1 through 8, representing the row that a queen would be in. Doing a recursive backtracker on an ordering of the digits and testing each pair for diagonal (digit i minus digit j was equal to +/- i-j) and my BASIC program spit out the solutions in twenty minutes.
I didnt enter the contest because I figured everybody would do that. Turns out when the editor published the 'best' solutions, they all, every single one, modeled the board as an 8 by 8 array and ran around following diagonals iteratively. And took hours to complete.
Anyway, choosing a good solution model is most of the problem solved.
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'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.
This is one that is hard for people to really internalize, I think? The SAT solvers many are likely to use today are not at all the same as the ones they would have used 20 years ago. They have made some amazing advances in how to approach those problems.
There are also probably some very poorly conceived models that people use to adapt a problem to some of these solvers.
Do you have examples that are public or that you can talk about?
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.
https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...
"Feed it to SAT solver" is a super useful technique every seasoned programmer should have in their toolbelt.
If you want to improve your programming skill, I suggest implementing your own version of these two interesting, satisfying algorithms:
- DPLL, the classic general-purpose SAT solving algorithm [3].
- Algorithm X (aka Dancing Links), Knuth's super elegant search algorithm for solving exact cover problems [4] [5].
You're not going to build something that beats CaDiCaL [6] in an afternoon, but writing your own implementation of these algorithms will teach you a lot, and a reasonable time investment will get you to a pretty satisfying endpoint of having a practical solver for your favorite application (Sudoku, polyomino packing, etc.)
[1] Reinventing wheels is not a bad way to spend your days at a retreat focusing on one's personal growth as a programmer. "I think I'll learn a lot and get some good practice at programming and algorithmic thinking" is an easy bar to meet.
In a professional context, telling your company or client they should commit scarce, expensive engineering resources (e.g. your time) to creating and maintaining their own wheel design requires justification [2].
[2] "Don't reinvent wheels" is good general advice for junior developers. Senior developers know that sometimes there are specific situations where this general advice doesn't apply. For example, if no existing wheels meet your application's requirements, or if you have ideas for proprietary features that give you a competitive advantage. Even in a professional setting, reinventing the wheel isn't always a bad idea; you just need to meet a much higher bar to justify the commitment of resources.
[3] https://en.wikipedia.org/wiki/DPLL_algorithm
[4] https://arxiv.org/abs/cs/0011047
[5] https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X
[6] https://github.com/arminbiere/cadical
If you want to try to implement one yourself, a simple one is Simulated Annealing [1]. The core algorithm shouldn't be more than 30 lines of code; it is simple to implement. If you want to try an existing library, you can try Timefold Solver [2] (disclosure: I work for Timefold).
[1] https://en.wikipedia.org/wiki/Simulated_annealing
[2] https://timefold.ai/solver
It just evaluates the data and constraints to search the more obvious paths first, and cut illegal paths earlier. And some integer tricks, and a cache of learned constraints. Which the Russians found, when trying to solve Chess efficiently. IBM/Ken Thompson just threw hardware at it, while the Russians made the algorithmic advances. Just as now with LLM's. The US folks just throw hardware at it, whilst the Chinese optimize their algos.
I'm not familiar with CP-SAT, but TTBOMK all SAT solvers use a type of backtracking search underneath called DPLL. Modern ones are highly tuned in terms of which variable they choose to branch on next, and in what order to try its possible values; this can have an enormous impact on runtime. They probably use several tricks on top of that; the big one that I'm aware is conflict-driven clause learning, where the solver adds new constraints that it discovers as it goes along (e.g., it might be able to determine that x and y always have the same value in every solution), which can shrink the search space a lot.
Eventually shitting on LLM code will be seen by all as lazy cope. I too am aware of the existence of SAT but I really would struggle to immediately see through some problem i was having and interpret SAT unless I did it a bunch. Having agent suggest the "right thing" is clearly better. And hopefully would help my intuition in the future.