Metraipolis › archive › dc_606bed5bbb4e

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:33:52.387Z
SHA-256 of the archived text: 811cd74d062ff72bab0ebb9bfc008cff8acd4ce64890c43b1afec0efb6640e69
Stable URL of this page: https://metraipolis.com/documento/dc_606bed5bbb4e

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_606bed5bbb4e (Metraipolis archive dc_606bed5bbb4e, sha256 811cd74d062ff72bab0ebb9bfc008cff8acd4ce64890c43b1afec0efb6640e69)

BibTeX

@misc{dc606bed5bbb4e,
  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_606bed5bbb4e; sha256 811cd74d062ff72bab0ebb9bfc008cff8acd4ce64890c43b1afec0efb6640e69},
  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:29:48.648Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).