ZIP program description

download ZIP program

download ZIP project

ZIP is a puzzle introduced by Linked-In.
A new puzzle is supplied daily.
Below is pictured a ZIP puzzle: left in the unsolved- , right in the solved state.

The ZIP help information is found [HERE]

This article is a description of the ZIP Delphi program.

Data formats

type TZipCell = record
                 nr       : byte;  //entered number in cell
                 borders  : byte;  //1:right; 2:up; 4:left; 8:down
                 entrydir : byte;  //cell entry direction 1,2,4,8
                 exitdir  : byte;  //cell exit direction 1,2,4,8
                 next     : byte;  //next cell in path
                 previous : byte;  //previous cell in path
                end;

var game : array[1..100] of TZipCell;
    Hsize : byte = 6; //column count
    Vsize : byte = 6; //row count 
    firstcell : byte; //cell that holds number 1
    lastcell : byte;  //cell that holds last number 
    lastNr : byte;    //last number of path (2,….)

Cell numbering is 1 dimensional

Horizontally adjacent cells differ 1, vertically adjacent cells differ by Hsize value.
Borders:

The border coding is also the direction of the path in a cell.
A 1 indicates a border, 0: no border.
Note: (game[cell].borders and direction) = 0 indicates free path, no border.

Drawing the ZIP puzzle

A cell may be empty, contain a number and may be part of the path.
While drawing the path, numbers and borders may not be affected.
This is ensured by splitting the image over 2 bitmaps:
Bitmap map1 contains the grid, a number and borders.
map2 contains the path.

map2 is drawn on paintbox1 on form1 to become visible.
The background color of map1 is white, which is set as transparentcolor.
So, when drawing map1 in map2, the path in map2 is not overwriiten by white but is overwritten by a number.
When drawing an individual cell, first the map1 cell is copied to a bitmap (called transparentmap)
with the dimensions of 1 cell.
Then this bitmap is drawn on map2 and the map2 cell rectangle is copied to the paintbox.
Reason is that the canvas.copyrect( ) method does not support a transparent color.

Drawing and registrating a path

A path is registered as direction to the next cell.
The path from cell 5 to cell 9, so direction 8, is registered as
- game[5].exitdir := 8
- game[9].entrydir := 8
- game[8].next := 9
- game[9].previous := 5
This is somehat double. It may speed up things, but this was not verified.

The manual drawing proces proved to be a litle more complicated than expected.
The easiest way would be simply connecting cells but this involves long mouse moves
and causes abrupt path changes.
I decided to connect adjacent cells in three steps.

Below are pictured 2 cells. A path is to be drawn from oldcell to newcell.
Six areas comprise a cell. The purple shaded area has value 0.
Mousemoves over this area are ignored.
Also a mousemove over the same grey area is ignored.
Actions only take place when moving into a new grey area.

Drawing starts by a mousedown event on area 7 of a cell. This cell is called OldCell.
Then, while moving the mouse toward newcell, area 1,2,4 or 8 is encounterd.
This area number becomes the direction, saved as OldDir.
From this direction newCell is calculated.
A counter dcc (draw control counter) controls the process. dcc starts at value 0 and becomes 1 after a mousedown on area 7.
Moving into area 1,2,4 or 8 draws a partial path if there is no border between
the cells and newcell holds no path already.
dcc is set to 2.
Moving the mouse further and reaching area 4 in newcell extends the path and increases dcc to 3.
Moving further and reaching area 7 of newcell paints the full path between the cells.
The oldcell properties next and exitdir are set,
of cell newcell properties previous and entrydir are set and oldcell gets the value of newcell.
dcc is reset to value 1.
This proces is repeated to connect further cells, extendig the path.

Complicating factors are:
1. the mouse movement may be reversed, so the dcc must decrease while the partial path
between the cells is shrinked.
2. mouse movement may be to the previous cell of the path which erases the connecting
path between the cells.

Variables for path drawing and low level support routines:

var  dcc : byte;        //draw control code
     oldCell : byte;
     newCell : byte;
     oldArea : byte;
     oldDir : byte;
         
function GetCellRect(nr : byte) : Trect;//return rectangle of cell 

function XY2Cell(x,y : word) : byte;//return cell number of mouse      
                                    //coordines (x,y)

function XY2Area(x,y : smallInt) : byte;//return area of cell for 
                                        //mouse coordinates (x,y)

Higher level routines:

function Connection(var nextcell : byte; cell,dir : byte):boolean;

//from cell and dir (direction) nextcell is calculated.
//if no border between cells , exit true if nextcell holds no path or is previous cell of path.

procedure paintPath(cell,dir,L : byte);

//from cell, in direction dir, paint path of lenght L.
//L=1: 15 pixels; L=2: 30 pixels; L=3: 50 pixels (full path to next cell);
The drawing of a path is controlled by :

type TmouseAction = (maDown,maMove,maUp);

procedure drawProc(ma : TMouseAction; x,y : smallInt);
//X,Y:from mouse events

This procedure uses nested case statements.
1st case : mouse events
2nd case : dcc values controlling path changes.

On a mouseup event a check is made for a solution.
This is done by

procedure checksolution;

checks made are for:
- path complete, no empty cells.
- numbers of cells are sequential on the path.
- last cell of path must hold highest number.

Initializing the game

For a new game, the maximum area of paintbox1 is erased on the form1 canvas.
Then the size of map1,map2 and paintbox1 must be set.

procedure recalcbox1;

Other procedures involved are:

procedure setEdgeBorders;//set borders in outer cells

procedure UpdateBorders(x,y : word);
//sets (erases) borders of cells in new mode 

procedure paintCellborders(cellNr : byte);
//paint cell borders of cellNr in map1

Finding a solution (solve button action)

Pressing the solve button in Play mode erases the current path and starts the search for a solution.
This code is found in the zip_unit.

Type  TSearchState = (ssStart,ssTimeout,ssSolution,ssEnd);

procedure Solve(var sst : TSearchState);

local variables in solve procedure:

var cell : byte;//current cell number
    dir   : byte; // direction 1,2,4,8 
    path: byte; //next number expected on path.
    distance : byte;//cells to go to end of path
    Xcell    : byte;//temporary cell nr
    Ltest    : boolean;//true if last number reached
    Dtest    : boolean;//true if all cells covered
    timer    : longword;//used for time-outs

The search process is of the type “brute force” which means trying to find the path without analytical reasoning.
A solution is that the exitdir fields of each cell point to the next cell of the path.
So a solution is a sequence of exitdir values.
However there is one check to avoid superfluous work, getting lost in wrong branches.
This check is performed by:

function entrycount(bcell : byte) : byte;//return entries into 
                                         //cell bcell

Since a path needs 2 entries in a cell (except for the first and last cell)
a game with an isolated cell (having only one entry) cannot be solved.

Early detection of this situation saves much time.
Example: A search time of 60 microseconds (easy puzzle) became 1700 microseconds without the isolated cell check.
Normally, difficult puzzles solve in around 1 milliseconds time.

Pressing the solve button calls procedure SolveProc in unit1.
Variable searchbusy is set true.
Variable searchstate is set to ssStart and the solve procedure in the zip_unit is called.
The solve procedure exits with searchstate ssEnd (no solution), ssSolution or ssTimeOut.
Pressing the stop button clears searchbusy and the search terminates.

The solve procedure is first called with sst = ssStart.
Variable timer is set to 1000000 to be decremented for each trial move.
When reaching zero, the local variables are saved and solve exits with sst = ssTimeout.
After re-entering solve with sst = ssTimeout, the saved variables are restored and the search continues.

PreCheck

When the precheck box is activated, when entering play mode a simple check is made for an unsolvable game.

In above 4*4 game, 16 cells have to be covered.
The left picture shows the shortest path.The length is 5 cells.
In the right picture this path is extended to 7 cells.
Path extension is always by 2 cells minimal.
This means: the number of cells minus the shortest path length must be even.
If odd, no solution is possible.

Search flow chart

Next a zip puzzle that takes more time to solve:

This concludes the description of the ZIP solver.
Please refer to the source code for details.