Solving Puzzles Described in English by Automated Translation to Answer Set Programming and Learning How To Do That Translation

Chitta Baral, Juraj Dzifcak

Introduction

Combinatorial logic puzzles, such as the well-known "Zebra Puzzle," represent a unique challenge for artificial intelligence. Solving these puzzles requires an agent to perform two distinct, difficult tasks: parsing complex, often ambiguous natural language clues into precise logical constraints, and then reasoning through a vast space of possibilities to find a unique solution. Historically, systems designed to solve such puzzles relied on manual encoding of logic rules. This paper presents a novel framework that automates this process, learning to translate English descriptions into Answer Set Programming (ASP) through a combination of semantic calculus and probabilistic parsing.

The Challenge of Logic Puzzles

For AI, logic puzzles present a "double whammy" of difficulty. First, the Natural Language Understanding (NLU) component must handle non-restricted English grammar to extract specific constraints (e.g., "The person with the Dragon had their fortune told fourth"). Second, the Knowledge Representation and Reasoning component requires a robust "world model" or ontology to understand concepts like temporal order, spatial positioning, and exclusive ownership.

In this domain, the cost of error is exceptionally high. Unlike many NLU tasks where a 90% accuracy rate is considered excellent, a single misinterpretation of a clue in a logic puzzle usually renders the entire puzzle unsolvable. This "fragility of logic" means that the system must achieve near-perfect translation across a set of clues to succeed.

Methodology

The authors developed a pipeline that transforms raw text into a formal solution using several innovative components:

1. $\lambda$-ASP-Calculus

The researchers adapted classical $\lambda$-calculus—a mathematical framework for semantics—to the domain of Answer Set Programming. In this system, the "meaning" of a word or phrase is represented as an ASP rule, allowing for the compositional construction of complex logical statements from individual words.

2. The Inverse $\lambda$ Algorithm

The core innovation of the paper is the Inverse $\lambda$ algorithm. This algorithm treats language acquisition as a mathematical deduction. If the system knows the logical meaning of an entire sentence and the meaning of some constituent words, it can "subtract" the known meanings to deduce the missing meanings of unknown words. This allows the system to learn a lexicon of ASP-mapped words directly from training data.

3. Probabilistic Combinatorial Categorial Grammars (PCCG)

Because English words often have multiple meanings depending on context, the system employs a probabilistic parser. It assigns weights to various potential meanings and learns, through experience, which interpretations are most likely to result in a valid and consistent ASP translation.

4. General Ontology

To avoid building a custom solver for every new puzzle, the authors created a generic ASP world model. This ontology handles the fundamental "rules of the game"—such as the requirement that every person has exactly one rank or one item—allowing the learned translator to focus solely on the specific constraints provided by the clues.

Experimental Setup and Results

The system was evaluated using a corpus of 50 logic puzzles sourced from Penny Press and Dell Magazines, comprising approximately 800 individual clues. While the English was preprocessed to resolve complex anaphora (e.g., replacing "he" or "it" with the appropriate subject), the grammar remained non-restricted.

Performance Metrics

  • Clue Translation: The system achieved a precision of 87.64% and a recall of 86.12% in translating individual clues into ASP rules.
  • Puzzle Solving:
    • Using 10-fold cross-validation, the system solved 56% of the puzzles entirely correctly.
  • When the training set was curated to include 20 diverse, representative puzzles, the success rate for solving entire puzzles rose to 83.3%.

These results are highly competitive with state-of-the-art NLU systems in related domains, such as Geoquery (database querying) and RoboCup (robotic command processing).

Discussion and Limitations

The research highlights several critical insights into the intersection of language and logic. The authors found that the system often learned "trivial" meanings for function words like "the" or "a," effectively learning to ignore them as they did not contribute to the final ASP constraints.

However, limitations remain. The system struggles with "rare phrasing"—clues that appear only once or twice in the dataset (e.g., "exactly two days after"). Without sufficient examples, the Inverse $\lambda$ algorithm cannot generalize the meaning of these unique constructions. Furthermore, the system is dependent on the initial syntactic parse; if the underlying C&C parser fails to identify the correct sentence structure, the semantic translation fails regardless of the learned lexicon.

Conclusion

This work demonstrates that it is possible to learn the mapping between natural language and formal logic rules without exhaustive manual coding. By treating word meanings as parameters to be learned from data, the authors have provided a path toward more flexible and autonomous reasoning systems. Future work aims to integrate more advanced NLU tools to handle raw, unprocessed natural language and to scale the approach to broader knowledge-retrieval tasks.

Summary updated

BibTeX
@inproceedings{baral2012solving,
  author = {Chitta Baral and Juraj Dzifcak},
  title = {{Solving Puzzles Described in English by Automated Translation to Answer Set Programming and Learning How To Do That Translation}},
  booktitle = {KR},
  year = {2012},
  url = {https://openreview.net/forum?id=9O1bUMJjK5},
}
Figure