Neuro symbolic method solves logic puzzles from natural language reliably
From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles
Artificial Intelligence
Summary
Solving logical riddles written in everyday language can be tricky for computer programs. The researchers developed a new method that uses AI to understand puzzle statements and then applies a precise mathematical tool to find solutions correctly. This approach combines the flexibility of language understanding with the certainty of formal logic. Their method works better than previous AI-based ways and can fix errors by checking the puzzle’s unique answer property.
What this means in practice
- •For ai software developers: Turn natural language logic problems into formal inputs for exact solvers to improve reasoning reliability in AI systems.
- •For automation engineers: Generate precise logic constraints from verbal requirements for automated planning and scheduling tools.
Authors
Paulius Skaisgiris, Thomas Pammer, Veronika Semmelrock, Mykyta Ielanskyi, Maximilian Heisinger, Erich Kobler
Abstract
Chain-of-Thought (CoT) generation has substantially improved the performance of Large Language Models (LLMs) on complex reasoning tasks, including code generation, data analysis, and exam-style question answering. Despite these advances, purely neural LLMs continue to struggle with elementary logical reasoning problems and lack the determinism, soundness, and reliability characteristic of symbolic reasoning systems. Conversely, classical symbolic methods such as SAT solving and exact cover guarantee correctness and completeness, but require problems to be expressed in highly specialized formal encodings, limiting their applicability to natural language inputs. In this work, we present a synergistic neuro-symbolic framework that bridges this gap by combining neural semantic parsing with deterministic exact cover reasoning. Given a Zebra-style logic puzzle in natural language, an LLM translates entities and constraints into structured tool calls that construct an exact cover instance. A symbolic solver then computes the solution and provides feedback to iteratively refine invalid, under- or overconstrained encodings, exploiting the uniqueness property of Zebra puzzles. We conduct a comprehensive empirical evaluation across multiple parameter scales, post-training paradigms, and LLM families. The results demonstrate that our hybrid approach consistently outperforms strong plain neural baselines, including CoT prompting, as well as recent neuro-symbolic methods.