Klingon Paths

[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. We receive a few cents from each purchase.   Thanks.

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

Problem Description

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

A Klingon can traverse squares horizontally or vertically, but not diagonally.  What is the longest path a Klingon can take without dying?"

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:

  • Temporarily change the size of the component to print size and redraw it that size.  In the case of StringGrid, the parameters that required changing were Width, Height, DefaultColumnWidth, DefaultColumnHeight, and Font.size.
  • Send it to the printer using the "PaintTo" method, 
  • Restore component its original size.  

Running/Exploring the Program

Suggestions for Further Explorations

Add user play -  either let the user click to define a path or make it a game, perhaps alternating turns between two players or a player and the computer.    Player who blows up the Klingon is the loser.
Grid values are currently limited to to the range 1 to 25, primarily to limit path lengths (clearly no path may exceed 25 ,moves) I assume.    This number of possible value could be an input to the program.   
In his book, ,Pickover suggests several other explorations.   

 

Created: July 13, 2003

Modified: February 18, 2016

 

 

  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright 2000-2017, Gary Darby    All rights reserved.