Metraipolis › archive › dc_fd58eb03c9cb

From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles — arXiv:2611.03641

Source
arXiv (en)
Original
https://arxiv.org/abs/2611.03641
License (as archived)
CC0-1.0
Archived
2026-11-03T10:24:22.057Z
SHA-256 of the archived text
4d98bcf01bb64f1d7b23e94d88afbbef8ca84420208f1ae7d082fcce54085b68
Stable URL of this page
https://metraipolis.com/documento/dc_fd58eb03c9cb

How to cite

From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles — arXiv:2611.03641 — arXiv (en), https://arxiv.org/abs/2611.03641 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fd58eb03c9cb (Metraipolis archive dc_fd58eb03c9cb, sha256 4d98bcf01bb64f1d7b23e94d88afbbef8ca84420208f1ae7d082fcce54085b68)
BibTeX
@misc{dcfd58eb03c9cb,
  title = {From Natural Language to Exact Cover: A Neuro-Symbolic Approach to Zebra Puzzles — arXiv:2611.03641},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2611.03641},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fd58eb03c9cb; sha256 4d98bcf01bb64f1d7b23e94d88afbbef8ca84420208f1ae7d082fcce54085b68},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03641. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno).
Categorie arXiv: Artificial Intelligence (cs.AI).
Pagina del lavoro: https://arxiv.org/abs/2611.03641 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-03T10:19:49.960Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).