Metraipolis › archive › dc_24345357bd7b

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:54:40.751Z
SHA-256 of the archived text
8c9e75efae1fb14f55f4c8d03347158f147dddb42c18290ff1ae5328240d081d
Stable URL of this page
https://metraipolis.com/documento/dc_24345357bd7b

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_24345357bd7b (Metraipolis archive dc_24345357bd7b, sha256 8c9e75efae1fb14f55f4c8d03347158f147dddb42c18290ff1ae5328240d081d)
BibTeX
@misc{dc24345357bd7b,
  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_24345357bd7b; sha256 8c9e75efae1fb14f55f4c8d03347158f147dddb42c18290ff1ae5328240d081d},
  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:49:38.437Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).