If you shop at Amazon anyway, consider using
this link. We receive a few cents from each purchase.
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.
e-mail with your comments about this program (or anything else).
Numbrix™ is a puzzle currently (September, 2008)
being published in the "Ask Marilyn" column of the weekly Parade Magazine
and daily in the "Fun and Games" section of the
Parade Magazine website.
The puzzle board is a square array of cells, 7x7,
8x8, or 9x9 in puzzles seen so far. For a puzzle with N cells per
side, the objective is to fill the cells with integers from 1 to NxN contiguously with
each number after the first adjoining the next lower number vertically or
horizontally. Some of the numbers are pre-filled and the user's
additions must interface with those to keep the entire number chain in
A Numbrix Puzzle
Background & Techniques
The puzzles are satisfyingly solvable, some would say "too easy"
but I enjoy them more than Sudoku. Several sample puzzles are included
in the program which may be accessed with the Load button
You can solve the puzzle yourself by entering numbers
in available squares (any that are not prefilled). The Check button will verify any trial solution. If you want some help,
the Fill forced locations button will fill in
all numbers which have only one valid location based
the geometry of pre-filled values. Each click will make
one pass through the board filling additional numbers if
The Solve button does a depth-first search search for a
solution, backtracking for each dead-end path it tries.
Solve time is displayed in seconds or milliseconds so
you can observe the effect of pre-filling the forced
locations on solution times if desired.
Controls used for debugging were left in place for future
changes/fixes but are normally invisible. The Show debug controls
checkbox will make them available. Users may drag the Show progress
control bar to any slower position to watch the
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 solution search was the most satisfying part of this project.
FindNext is the recursive function which performs a depth first
search. Because we are progressing from low to high numbers, we we
don't have to worry about looping, i.e. repeating a position that we have
already visited. The pseudo code for puzzle size N looks like
|Insert Fromvalue into Fromcell|
|If Fromvalue is the last point (NxN) then set
result=true and exit.|
|Fromvalue not the last point:|
| Set Nextvalue=Fromvalue+1,
| For each of the 4 directions check
the neighbor (Nextcell)|
|Is Nextcell empty and Nextvalue
|No: If Nextcell already
contains Nextval then this is a predefined number,|
|end neighbor search loop|
|if Result=False and Fromvalue was not
predefined then set Fromcell abck to empty |
Procedure SolveBtnClick makes the initial call to
FindNext passing the location, or a possible location for the first
entry ( "1"). Location is a one dimensional array
containing NxN the cell coordinates for all predefined numbers or
(0,0) if not predefined. Findnext uses Location to
checked for predefined numbers. It is also the used to build a list of
cell locations where 1 might belong if it is not predefined. The
solution can start at any cell that is within the lowest predefined number
of cells from its location. For example, if the lowest predefined
number is 5 and is located at (1,1), then 1 must belong to any empty cell
within the rectangle defined by (1,1) to (5,5).
SolveBtnClick builds a list of these cells and make the initial call
with each of these possible starting points until a true result is found.
The other interesting aspect of the code was setting up the controls used
to bug the search code. It is helpful to watch the search proceed if
one can watch the point where the error exists. Unfortunately that may
be several thousand moves into the search and could take hours reach.
By setting limits for the display animation and forcing a pause when a
specific number is reached, the error location can be located quickly (or at
least a lot faster than without the controls :>). A
trackbar controls the pause time after each changed board is displayed.
Setting the bar to its max position by passes the animation completely.
When the specified value is placed in a specified cell, a pause loop is
entered allowing the programmer to set a break in code or to change the
pause values before continuing. This is accomplished by setting
a "Pause" flag to true and looping with "Sleep" and "application.processmessages"
commands until Pause=false. Clicking the displayed pause
message sets Pause to false.
Addendum October 9, 2008: A Numbrix puzzle generator was
posted today. It generates puzzles of several sizes and has a few
options. Users may choose to define the border cells as the
predefined values or may click cells to define any other pattern.
Puzzles up to 10x10 cells in size may be generated. A small change to
the Numbrix program allows it to solve 10x10 puzzles also.
Running/Exploring the Program
Suggestions for Further Explorations
Done October 8, 2008:
A "generator" would be a nice addition
to the program. Simply generating a random starting point and a random
direction for each successive number would usually not succeed because
unreachable holes would be left and stop the generation before the puzzle
was complete. So we would need to generate random moves with the
constraint that each number added must not leave unreachable cells or "one
way streets". Twisty alleyways that are two cells wide, so numbers
could be added down and back would seem to make a harder puzzle than those
that are continuously filled as we progress.
Original Date: September 28, 2008
May 18, 2009