LGPS olver - Solving Logic Grid Puzzles Automatically (2020)

Abstract: Logic grid puzzle (LGP) is a type of word problem where the task is to solve a problem in logic. Constraints for the problem are given in the form of textual clues. Once these clues are transformed into formal logic, a deductive reasoning process provides the solution. Solving logic grid puzzles in a fully automatic manner has been a challenge since a precise understanding of clues is necessary to develop the corresponding formal logic representation. To meet this challenge, we propose a solution that uses a DistilBERT-based classifier to classify a clue into one of the predefined predicate types for logic grid puzzles. Another novelty of the proposed solution is the recognition of comparison structures in clues. By collecting comparative adjectives from existing dictionaries and utilizing a semantic framework to catch comparative quantifiers, the semantics of clues concerning comparison structures are better understood, ensuring conversion to correct logic representation. Our approach solves logic grid puzzles in a fully automated manner with 100% accuracy on the given puzzle datasets and outperforms state-of-the-art solutions by a large margin.

## introduction logic grid puzzle (lgp) is a type of word problem where the task is to solve a problem in logic. lgp can be on any domain. constraints for an lgp are provided as textual clues. the precise understanding of these clues is crucial to correctly solve the puzzle because the representation of clues leads the logical reasoning process. automatically solving any word problem paves the way for more equipped digital assistants that take textual commands. both word algebra problems and logic puzzles appear in admission tests such as the graduate record exam (gre). thus, automation improves the understanding of these problems and can be used in the training of students. in the field of natural language processing (nlp), semantic representations are improved day by day. state-of-the-art bert @xcite representations have boosted performance in a wide variety of nlp tasks. the rising interest is on frameworks that combine neural network-driven representations with logic representations to reason about language and predict correct outputs for tasks such as natural language inference (nli) @xcite . logic puzzle solving is a task that is considered in this direction, as well. lgps are usually defined by a description and clues. the description part introduces categories and instances associated with each of them, and clues provide the definitions of constraints on the relationships between instances. the description can be represented by an n ×m matrix where n is the number of categories, and m is the number of instances of a category. the main rule of logic grid puzzles is that one instance of a category should match only one instance of another category. the solution is provided as a tuple of instances for each category. here is an example of a simple 3 × 4 logic grid puzzle taken from puzzlebaron foot_0 : the student who studies astronomy gets a smaller scholarship than alice, alice is either the one who studies english or the one who studies philosophy, the student who studies physics has a $5000 bigger scholarship than alex. there has been some work that can automatically solve an lgp. puzzler @xcite uses an architecture that is composed of a parser and an inference module. in the parser module, clues are parsed using a link grammar parser, and the resultant parse trees are converted into logic representations by a semantic translator. puzzler runs constraints in logic representation through the alloy language to provide the solution. the system is designed around the zebra puzzle and tested on a small dataset. @xcite use a trained model that consists of clues along with their desired representations in the form of λ-calculus rules to translate clues into answer set programming (asp). to distinguish between the multiple meanings of words, their system governs word to λ-asp-calculus rule association through probabilities. logicia @xcite introduces a maximum-entropy based model for categorizing clues using features such as dependency trees, pos tags, etc. with the use of answer set programming, it correctly solves 71 puzzles out of 100. logicsolver @xcite generalizes and improves puzzler's @xcite parser method by adding more regular expression rules. in the solver module, puzzle is solved using custom first-order predicate logic parser on the predicates of type is, not, xor, and comparison predicates. he uses a dataset of 68 puzzles with various difficulties to evaluate logicsolver. lgpsolver differs from the aforementioned systems in two ways. in lgps, semantic representation of clues is crucial because it leads the logical reasoning process to solve the puzzle. considering this, we use a distilbert-based @xcite classifier, where a transformer model is combined with a feed-forward layer and softmax to perform clue classification. language models like distil-bert take word order and context into account, which are distinctive features of clues. another notable characteristic of clues is that they consist of comparison structures. in general, a comparison is given among locations, times, or some numbers in the selected domain. we use a collected set of comparative adjectives and a semantic framework to identify comparative quantifiers. by categorizing these comparison quantifiers, lgpsolver can parse comparison clues. our experimental results show that our approach outperforms state-of-the-art solutions by a large margin by reaching 100% accuracy on the given puzzle datasets. ## methodology our approach to solving lgps consists of four steps: parsing and classifying the given clues, defining the category instances in prolog, converting the parsed clues into logic representations, and solving puzzles using the reasoning module. the source code with dependencies is provided as a downloadable link foot_1 . ## results for the work's evaluation, we have used the datasets provided by logicia @xcite and logicsolver @xcite . logicia dataset has 150 lgps, whereas logicsolver has @xcite lgps. we have used the 50 lgps (the training set in logicia) from the logicia dataset for distilbert training, and the remaining 100 lgps are used for the testing purposes. the 68 lgps in the logicsolver dataset are also used as a test set without additional training. in brief, there are 50 training and 168 test samples. the details of these datasets are given in the evaluation is based on two factors: parser and solver accuracies. parser accuracy is defined as the percentage of the correctly parsed clues (including classification), while solver accuracy is the percentage of correctly solved puzzles. the performance of lgpsolver was compared to logicsolver and logicia. the experimental results are shown in lgpsolver has correctly solved all the lgps in the given datasets. it should also be noted that to solve lgps successfully with the reasoning module of prolog; the puzzle description should be parsed without any errors. ## conclusion and future work this paper presents a system that automatically solves logic grid puzzles. better identification of comparison structures in clues and using a distilbert-based clue classification solution are the two highlights of the system. lgpsolver achieves full accuracy in a fully automated manner. the distilbert-based classifier is a fundamental component of our workflow because it can capture the context of clues. the traditional classifiers (e.g., naive bayes, svm, logistic regression) have a lower accuracy, which can be attributed mostly to the misclassification of comparison type clues as is type clues. furthermore, rule-based classifiers (e.g., regex patterns) were not preferred due to their generalizability issues as every little variation in clues introduces an update to the rule base. on the other hand, a pretrained language model is quite robust and able to classify a clue even there are small variations in the sentence structure.