abbott@aero.ARPA (Russell J. Abbott) (12/17/88)
Recently a friend and I were discussing the old puzzle that requires one
to draw a line consisting of (no more than) 4 line segments through the
following points without lifting the pencil from the paper or retracing
part of the path.
o o o
o o o
o o o
The trick, of course, is not to limit the line segments to the rectangle
defined by the corner points, for example:
o--o--o--/
\ /
\ /
o o o
| \/
| /\
o o o
| /
|/
When I first saw this puzzle, I felt cheated because the solution was
not within the bounds that I had assumed had been defined. My friend
(Dan Kalman) argues that the limitations that the naive solver imposes
on himself are not stated in the puzzle. Not only that, but much of the
work we do exists within unclearly specified contexts, and one aspect of
intelligence is to see that one is not limited by boundaries that aren't
really there.
How does this relate to AI? The general question is whether there is
some way of designing a program that can go beyond the implicit
boundaries of the problems it is supposed to solve. There is an
immediate difficulty since in expressing a problem to a program, one is
forced to specify the problem. So the question becomes: how can one
present this or similar problems to a problem solving program in such a
way that the possibility of discovering the insightful solution is
present, but the problem statement doesn't lead to it directly?
If this problem were presented as that of drawing four line segments
through 9 points in a plane, then the solution is easy. There is no
implicit limitation to the rectangle defined by the corner points.
An alternate formulation is to present the problem as 9 nodes in terms
of which one is supposed to define arcs for some yet-to-be-defined
graph. In these terms there is no solution (as the naive problem solver
suspects)--unless one adds additional nodes, which is the insight. This
second approach also requires that one define the notion of "colinear"
arcs. But if colinear arcs are defined only in terms of the given 9
nodes, there is no way to add new nodes that are colinear with any of
the existing nodes. So a more general notion of colinear is needed,
e.g., in terms of the nodes as embedded in a plane.
So, suppose a problem solving program "knows" about both planes and
graphs and also knows that graphs may be defined in terms of points in a
plane. Two arcs may then be defined as colinear if their endpoints in
the plane are colinear. Then, one could present the problem as that of
building a directed graph that defines a path through the given 9 points
in a plane so that the path consists of a sequence of (no more than) 4
subpaths, each of which consists exclusively of colinear arcs. (Sounds
like a complex problem statement!)
The preceding appears to be a problem formulation that allows the
problem to be solved without giving the solution away. In order to
solve it the system must still come up with the idea of adding new
nodes; yet there is nothing in the problem statement that leads to the
operation of adding nodes.
It would appear then, that a system could solve this problem only if its
repertoire of arc creation operations (which is what the problem
requires) includes the addition of new nodes. But if that were the
case, the insight is built in and hardly an insight. If the addition of
new nodes is not built into the system's repertoire of arc creation
operations, then is there some other heuristic that would lead to the
solution of this problem?
A natural question at this point is whether anyone knows of a system
that could deal with such a problem--on the level on which it is
intended.
-- Russ Abbottbph@buengc.BU.EDU (Blair P. Houghton) (12/18/88)
In article <43353@aero.ARPA> abbott@aero.UUCP (Russell J. Abbott) writes: >An alternate formulation is to present the problem as 9 nodes in terms >of which one is supposed to define arcs for some yet-to-be-defined >graph. In these terms there is no solution (as the naive problem solver >suspects)--unless one adds additional nodes, which is the insight. This >second approach also requires that one define the notion of "colinear" >arcs. But if colinear arcs are defined only in terms of the given 9 >nodes, there is no way to add new nodes that are colinear with any of >the existing nodes. So a more general notion of colinear is needed, >e.g., in terms of the nodes as embedded in a plane. If I may, this sort of situation came up at the Pub the other day. We settled on it's being the distinction between the mathematical fields of Topology and Geometry. I.e., the nodal description is strictly topological, and the solution requires a geometrical formulation, to wit, your statement "embedded in a plane". It took a half-drunk MS candidate, a near-sober Ph.D., and an easily sloshed Ph.D. to get the distinction straight. >A natural question at this point is whether anyone knows of a system >that could deal with such a problem--on the level on which it is >intended. Sorry, but I don't. It seems from your posting that even overeducated humans have trouble with it, so an artificial system that could solve it would be a curious bird, indeed. --Blair "Is Usenet therefore topological or geometric, taking economics (costs) into account? And does it affect the cost of Harpoon Winter Ale?"