Problem Description
Here is a solitaire version of the classical Battleships game
where, in addition to the ship quantities and types, you are supplied with
the number of ship parts hidden in each row or column and a few preplaced
ship parts.
Background & Techniques
I found this Battleship Puzzle in one of my favorite puzzle books: "Logical Puzzles"
,
2006, ChartWell Publishers. It is apparently out of print, but a few new and
used copies are available at the above Amazon link as of this date (June, 2009) .
There are about 10 puzzles of this type in the book, two of which have been
implemented here.
For each puzzle, the upper grid displays the number of ships and the number which have
not yet been displayed on the board for each ship type. The lower grid
is the playing board and represents the "sea".
The first row displays the total number of ship parts in each column and the
number which are currently displayed separated by a "/". Row
values are displayed in the first column. A few ship parts will
be initially displayed in their proper location.
You can use PrntScrn button or a window capture feature of any
image processing program to print the puzzle if you want to tackle it with
pencil and paper. To play on-screen, click the start square where you
wish to add a ship. A popup menu will allow you to select the
ship to add - only those which will fit at this location will be available.
Double-clock a ship on the board to remove it.
When all ships have been displayed, the "counts" column and row
will have equal "total" and "displayed" values and the "Available" column in
the upper grid will display all zero values.,
Non-programmers are welcome to read on, but may
want to skip to the bottom of this page to download
executable version of the program.
Notes for programmers
The data model for this puzzle turned out to be more complicated than I
recognized when I started working on it.
We have ship types with properties like Name, Length, Total #, and the
Available #. I made a TShipRec record type to hold this
information. The Ships array of TShipRec records
contains the information for a specific puzzle. When
a ship is placed, additional fields containing location and orientation
(vertical or horizontal) must be associated with each individual ship.
I chose to use the BoardGrid cells to contain a 3 character representation
of the ship type index in the Ships array, the orientation and an indication
of which part this cell represents. See below for details. Using
the cell for this info makes it easy to draw the proper shape in each cell
and also to count the number of parts used in each column and row.
Each puzzle contains some ship parts which are initially displayed.
These parts must be identified so that they do not block out adjacent cells
as normal placed parts would and so that they can be redrawn if the user
defines a ship here and later removes it. OriginalParts
is an array of TPieceRec records with column, row, and TPartType
information. A Placement array of TPieceRec records was
added to TShiprec records to hold the solution for each puzzle.
Lots of fiddly problems to solve as indicated by the list of the methods
defined:
Private Methods
 | procedure FormActivate: Call
MakeDefaultCase to display the initial puzzle. |
| procedure ShipGridDrawCell:
OnDrawCell event exit to display upper grid cells. Using the
ships[Arow] record it update shipname, total, and available columns
and calls DrawLeftEnd, DrawMiddle, DrawRightEnd as
appropriate to draw the ship for that row. |
| procedure BoardGridDrawCell:
OnDrawCell event exit to draw row and column values or the ship part
defined for this cell or the "unavailable flag. "X". Ships
parts are encoded as 3 character text values as follows:
 | s[1] = ship number or '?' for an
original part whcih ahs no assigned ship yet. |
| s[2] = Direction: "H" or "V".
"?" if unknown or not applicable (e.g. Destroyer with a
length of 1) |
| s[3] = Piece type
 | "F" first piece of a multi-piece ship |
| "L" Last piece of a multi-piece ship. |
| "S" Square; middle pieces of a
multi-piece ship. |
| "C" Circle for a one piece Destroyer.
|
|
|
| procedure BoardGridClick User
clicked on a cell to indicate that he wants to add a ship here.
The first problem is to determine which cell was clicked. Mouse.Cursorpos
plus ScreenToClient and MouseToCellrect methods take care
of that. This routine examines each of the 7 possible ship
orientations and sets the Visible property of a Popup menu TMenuItem
for that ship to true or false accordingly. Function
CanPlaceShipAt does most of the work in determining which result
applies. PopupMenu1 is displayed at the end of the routine.
|
| procedure PlaceShipClick; Called
when the user clicks one of the menu items. The Tag field of each
visible menu item has been code to contain the index of the ship and
direction entry, plus the row and the column where the ship is to be
places (tag=1000*column+ 10*row + menu item index). |
| procedure BoardGridDblClick: User
double clicked on a ship to remove that guess. |
| procedure DefcaseBtnClick:
Reinitialize the currently displayed case by call MakeDefaultCase
procedure. |
| procedure CheckBox1Click: Display or
hide indicators of cells which cannot receive ship parts. |
| procedure ShowMeBtnClick: Show the
solution for current case. Solution will display for one second on
the first click, 2 seconds on the 2nd click, etc. |
| {procedure MakeDefaultCase: Initialize and display one of the two sample cases. |
| procedure MakeShip; Called by MakeDefaultCase to make a
TShipRec from passed
parameters, add it to the Ships array and display it in the ShipsGrid
StringGrid. |
| function CanPlaceShipAt;: Test location
of the ship described by "ship" in direction
"dir" at (c,r) and return true if it can be placed there.
|
| procedure DisplayShip: Place a ship of
the specified type in the specified direction starting at the specified
column and row. |
| function IsOriginalpart): Check if the
ship part in this square was part of the original puzzle definition and
therefore must remain visible even if a ship containing it is removed
from the board. |
| procedure UpdateAvailable: Decrement
count of ship parts of specified type are still hidden after a ship is
displayed, increment the available count for that type if one is
removed. |
| function IsSolved:boolean: Check if all
ships have been displayed (available counts are all 0) and return
True if so. |
| procedure UpdateUsed: Update column and
row used counts - called after a ship has been added or removed fro m
the board. |
| procedure FlagUnavailable: Identify and
flag squares which cannot be hiding a ship |
| Procedures which draw parts of a ship,
oriented as specified in the cell text code:
| procedure DrawLeftEnd |
| procedure DrawRightEnd |
| procedure DrawMiddle
|
|
