Solving problems with some help
Version 1.2, Jan 8 2009
by leonardo maffi
Keywords: AI, intelligent interfaces, chakasa, problem
solving.
[Go back to the index]
Note: in this text "AI" means some smart artificial system, not specifically
a sentient artificial mind as HAL9000 and the like. So an ORC system to convert
a scan into ASCII text too is a form of AI.
This page by Erich Friedman is filled with many different puzzles, many of
them are nice:
http://www.stetson.edu/~efriedma/puzzle.html
I am very lazy and I like to program, so I like computers to work for me. So
I like to solve such problems with a computer, writing some programs.
Now in particular I have taken interest in this group of puzzles, "Number
Link":
http://www.stetson.edu/~efriedma/numlink/
Its rules:
- Each digit in a triangle should be the first digit of the product of neighboring
digits.
- Each digit in a square should be the last digit of the product of neighboring
digits.
- Each digit in a pentagon should be the first digit of the sum of neighboring
digits.
- Each digit in a hexagon should be the last digit of the sum of neighboring
digits.
- There are no restrictions on numbers contained in circles.
Such group of puzzles doesn't look much complex, I presume lot of people are
able to solve them in a short time, but I haven't even tried to solve them by
hand :-)
Chakasa (finctional creatures that I have invented with a friend, described
elsewhere in my site)
have bionanites inside, they have several purposes, and a percentage of such
bionanites are able to compute, in parallel. A chakasa has some limited ways
to interact with hir nanosystem. I presume some chakasa like to run some kind
of AI on their nanosystem (I call it nanoAI), other just want to run a group
of smart agents able to do a limited number of specialized things, and some
other chakasa may like to keep it almost off all the time (my experience has
shown me that lot of people don't like to have a second intelligence inside).
How can a chakasa use the nanoAI to solve the Number Link problems?
A first way is to ask the AI: "Solve this!", but:
- it's a boring way, because it skips some complexities
- it teaches nothing to the chakasa (so hir brain may become really lazy. You
may end with a dumb chakasa that is kind of the animal "pet"/puppet
of the AI inside hir. That's not what I want).
- You have just moved the problem to solve the problem from a mind to another
mind. So now you need to say how such AI mind can solve the problem.
- You need a powerful AI, almost as intelligent as a person (well, some intelligence
has to be quite developed, but not all of them). But I prefer to think about
a simpler AI, unable to do everything. It's also more interesting from a literary
point of view (I like to write about the chakasa nanosystem too in my stories).
So let's start over :-) First of all I can write a small program to solve this
class of problems. I use Python because it's one of the best languages you can
find. One of such problem Number Link problems can be represented with a undirected
graph, where a node can be one of five classes. I have created a Graph class
to represent graphs and able to compute some graph-related things:
http://www.fantascienza.net/leonardo/so/graph.zip
The problem Number Link seems perfect to be solved by a general Constraint
System Problem solver, that is an AI. I have written a wrapper around one simple
example of such solvers (by Gustavo Niemeyerby, derived from ideas and code
by Norvig, a famous AI expert):
http://www.fantascienza.net/leonardo/so/csp.zip
So now I don't need to actually solve the problem, because the CPS solver is
supposed able to do it by itself :-) I just need to define the problem space
and its constraints.
The end result in Python is very simple. The almost-enum is ugly and the code
be nicer, but this probably is able to solve all the problems in that page (the
following code encodes only the first problem of the page):
-----------------------------
from graph import Graph
from csp import Problem, timing
# ugly homemade enum
triangle = 1
square = 2
pentagon = 3
hexagon = 4
circle = 5
problem_vars = "abcdefghi"
type_map = {triangle: "triangle", square: "square", pentagon: "pentagon",
hexagon: "hexagon", circle: "circle"}
def create_graph(node_types, arcs, dolog=False):
g = Graph()
for i, node_type in enumerate(node_types):
g.addNode(problem_vars[i], node_type)
for n1, n2 in arcs:
g.addBiArc(problem_vars[n1-1], problem_vars[n2-1])
if dolog:
print "Problem graph:\n", g
print "\nNode types:", dict((node, type_map[g.getNodeData(node)]) for node in g)
print
return g
def solve_number_link_problem(node_types, arcs, dolog=False):
g = create_graph(node_types, arcs, dolog)
if dolog:
print "Rules:"
p = Problem()
p.addvars(problem_vars, range(1, 10))
for node in g:
node_type = g.getNodeData(node)
out_nodes = g.outNodes(node)
local_nodes = out_nodes + [node]
if node_type == triangle:
rule_part = 'int(str(%s)[0])' % "*".join(out_nodes)
elif node_type == square:
rule_part = '(%s) %% 10' % "*".join(out_nodes)
elif node_type == pentagon:
rule_part = 'int(str(%s)[0])' % "+".join(out_nodes)
elif node_type == hexagon:
rule_part = '(%s) %% 10' % "+".join(out_nodes)
elif node_type == circle:
rule_part = ""
if rule_part:
rule_str = "lambda " + ",".join(local_nodes) + ": " + node + " == " + rule_part
if dolog:
print rule_str
p.addrule(eval(rule_str))
p.alldifferent()
if dolog:
print
return timing(p.solutions)
node_types = [pentagon, pentagon, hexagon, hexagon, triangle, circle, square, square, square]
arcs = [(1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 7), (5, 8), (7, 9), (8, 9)]
solution, time = solve_number_link_problem(node_types, arcs, dolog=True)
print "Solutions:\n", solution
print "\nSolved in:", time, "s"
-----------------------------
You can also download that Python code.
As you can see I have assigned the "a" to "i" names to
the polygons of the graph:
You can also see I have had to use "eval" to create a lambda function (that
represents a constraint) on the fly. Probably there are ways to avoid the need
of using eval here (maybe stating explicitly the list of arguments each lambda
accepts, giving to all such lambdas the full array of vars as input argument
and using vars[i] to represent a variable into the lambda body).
Setting the dolog=True this is the output, that is correct, computed in just
0.05 seconds:
-----------------------------
Problem graph:
a-b,c b-d c-d,e,f d-g e-h g-i h-i
Node types: {'a': 'pentagon', 'c': 'hexagon', 'b': 'pentagon', 'e': 'triangle',
'd': 'hexagon', 'g': 'square', 'f': 'circle', 'i': 'square', 'h': 'square'}
Rules:
lambda c,b,a: a == int(str(c+b)[0])
lambda a,e,d,f,c: c == (a+e+d+f) % 10
lambda a,d,b: b == int(str(a+d)[0])
lambda h,c,e: e == int(str(h*c)[0])
lambda c,b,g,d: d == (c+b+g) % 10
lambda i,d,g: g == (i*d) % 10
lambda h,g,i: i == (h*g) % 10
lambda i,e,h: h == (i*e) % 10
Solutions:
[{'a': 5, 'c': 4, 'b': 1, 'e': 3, 'd': 7, 'g': 2, 'f': 9, 'i': 6, 'h': 8}]
Solved in: 0.05 s
The encoding of the first problem (problem and image from Erich Friedman,
image adapted):

The result:

-----------------------------
The problem may be seen solved, but creating such input data requires some
time, and you can think about other kinds of problems that the chakasa must
solve in a very short time. So it's better to automate the conversion.
Input data, now created manually:
node_types = [pentagon, pentagon, hexagon, hexagon, triangle, circle, square,
square, square]
arcs = [(1, 2), (1, 3), (2, 4), (3, 4), (3, 5), (3, 6), (4, 7), (5, 8), (7,
9), (8, 9)]
Today a solution to that is to create a program able to scan the problem image,
locate the polygons and the arcs, and use this to create the problem as a graph,
that can it can then feed to my proggy, that uses the CPS solver.
Today this is well possible, there are programs able to do such things, like
OSRA, an optical chemical structure recognition program:
http://cactus.nci.nih.gov/osra/
but it may require lot of time and coding with (simple) image recognition algorithms.
I assume a nanoIA may already have inside subsystems more refined than OSRA,
that can be used as building blocks.
So a chakasa that wants to solve quickly many such problems (or other kinds
of problems that are more important than silly puzzles) may use some interactive
way to explain the nanoAI how to extract clean data from a class of stimuli
(eg. images), then in some way shi can create the equivalent of my Python program
(maybe using some kind of visual interface). Such software can use already existing
solvers as building blocks (or of course shi can even invent a new solver, specialized
for a class of problems). The end result is essentially a new agent of the nanoAI,
able to solve another class of problems.
Then faced with that class of problems a chakasa can just look at the solution
given by the nanoAI.
If the problem is uncommon it may be a waste of time to create such agent. If
the class of problems is too much large or not well defined or it can have too
much different forms, then a chakasa has to use hir intelligence to solve the
problems (the chakasa brain has few some tricks and subsystems that may help
for this).
--------------------------
silent80196 from the AnthroLitArts has asked something, that has lead me to
add few more comments:
For a Chakasa to have a too much smart nanoAI is a risk, because shi can become
too much stupid.
Because to have and develop a good brain you must keep using it all the time,
especially on hard-to understand problems and ideas.
If you let something else (like a nanoAI) solve many of your problems, especially
when you are a child, then your brain probably becomes "lazy", and
in the end you don't become smart at all.
(To avoid a similar risk I have made their very-long-term memory bad (= very
slow recall) on purpose to avoid them to try to solve too much problems using
memory instead of intelligence. Experience shows that humans with lot of memory
grow dumb because of this).
Even letting a CPS system solve those little number problems doesn't help keep
the brain exercised. So every design decision is a matter of balance between
the good and bad effects in a specific setting.
[Go back to the index]