 and is defined using the tuple/3 predicate.

Domain Constraints
In the proposed approach, the logic grid puzzle problem is solved as a constraint satisfaction problem. Given a puzzle problem the goal is to enumerate over all possible configurations of tuple/3, and select the one which does not violate the constraints specified in the clues. However, 1) each tuple in a logic grid puzzle will contain exactly one element from each category and 2) an element will belong to exactly one tuple. These constraints come from the specification of a puzzle problem and will hold irrespective of the problem instance. Following blocks of code show an elegant representation of these domain constraints in ASP along with the enumeration.

Representing clues
Each clue describes some entities and the relations that hold between them. In its simplest form, the relations will suggest if the entities are linked together or not. However, the underlying semantics of such relations can be deep such as the one in clue 5 of Problem.1. There are different ways to express the same relation that holds between entities. For example, in Problem.1, the possessive relation has been used to express the linking between clients and masseuses; and the word paid expresses the linking between the clients and the prices. Depending on the puzzles the phrases that are used to express the relations will vary and it is crucial to identify their underlying semantics to solve the problems in systematic way.
In the current version, the reasoning module has knowledge of a selected set of relations and the translation module tries to represent the clue as a conjunction of these relations. All these relations and their underlying meanings are described in table 1. In this subsection, we describe the representation of a clue in terms of these relations in ASP and show how it is used by the reasoning module. In the next section, we present our approach to automate this translation.
Let us consider the clues and their representation from Problem.1: [1] Hannah paid more than Teri's client.
The first rule clue1 evaluates to true (will be in the answer set) if the element from category 1 with value hannah is linked to some element from category 2 which has a higher value than the element from its own category which is linked to an element from category 1 which is linked to teri from category 3. Since the desired solution must satisfy the relations described in the clue, the second ASP rule is added. A rule of this form that does not have a head is known as a constraint and the program must satisfy it to have an answer set. As the reasoning module enumerates over all possible configurations, in some cases the clue1 will not hold and subsequently those branches will be pruned. Similar constraints will be added for all clues. In the below, we show some more examples. A configuration which satisfies all the clue constraints and the domain constraints described in the previous section, will be accepted as the solution to the puzzle.
[3] Hannah was either the person who paid $180 or Lynda's client.

Learning Translation
To automate the translation of a clue to the pair of ASP rules, the translation module needs to identify the entities that are present in the clue, their category and their value; and the underlying interpretations of all the relations that hold between them. Once all the relation instances {R 1 (arg 1,..., arg p 1 ),..., R q (arg 1,..., arg pq )}, in the clue are identified, the ASP representation of the clue is generated in the following way: clue : −R 1 (arg 1..., arg p 1 ),..., R q (arg 1..., arg pq ) The entity classification problem for logic grid puzzles poses several challenges. First, the existence of a wide variety in the set of entities. Entities can be names of objects, time related to some event, numbers, dates, currency, some form of ID etc. And it is not necessary that the entities in puzzles are nouns. It can be verbs, adjectives etc. Second and of paramount important, the "category" of a puzzle "element" is specific to a puzzle problem. Same element may have different category in different problems. Also, a constituent in a clue which refers to an entity in a particular problem may not refer to an entity in another problem. We formalize this problem in this section and propose one approach to solve the problem. Next, we discuss the method that is used to extract relations from clues. To the best of our knowledge, this type of entity classification problem has never been studied before.

Entity Classification
The entity classification problem is defined as follows: Problem description Given m categories C 1,..., C m and a text T, each category C i, 1 ≤ i ≤ m, contains a collection of elements E i and an optional textual description d i. The goal is to find the class information of all the constituents in the text T. Each category contributes two classes, where one of them represents the category itself and the other represents an instance of that category. Also, a constituent may not refer to any category or any instance of it, in that case the class of that constituent is null. So, there are a total 2m+1 classes and a constituent will take one value from them.
The constituent "clients" in the fourth clue refers to the category C 1.

Our approach
We model the Entity Classification problem as a decoding query on Pairwise Markov Network (Koller and Friedman, 2009;Kindermann et al., 1980;Zhang et al., 2001). A pairwise Markov network over a graph H, is associated with a set of node potentials {φ(X i ) : i = 1,..., n} and a set of edge potentials {φ(X i, X j ) : (X i, X j ) ∈ H}. Each node X i ∈ H, represents a random variable. Here, each X i can take value from the set {1...2m + 1}, denoting the class of the corresponding constituent in the text T.
In our implementation, the node potential captures the chances of that node to be classified as one of the possible categories without being affected by the given text T. And the edge potentials captures hints from the context in T for classification. After constructing the pairwise Markov network, a decoding query is issued to obtain the configuration that maximizes the joint probability distribution of the pairwise Markov network in consideration. The proposed approach is inspired by the following two observations: 1) to find the class of a constituent one needs some background knowledge; 2) however, background knowledge is not sufficient on its own, one also needs to understand the text to properly identify the class of each constituent. For example, let us consider the word "person" in clue 5 of Problem.1. Just skimming through the categories, one can discover that the word "person" is very unlikely to be a instance of the category "prices", which is from her knowledge about those constituents. However a proper disambiguation may face an issue here as there are two different categories of human beings. To properly classify the word "person" it is necessary to go through the text.
The following paragraphs describe the construction of the grah H, and the algorithm that is used in the computation of associated set of node potentials and edge potentials.
Construction of the graph While constructing the graph, we assign a label, L, to each edge in H which will be used in the edge potential computation. Let D G denotes the dependency graph of the text T obtained from the Stanford dependency parser  and dep(v 1, v 2 ) denotes the grammatical relation between (v 1, v 2 ) ∈ D G. Then the graph, H, is constructed as follows: 1. Create a node in H for each constituent w j in T if w j ∈ D G.

Add an edge
3. Add an edge between a pair of nodes (X i, X j ) if the corresponding words are synonyms. L(X i, X j ) := synonymy.
4. Create a node for each element and category specified in the puzzle and add an edge from them to others if the corresponding string descriptions are'same'. In this case, the edges are labeled as exact match.
5. If (X i, X j ) ∈ H and L(X i, X j ) = exact match and both of them are referring to a verb, then add more edges (X i, X j ) to H with label spatial symmetry, where L(X i, X i ) = L(X j, X j ).
Determining Node potentials For each element in the m category, a set of naive regular-expression based taggers are used to detect it's type (For example, "am-pm time"). Each element type maps to a WordNet (Miller, 1995) representative (For example, "time unit#n"). For each constituent w a similarity score, sim(w,c), is calculated to each class c ∈ {1...2m + 1}, in the following way: •Class c is denoting instance of some category C i Similarity scores are computed between the textual description of the constituent to both the WordNet representative of E i and the textual description d i using the HSO WordNet similarity algorithm (Hirst and St-Onge, 1998). The similarity score, sim(w,c), is chosen to be the maximum of them.
•Class c is denoting a category C i : sim(w,c) is assigned the value of HSO Similarity between the textual description and d i.
•Class c is null : In this case similarity is calculated using the following formula: where M AX HSO denotes the maximum similarity score returned by HSO algorithm, which is 16.
Node potential for each node X i ∈ H, corresponding to the constituent w j, are then calculated by, φ(X i = c) = 1 + sim(w j, c