Delphi For Fun Newsletter #8
Sunday, Nov 19, 2000
Another busy week hunting and working on the darn 15 Puzzle. The Bambi's are all safe (so far). The 15 Puzzle turns out to be one still being used for Artificial Intelligence research. I've found several PhD theses that reference the puzzle when discussing search techniques, heuristic finding, planning, etc. I'm going to give it one more week and then publish what I have as a research project for others to carry on.
Here's what I've posted since last time:
November 16: I've been working on the auto-solve capabilities for the 15 Puzzle all week. So far, it solves OK up to about 25 moves, but bogs down after that. The algorithm I'm using is one called A* (AStar) which tries to find almost optimum solutions for hard problems in a reasonable amount of time. I can't beat it in terms of number of moves to solve - when it can find the solution. But I can, by hand, at least always find a solution, optimum or not, in a matter of minutes. I may add a 2nd "Solve" button using more human-like techniques to handle cases where AStar doesn't work well. I also need more work to make sure that my current AStar implementation isn't buggy. Fun, fun.
In the meantime, I posted the MinMax problem today. It's a small mind bender, easy to answer with pencil and paper, slightly more difficult to solve in your head. But it does introduce a few coding techniques.
November 11: The 15 Puzzle. This ancestor of the Rubik's Cube was popularized by Sam Loyd, a well known puzzlist in 1870. Fifteen sliding tiles are moved around a 4X4 board to produce a specified arrangement. The fact that Loyd's set up instructions made the puzzle unsolvable gave him lots of press but no one ever claimed his $1000 reward for a correct solution. What a surprise! This is version 1, with a program smart enough to respond to your attempts to solve it, but too dumb to solve the puzzle itself. I'm working to make it smarter though. Maybe next week.
November 9: Seven Coins is a little coin moving puzzle. The program is probably more complicated than could be justified by the effort of solving by hand. But it is an interesting exercise in how to represent a graph in code.
"Don't give up at half-time. Concentrate on winning the second half." -- Coach Paul "Bear" Bryant (Football coach)