Claude решил головоломку с кукурузой через CP-SAT, а не перебор
Solving a corn puzzle with CP-SAT
Автор наткнулся на физическую головоломку «кукурузный початок» и попросил Claude написать решатель. Вместо ожидаемого рекурсивного перебора Claude импортировал OR-Tools CP-SAT от Google и свёл задачу к Exact Cover: бинарные переменные для каждого размещения деталей и два набора ограничений — каждая деталь используется ровно один раз, каждая клетка покрыта ровно один раз. Для закрепления урока автор с друзьями применил тот же подход к судоку.
Однако, взглянув на скрипт Claude, я понял с первой строки, что веду себя глупо: from ortools.sat.python import cp_model
- 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, если бы я не делал этого много раз. То, что агент предлагает «правильную вещь», явно лучше. И, надеюсь, это поможет моей интуиции в будущем.