What's New - November 2000

[Home]


November 30:  A palindromic number is one that reads the same from either end, for example 12321 or 4554.     Take any 2 digit number, reverse it and add it to the original number.  Is the number a palindrome?   If not, repeat the process until it is.   ((94+49=143, 143+341=484, a palindrome in 2 steps).  Which 2 digit numbers  require the most steps to a reach a Palindrome Sum?

November 29: Three new clever logo contest entries from Robert in South Africa were posted today.  Check them out and vote!   

I also reposted 15 Puzzle #2 with a minor correction to the hashing code.   For very long solutions, when the hash tables fill up, they are automatically expanded - in theory.  Now it works in practice too. 

November 28:  Whew!  15 Puzzle #2 is available.  That was almost too much fun.  It solves most puzzles in some fashion, although optimal solutions turn out to be very hard to calculate for large (5X5) boards.  It was discouraging to find a paper published in an Artificial Intelligence journal describing the first 10 random 5X5 board optimal solutions ever found.  Run times were from hours to months and board configurations evaluated ranged from 8 billion to 8 trillion per case!   I can guarantee that any  5X5's you solve with this program will not be optimal.  But probably still better than you can do by hand.   In any event, after 50-100 hours of work, I'm ready to for a new (and simpler) problem.    

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.    

 

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15  

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 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. 


 

I received an note from my son (an engineer) the other day informing me of an error in the Knight's Tour program.  If you click the "Let me try" button while the program is displaying its solution, bad things happen.   Engineers do make good beta testers.  Corrected code has been posted - instead of freeing and recreating the board when the user clicks "Let me try", a flag is tested first and flag is set to "manual mode".  The auto-solving loop also checks the  manual-mode flag and stops solving if the user pressed the button.

We have a new logo contest entry from Rachel - a bright young lady whose father, James, runs the excellent  Delphi Programming Source Code site.

November 6:  AirportSim, an airport simulation program is available.  It's a first step toward future explorations of discrete event simulation (airports, banks, gas stations, grocery stores, factories -  anywhere people or things show up for some service, get it,  and leave).    We can even count the number of  planes that run out of fuel while waiting to land. (No lives were lost in the creation of this program.)

 November 3: "Insert + and - signs as necessary into the string 123456789 to form an expression that evaluates to 100".    I received this problem yesterday in an e-mail from an 11 year old boy who says his teacher assigned it.  I told him that it would probably take me 2 hours to write the program, so if he would spend 2 hours working on it and send me his closest solution, I'd send him the program. I haven't heard back, but I couldn't resist coding it anyway.    How would you solve it?  Here's my solution, called  Expressions 100.

November 2:  Uli from Switzerland, just let me know that the Knight's Tour does not compile under Delphi 3.  Thanks Uli.  Apparently D3 doesn't support dynamic arrays (arrays that can change size at run time).   I've made a version that doesn't use dynamic arrays.  If anyone else has the same problem, let me know.   There may be other programs posted that use dynamic arrays or other features that didn't exist in earlier Delphi versions.   Please, let me know if you encounter problems using downloaded source code.

November 1:  Magic Squares #1 generates Magic Squares of odd size (up to 51x51).  This a simple introduction to another interesting mathematical niche.  (Magic Squares, in case you have never seen them, are square arrays of the integers from 1 to N2 arranged in an NxN matrix so that each row, column, and corner-to-corner diagonal sums to the same number. )   Another problem only made solvable because some smart mathematicians developed an algorithm a few hundred years ago.