Classically, the zebra puzzle can be easily solved by a modelling it as a constraint satisfaction problem (CSP). All you need to do is define the variables, ranges, and constraints. 

Dear N. H. N. D. De Silva

Right, you can solve the zebra puzzle by CSP. You can also solve it in many other formal languages (http://rosettacode.org/wiki/Zebra_puzzle).

Note, however, that you wrote "all you need to do is define the variables, ranges, and constraints", i.e. you have to reformulate the zebra puzzle – given in natural language – in the concepts and data structures of CSP, respectively of the formal language that you use.

Maybe, I was not sufficiently clear in my original question. What I meant to ask is this: Given a puzzle expressed in natural language, is it possible to solve it by logical deduction – i.e. not reformulating it in a formal language –  without additional information?

For Schubert's steamroller and some of Lewis Carroll's puzzles the answer is yes – I proved this by using my reasoner RACE for Attempto Controlled English – while for the zebra puzzle and the marathon puzzle the answer seems to be no since you need to add problem-specific information based on a problem-specific solution strategy.

A corollary question: If there is a difference between puzzles that can be solved directly by deduction and others that cannot, what is this difference?

In a line, in my humble opinion: the problems with additional information which make generalization difficult require the use of prior ontological knowledge to 'bridge' statements which do not have connected grounded evidence. This requires an AI system around the n-order logic reasoner.

A primary, prior matter to be solved is in the correct formulation/formalization of the question itself, to then either i) use defaults/prior structural knowledge to 'bridge' statements which are not connected, or alternatively ii) acknowledge partiality of information and make use of statistical inference on predicate evidence.

This is regardless of the level of reasoning which is required in the backend (e.g. quantifying over predicates, functions, or modality). 

A possible stochastic-enabled approach, which is to be preferred to the use of defaults as these are usually inputted and cannot be taken for granted, is perhaps statistical relational learning (informally, making use of a set of weighted first-order logic statements that compose undirected networks), to then attempt a probabilistic inference to find a solution, e.g. via maximum a posteriori. 

In short, I recommend thinking on how to constrain the problem formulation to a correct formalization, to then check if "Markov logic networks" (Richardson and Domingos, 2006) or its tractable subset ("A Tractable First-Order Probabilistic Logic.", Domingos et al. 2012) can offer the required expressiveness. I have strong doubts that CSP or its weighted equivalent can provide solutions given its 'bridging problem'. CSP when formalized in first order logic comprises a subset of the latter's expressiveness and does not scale to problems that have more than unary and binary constraints over the solutions.

All this is not a certain reply but an educated guess.

In the meantime I found an answer to my question "If you need additional information to solve a natural language puzzle by logical deduction, is there a systematic way to find this information?".

I came to the conclusion that the answer is "no".

Here is why:

To understand a text in natural language, specifically to draw conclusions from the text, humans use additional, contextual knowledge – usually without even being aware of this.

But context is difficult to define. Graeme Hirst wrote in his paper "Context as a Spurious Concept" (http://ftp.cs.toronto.edu/pub/gh/Hirst-Context-97.pdf) "In natural language, context is constructed by the speaker and the interpreter, and both have considerable discretion in so doing.".

When we use a logic deduction system to solve a natural language puzzle, we need to explicitly provide the contextual knowledge necessary for the solution. While in some cases like Schubert's steamroller no contextual knowledge is needed, this is not true in other cases like the zebra puzzle.

Translating the natural language puzzle into a formal language (CSP, Prolog, ...) we implicitly add contextual knowledge when we construct the respective data structures of the formal language, for instance in the zebra puzzle when we define the concept "left".

Considering the great variety of natural language puzzles each of which is embedded in its specific context and needs part of the contextual information to be solved by deduction, it seems impossible that there is a systematic, generally applicable way to find the necessary contextual information for any given puzzle.

It's more complicated. When you express a problem in some formal notation, in order to solve it by deduction or by constraint satisfaction, or mathematical programming or anything else, you need to capture *enough* of the semantics of the problem. Maybe your formal logic already gives you all you need, with a simple transliteration of the problem statement into uninterpreted predicate symbols (as perhaps in the Steamroller) but usually it doesn't because basic logic is a very thin theory. When the Zebra problem says there is a "row" of houses, you can't capture this taking "row" to be just any old uninterpreted symbol - it is required to represent a total order for one thing, so the logic of lists or arrays can be applied. Again, the fact that an animal is not a house is needed in some formulations of the Zebra puzzle and could be represented by an explicit assertion, or it could be incorporated by using a many-sorted logic and having different variables to range over the two domains. Maybe you use a logic in which these things are primitively available, or maybe you don't; in the latter case you have to supply them by adding some axioms.

Sometimes the deduction required is enthymematic, appealing to pieces of unstated background knowledge. The Jobs puzzle (http://www.mcs.anl.gov/~wos/mathproblems/jobs.html) is like that, for example. The fact that teachers are all educated past ninth grade is not an analytic truth - part of the semantics of "teacher" - but is just a fact that everyone knows. Similarly, that Pete is male and Thelma female and that there are no same-sex marriages in this little world are not provable theorems of logic but have to be supplied to get the reasoning to work. When we make up a logic puzzle, we are very much aware of this, and carefully design it so as to make the solver import background assumptions at given points.

The boundary between what is part of logic and what belongs to semantics is neither fixed nor clear. Nor, famously, is the boundary between analytic truths and empirical facts. Moreover, the connectives and quantifiers etc in a formal system are not exact copies of their analogues in natural languages. This is unavoidable, and a good thing: language is used in a vast number of subtle ways, whereas formal logic is not, and something simple and precise cannot be an accurate analysis of something complex and imprecise. Even in the artificial case of logic puzzles, the relationship between the formal and the informal is rough.

John

Your answer seems to second my statements, namely first that to solve a natural language puzzle you often need – beyond what is explicitly stated in the puzzle – contextual knowledge usually derived from the human sphere, and second that each puzzle requires its own specific contextual knowledge which prevents finding general solutions.

But you are also addressing a second issue, namely the relation between natural language and logic. Having developed Attempto Controlled English – a subset of English that can be translated into logic – I completely agree with you that formal languages are not capable of representing the fullness of natural language. However – again based on my experience with controlled languages – there are cases where natural language texts can be adequately translated into logic and then usefully submitted to logic deduction. Besides the already discussed logical puzzles, examples are technical texts like software specifications, simulations, rule-based systems like clinical practice guidelines, regulations, and ontologies. In each of these cases controlled languages translatable into logic help users who need formal reasoning but are not familiar with formal notations.

I concur with your statement "The boundary between what is part of logic and what belongs to semantics is neither fixed nor clear." In the case of Attempto Controlled English we took this boundary into account by leaving the meaning of the so-called content words (nouns, verbs, adjectives, adverbs) open to the interpretation by the human users.