옥수수 퍼즐, CP-SAT로 풀어내다
Solving a corn puzzle with CP-SAT
RC에서 옥수수 퍼즐을 풀다가 Claude에게 물어봤더니, Claude는 직접 백트래킹을 구현하는 대신 Google의 OR-Tools CP-SAT를 사용했다. 퍼즐은 Exact Cover 문제의 변형으로, 각 조각이 정확히 한 번 놓이고 각 칸이 정확히 한 번 덮이는 제약만으로 모델링된다. 이후 스도쿠에도 같은 도구를 적용해보며, 앞으로 비슷한 문제를 만나면 직접 구현하기보다 솔버를 쓰기로 배웠다.
앞으로 또 cp-sat 형태의 문제를 만나면, 직접 구현하기보다 솔버를 시도하고 필요한 건 문서를 읽어서 해결하겠다는 것을 배웠다.
HN 토론
16- emil-lp
여기서 CP는 Constraint Problem, 즉 CSP(Constraint Satisfaction Problem)를 뜻한다.
https://en.wikipedia.org/wiki/Constraint_satisfaction_proble...
- sashank_1509
좋아, 이 특정한 경우에는, 조각이 10개쯤 되는 퍼즐이라면 재귀 백트래커가 속도도 똑같이 빠르고, 더 중요하게는 추론하고 구현하기가 훨씬 쉽다.
만약 이게 천 조각 퍼즐이었다 해도, 나는 여전히 좋은 휴리스틱을 갖춘 재귀 백트래커가 CP-SAT를 이길 거라고 본다. 심지어 스도쿠 같은 경우에도 백트래킹에 좋은 휴리스틱을 몇 개 붙이면 CP-SAT를 이긴다. Claude가 왜 곧바로 CP-SAT를 쓰는 쪽으로 뛰어들었는지는 모르겠다.
- nh23423fefe
> 내가 직접 작성했을 것보다 훨씬 나았고, 결국 그것에서 배우게 됐다.
결국 LLM 코드를 까는 건 누구에게나 게으른 현실 부정으로 보이게 될 거다. 나도 SAT의 존재를 알고 있지만, 내가 겪고 있는 어떤 문제를 곧바로 꿰뚫어 보고 SAT로 해석하려면 그걸 여러 번 해보지 않고서는 정말 어려울 것이다. 에이전트가 "올바른 것"을 제안해 주는 건 분명 더 낫다. 그리고 앞으로 내 직관에도 도움이 되길 바란다.