Path: news.media.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!agate!anarres.CS.Berkeley.EDU!bh
From: bh@anarres.CS.Berkeley.EDU (Brian Harvey)
Newsgroups: comp.lang.logo
Subject: Re: Possible project for youngster
Date: 28 Dec 1993 17:39:11 GMT
Organization: University of California, Berkeley
Lines: 46
Message-ID: <2fpqvv$61s@agate.berkeley.edu>
References: <1993Dec28.133655.17705@Lehigh.EDU>
NNTP-Posting-Host: anarres.cs.berkeley.edu
Keywords: backtracking memory youngster

logant@lafcol.lafayette.edu (Logan Tracy H) writes:
>Recently a 5th-grade teacher tried a puzzle on me: five persons
>live in five row-houses, of five colors....
>
>My original attack was to assign everyone some permutation of all properties
>and then test against the specs ("the person in the green
>house has a dog"), but that method ran out of memory, so I tested
>as soon as I assigned enuf relevant properties.

I don't think you should have to do this by backtracking.  The best way
to solve the problem by computer is the same way you'd solve it on
paper: make inferences from the things you know.  There is a program to
solve one of these puzzles in the third volume of my Computer Science
Logo Style, in the discrete math chapter.  (The program solves a
specific puzzle, but its subprocedures are general and could be used with
a different top-level procedure to solve a different puzzle.)

In principle the right way to solve these problems is with a general
predicate logic language like Prolog, but because of the finite universe
(in your problem, only five people, five houses, etc.) we can get away
with simple propositional logic, and that means we can reach *all* the
relevant inferences from the things we know in finite time.

Have you seen the grids that people use to solve these problems on paper?
You draw arrays of boxes with the names of things on the edges, e.g.,
people's names on the rows and house colors on the columns, and then you
put in checks or crosses as you find out stuff.  You make a grid like
that for every pair of properties.  The rules of inference are these:

1.  If you put a check in a box, put a cross in every other box in the
same row or column.

2.  If a row or column has n-1 crosses, put a check in the remaining box.

3.  If A-check-B and B-check-C, then infer A-check-C.

4.  If A-check-B and B-cross-C, then infer A-cross-C.

I did indeed use property lists.  The data structure is pretty complicated;
I found it useful to include some redundancy, so that, for example, if
Smith lives in the yellow house and has a dog named Rover, I do
	pprop "smith "house "yellow
	pprop "smith "dog "rover
	pprop "smith "known [yellow rover]
	pprop "smith "category "person
and so on.