June
27, 2002: More brain candy for the younger set. The SafeCracker
program represents an unusual safe. Each of the buttons
must be pressed in the correct order to open it. The
distance to move and the direction are indicated on each button. The
last button is marked "LAST". The safecracker's job
is to locate the first button and unlock the safe by clicking the chain of
buttons from first to last. (By the way, even though the
image at left looks computer playable, it's not, so save your clicking finger.
You can copy it to paper and try it though. You can also follow
the link above to download the executable or Delphi source
code for SafeCracker in order to generate and solve many puzzles of many sizes.)
June 20, 2002: One of the proposed changes
for the Traveling Salesman Program was implemented today. It was
just too good to resist, reducing
exhaustive search times for the 13 city closed route by 94% and increasing
the maximum practical search size by a city or two. See
the Further Explorations section at the bottom of the Traveling
Salesman Program page for more details.
June
18, 2002: The Traveling Salesman Problem is interesting because
it is easy to state but hard to solve. Given a set of
cities, plan a roundtrip for our salesman that visits all the cities and
minimizes the total distance traveled. This turns out
to be a very hard problem because of the explosion of possible paths as the
number of cities increases.
Examining all paths is probably only practical
up to 13 or 14 cities. Above that number we need heuristic algorithms
that give pretty good results. Lots of academics are
spending lots of time finding better solving techniques with some success,
but you won't find that code here. You can try your hand at
beating the heuristics in my Traveling
Salesman Program. Or benchmark your computer by timing an exhaustive
search for a 13 city path.
June
13, 2002: One of the early experiments in machine learning was a "machine"
which used matchboxes and colored beads to play tictactoe. It
was invented by Dr. Donald Michie over 40 years ago. 300 (or perhaps
304) matchboxes represent the the board positions presented to the
machine. For each move, a bead is selected randomly from the
appropriate matchbox. At the end of the game, wins are rewarded by
more of the winning beads and losses punished by confiscating beads. You
can train this computerized version of the TicTacToe
machine for yourself.
June 3, 2002: Here's an
Equation Search program that can be quite challenging to
play. Given four sets of four numbers each, find an arrangement
of the numbers combined with two operators to form an equation of the form
(N1 op1 N2) op2 N3 = N4 that is satisfied by each of the sets of
numbers. Operator choices may be restricted to from14 operator types
chosen from +, , ×, and ÷.
Problems are randomly generated by the program. Use all four operations and
allow number values up to 99 and it can take a while to "unlock the
code".
