mlsanityData to 14 Oct 2026

Solving Zebra Puzzles Using Constraint-Guided Multi-Agent Systems

arXiv 2407.03956 ↗First posted 4 Jul 2024cs.MA cs.CLcited by 4

On the map: LLM reasoning → Reasoning benchmarks and evaluation

also in 1 more
Abstract (arXiv)

Prior research has enhanced the ability of Large Language Models (LLMs) to solve logic puzzles using techniques such as chain-of-thought prompting or introducing a symbolic representation. These frameworks are still usually insufficient to solve complicated logical problems, such as Zebra puzzles, due to the inherent complexity of translating natural language clues into logical statements. We introduce a multi-agent system, ZPS, that integrates LLMs with an off the shelf theorem prover. This system tackles the complex puzzle-solving task by breaking down the problem into smaller, manageable parts, generating SMT (Satisfiability Modulo Theories) code to solve them with a theorem prover, and using feedback between the agents to repeatedly improve their answers. We also introduce an automated grid puzzle grader to assess the correctness of our puzzle solutions and show that the automated grader is reliable by evaluating it in a user-study. Our approach shows improvement in all three LLMs we tested, with GPT-4 showing 166% improvement in the number of fully correct solutions.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Placed in Reasoning benchmarks and evaluation, one of 17 directions in LLM reasoning. Builds on 8 of its 23 references that are in the map. First posted on arXiv 4 Jul 2024.

Builds on

8 of 23 references.

Closest ancestors · 2

Same direction, newest first

  1. 2023Measuring reasoning capabilities of ChatGPT8 Oct
  2. 2023SatLM: Satisfiability-Aided Language Models Using Declarative Prompting16 May

Other references · 6

  1. 2023A Survey on Large Language Model based Autonomous Agentscited by 2,242
  2. 2022Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Taskscited by 1,076
  3. 2023Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Modelscited by 574
  4. 2024Agent AI: Surveying the Horizons of Multimodal Interactioncited by 170
  5. 2019Learning from Dialogue after Deployment: Feed Yourself, Chatbot!cited by 102
  6. 2023Integrating Graphs with Large Language Models: Methods and Prospectscited by 18

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025Logic.py: Bridging the Gap between LLMs and Constraint Solverscited by 9
  2. 2025A Reality Check of Language Models as Formalizers on Constraint Satisfaction Problemscited by 1
  3. 2025Evaluating Implicit Biases in LLM Reasoning through Logic Grid Puzzlescited by 1
  4. 2026VeryTrace: Verifying Reasoning Traces through Compilable Formalism and Structured Verificationcited by 1

Similar, not cited

Close in wording, no citation either way

  1. 2025ZebraLogic: On the Scaling Limits of LLMs for Logical Reasoning
  2. 2024Puzzle Solving using Reasoning of Large Language Models: A Survey
  3. 2025Logic-of-Thought: Empowering Large Language Models with Logic Programs for Solving Puzzles in Natural Language
  4. 2025LogicPuzzleRL: Cultivating Robust Mathematical Reasoning in LLMs via Reinforcement Learning
  5. 2025Enigmata: Scaling Logical Reasoning in Large Language Models with Synthetic Verifiable Puzzles
  6. 2025MultiZebraLogic: A Multilingual Logical Reasoning Benchmark
  7. 2025FINEREASON: Evaluating and Improving LLMs' Deliberate Reasoning through Reflective Puzzle Solving
  8. 2025What to Ask Next? Probing the Imaginative Reasoning of LLMs with TurtleSoup Puzzles