December 19, 2000: A couple of demo
programs are available for download from a new Math Topics article on
Graph
Searching. The article describes the use of "depth
first" and "breadth first" searching for solutions of
puzzles which can be represented as graphs. SimpleSearch
demonstrates the techniques with a trivial graph and CoinSearch
finds solutions to the Sliding Coins puzzle. A quick and dirty TicTacToe
Count program is also included which generates all valid board
configurations for tic-tac-toe (I think). I get slightly over 6000
valid boards assuming X moves first. If anyone can verify or
correct this number, I'd appreciate it.
There was a show today on the History Channel about the
Apollo 13 accident and what it took to get it safely back to
earth. One step was a precision "burn" of the rocket
engines to get the ship to swing around the moon and slingshot back to
earth. That might make an interesting animated graphics
Physics program. Hmmm.
We're off to my daughter's for Christmas, so postings are
on hold for a week or so. Here's wishing everyone a happy
holiday season.
December 14, 2000: Well, another 4-day Sabbatical
has passed, working on the Sliding
Coins puzzle this time. Place 3 dimes and 2 quarters in a row like this
Then rearrange the coins to look like this
by sliding adjacent Quarter/Dime or Dime/Quarter pairs of coins to a
new location. No reversing the order of the coins while
dragging! This is more of a program about drag drop processing than
solution searching but worthwhile if you've never wrestled with drag
images. I also developed some good material on
searching adjacency list representations of graphs. I'll be
posting that in a day or two.
Note to H.R. Nazif. I have some
information for you, but you forgot to include an email address in your
feedback response. Try again.
December 10, 2000: Two postings today.
Pi Calc #1 is a
Beginners program that estimates Pi by shooting cannonballs randomly into a
square field that just contains a round pond and counts how many of the
total land in the pond. Pi is the Greek letter
p, our letter P,
which they used as an abbreviation for perimeter. Since Pi is
the ratio of of the distance around a circle to the distance across, I
guess it makes some sense. No fancy graphics here - it
takes a million or so shots to get a good estimate, by which time the pond
is full and the field is pretty well buried in cannonballs.
Spring Mass #1 is
a new program introducing the physics of spring mass systems. It
animates the motion of a spring with a weight hanging from it when you give
it a bump or stretch and release it. About 300 lines of code
puts it in the Intermediate category, but most of that is just setting up
the data. The animation loop has about 30 lines of code. Would
it work in zero gravity?
December 6, 2000: BruteForce
solves a class of problems with integer solutions. As the name
implies, it uses trial and error to search for solutions. Word
arithmetic problems, Magic Squares (well 3X3 and 4X4), and others like the
Bookshelf Problem, the Olympic Rings problem, and many others.
Check it out.
|