Learning to Automatically Solve Logic Grid Puzzles

Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1023–1033, Lisbon, Portugal, 17-21 September 2015. c⃝2015 Association for Computational Linguistics. Learning to Automatically Solve Logic Grid Puzzles Arindam Mitra SCIDSE Arizona State University amitra7@asu.edu Chitta Baral SCIDSE Arizona State University chitta@asu.edu Abstract Logic grid puzzle is a genre of logic puz- zles in which we are given (in a natural language) a scenario, the object to be de- duced and certain clues. The reader has to figure out the solution using the clues provided and some generic domain con- straints. In this paper, we present a sys- tem, LOGICIA, that takes a logic grid puz- zle and the set of elements in the puz- zle and tries to solve it by translating it to the knowledge representation and rea- soning language of Answer Set Program- ming (ASP) and then using an ASP solver. The translation to ASP involves extrac- tion of entities and their relations from the clues. For that we use a novel learn- ing based approach which uses varied su- pervision, including the entities present in a clue and the expected representa- tion of a clue in ASP. Our system, LO- GICIA, learns to automatically translate a clue with 81.11% accuracy and is able to solve 71% of the problems of a corpus. This is the first learning system that can solve logic grid puzzles described in natu- ral language in a fully automated manner. The code and the data will be made pub- licly available at http://bioai.lab. asu.edu/logicgridpuzzles. 1 Introduction Understanding natural language to solve problems be it algebraic word problems (Kushman et al., 2014; Hosseini et al., 2014) or questions from bi- ology texts (Berant et al., 2014; Kim et al., 2011), has attracted a lot of research interest over the past few decades. For NLP, these problems are of par- ticular interest as they are concise, yet rich in in- formation. In this paper, we attempt to solve an- other problem of this kind, known as Logic Grid Puzzle. Problem.1 shows an example of the same. Puzzle problems in the same spirit as the previ- ously mentioned science problems, do not restrict the vocabulary; they use everyday language and have diverse background stories. The puzzle prob- lems, however, are unique in their requirement of high precision understanding of the text. For a puzzle problem, the solution is never in the text and requires involved reasoning. Moreover, one needs to correctly understand each of the given clues to successfully solve a problem. Another in- teresting property is that only a small core of the world knowledge, noticeably spatial, temporal and knowledge related to numbers, is crucial to solve these problems. PROBLEM .1 A LOGIC GRID PUZZLE Waterford Spa had a full appoint- ment calendar booked today. Help Janice figure out the schedule by matching each masseuse to her client, and determine the total price for each. 1. Hannah paid more than Teri’s client. 2. Freda paid 20 dollars more than Lynda’s client. …

Content truncated to 500 words