Statt Backtracking: Wie Claude ein Mais-Puzzle mit CP-SAT löst
Solving a corn puzzle with CP-SAT
Ein 3D-gedrucktes Mais-Puzzle diente als Anlass, statt selbstgebautem Backtracking Googles OR-Tools CP-SAT einzusetzen. Der Autor modelliert das Puzzle als Exact-Cover-Problem mit binären Variablen und zwei Constraint-Klassen: Jedes Teil wird genau einmal platziert, jede Rille genau einmal bedeckt. Anschließend überträgt er das Gelernte auf Sudoku – und zieht das Fazit, künftig lieber fertige Solver zu nutzen.
Wenn ich in Zukunft auf ein weiteres CP-SAT-förmiges Problem stoße, werde ich wissen, dass ich einen Solver ausprobieren und die Dokumentation lesen sollte, anstatt etwas Eigenes zu entwickeln.
- emil-lp
CP steht hier für Constraint Problem, oder CSP (Constraint Satisfaction Problem).
https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...
- sashank_1509
Ok, in diesem speziellen Fall, bei einem Puzzle mit etwa 10 Teilen, wird ein rekursiver Backtracker genauso schnell sein und – was noch wichtiger ist – viel einfacher zu durchdenken und zu implementieren.
Wenn es ein Puzzle mit tausend Teilen wäre, würde ich immer noch darauf wetten, dass ein rekursiver Backtracker mit guten Heuristiken CP-SAT schlägt; selbst im Sudoku-Fall schlagen einige gute Heuristiken mit Backtracking CP-SAT. Ich bin mir nicht sicher, warum Claude sofort zu CP-SAT gegriffen hat.
- nh23423fefe
> Es war viel besser, als ich es selbst geschrieben hätte, und ich habe am Ende davon gelernt.
Irgendwann wird es von allen als faule Bewältigungsstrategie angesehen werden, auf LLM-Code herumzuhacken. Ich bin mir auch der Existenz von SAT bewusst, aber ich würde mich wirklich schwer tun, sofort ein Problem, das ich habe, zu durchschauen und SAT zu interpretieren, es sei denn, ich hätte es oft gemacht. Wenn ein Agent das "Richtige" vorschlägt, ist das eindeutig besser. Und hoffentlich würde es in Zukunft meiner Intuition helfen.