[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
"This grid of numbers is Klingon City and it's a tough place to live.
Each Klingon inhabiting this world carries a bomb on his hip as a testament to his courage. As a Klingon walks through the grid of squares,
his bomb records
the number of each square visited; if the bomb is exposed to that number a second time, the bomb explodes and the Klingon dies.
Background & Techniques
I found this problem in a book I recently acquired: " Wonders of Numbers" by Clifford Pickover, published by Oxford University Press, 2001. It's a great book with lots of new material and many of the problems are computer solution friendly. In fact a number of them have references to a web site with Basic or C code solutions.
This implementation just searches for the longest path for the given city. A Reset button forgets the existing path and prepares to start over. A New Random Grid button generates additional cities randomly. A Print button prints the current grid image on the default printer for further study if desired.
Technically, the search is a straightforward depth-first search for solutions using the magic of recursion. There are probably two dozen programs posted here at DFF now with similar searches, so maybe I'm finally getting the hang of it. This one went in pretty simply in an hour or so, considerably less than the time spent doing the documentation. Procedure MakeMovesFrom is the heart of the search. Passed a column and row location on the grid, the procedure searches all four directions for a valid move (valid defined as: in the grid and value not previously encountered). If found, we just add that move to the path and call ourselves with the new point as the starting point. Before doing that, we also need to check if this is a new maximum length path and save the information if it is. When we return from the recursive, we remove the point that was added from the path, etc. and continue checking.
The maximum path information is used in an OnDrawCell exit in the Stringgrid1 board image to color the background of each cell in the path as they are redrawn. An call is made to the grid's Invalidate method whenever a new longest path is found to force a complete redraw of the grid.
I added the Print button in part just in case some viewer wanted to work on finding the path on its own, or to play the game suggested below. The other reason was to determine the minimum amount of code to accomplish the task. By using the default printer and making assumptions about the size of the image to be printed, we can get by with three steps:
Running/Exploring the Program
Suggestions for Further Explorations
[Feedback] [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby All rights reserved.