From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles
The paper pairs an LLM’s natural-language parsing with an exact-cover solver for Zebra puzzles. For agent workflows, it shows how a symbolic tool can check and help repair an LLM’s structured interpretation.
The framework turns a natural-language Zebra puzzle into structured tool calls, builds an exact-cover instance, then uses a symbolic solver to find a solution. Solver feedback helps revise invalid or over- or underconstrained encodings, using the puzzle’s uniqueness property. The authors report better results than chain-of-thought prompting and recent neuro-symbolic methods across multiple models and evaluation settings.
For agent workflows that need reliable logical results, consider having the model translate the request into a formal representation and letting a deterministic solver handle the decision. Use solver feedback to catch errors in the representation itself.
The framework turns a natural-language Zebra puzzle into structured tool calls, builds an exact-cover instance, then uses a symbolic solver to find a solution. Solver feedback helps revise invalid or over- or underconstrained encodings, using the puzzle’s uniqueness property. The authors report better results than chain-of-thought prompting and recent neuro-symbolic methods across multiple models and evaluation settings. For agent workflows that need reliable logical results, consider having the model translate the request into a formal representation and letting a deterministic solver handle the decision. Use solver feedback to catch errors in the representation itself. The evaluation is limited to Zebra-style puzzles. The material does not establish that this approach generalizes to other tasks, or quantify its gains.
The paper presents a narrow but concrete pattern for reliable logical tasks: translate natural language into a formal problem, delegate decisions to a symbolic solver, and use solver feedback to revise the encoding. Its reported gains apply to Zebra-style puzzles, so the supplied material supports testing this separation of responsibilities without establishing broader generalization.