From: rhinoceros (rhinoceros@freemail.gr)
Date: Sat Feb 28 2004 - 19:45:49 MST
About the eight 8s puzzle again:
[Mermaid]
how will you write a computer program to get the solution for this problem?
[rhinoceros]
There is one slow and certain way to find all the solutions of any such problem with the help of a computer. Remember Goedel's incompleteness theorem? We have talked a lot about it here. Well... in the first part of his proof, while trying to lay down the problem, Goedel devised a method of enumerating all possible arithmetic expressions. This method takes into account the numbers and the symbols of any arithmetic expression as well as their arrangement and produces a unique serial number for any arithmetic expression. It is a proven and thorough method and (in theory) one can use it to step through all arithmetic expressions which satisfy some criteria and check them.
The only problem is that -- if we really want to get results in a reasonable time -- this method sucks.
A brute force computer method would do something similar to this, producing search trees by sprouting branches of possible arithmetic expressions and checking them. The efficiency of the program depends on how good it is at ignoring many branches without even checking them and proceeding straight to "the right" branches.
In the field of Artificial Intelligence, where the experts have been trying to take advantage of "the human way" of reasoning, a lot of work has been done on software agents and heuristics.
Software agents act either randomly or in response to what they (or other agents) have found so far.
A heuristic is essentially a metric or a "utility function" which tells an agent "how close" to the solution it has reached. In the case of the eight 8s problem, for example, we might use a heuristic function which would take maximum values when we approach 1000 by using a paticular combination of eight 8s. It is not so simple of course... there can be "local maxima" which do not really lead to a solution (there is a whole methodology called "hill climbing": the top of a hill is not necessarily a solution -- it can be a dead end from where you can't go higher, and the agent must decide to head downhill again).
Well, maybe I am just babbling and all this is not really necessary for solving the eight 8s puzzle. There is a way to know. Just solve the same problem with eight 8s giving a sum of 700 instead of 1000. I just made it up myself, so you can't google it. :P
I didn't look into the 10 divisions problem yet. I hope I will find some time for that. It looks discouragingly interesting.
---- This message was posted by rhinoceros to the Virus 2004 board on Church of Virus BBS. <http://virus.lucifer.com/bbs/index.php?board=61;action=display;threadid=29971> --- To unsubscribe from the Virus list go to <http://www.lucifer.com/cgi-bin/virus-l>
This archive was generated by hypermail 2.1.5 : Sat Feb 28 2004 - 19:47:57 MST