Programming notes

So far I've only got around to describing the basic variables and the algorithms involved in dealing with the "Isolated neck" methods. Given a bit of encouragement I could do the others.

The puzzle data is stored as a list of cells. For example a 9x10 grid would have a list of 90 cells.

There are 5 types of cell: those to be solved, those with sums across, those with sums down, those with sums down and across, those that are just padding.

For each cell we store:

• Cell index - element number in cell list
• Row index - which row of the grid we are in
• Column index - which column of the grid we are in
• Cell type - see above
• Solution
• Current guess
• Candidate status - ie on or off for all 9 digits
• Sum across index - cell index of sum across
• Sum down index - cell index of sum down
• Sum across given - initial sum across
• Sum down given - initial sum down
• Sum across - the remaining sum across
• Sum down - the remaining sum down
• Cells across given - number of cells in a horizontal strip
• Cells down given - number of cells in a vertical strip
• Cells across - number of unsolved cells in a horizontal strip
• Cells down - number of unsolved cells in a vertical strip

Obviously some of these items are only relevant to certain types of cells, some are fixed and some have to be kept up to date as the puzzle gets worked on.

For traversing the grid we have 4 functions: next_cell_across, next_cell_back, next_cell_up, next_cell_down, which take as input the current cell_index and, knowing the grid width, return the cell_index for the requested direction.

Finding and solving necks

A "neck" is a cell made special by a particular type of grid layout. This form of layout sometimes makes it possible to solve the cell at the neck by simply adding and subtracting the sums across and down. Please see the figure.

Recognising necks is performed in two stages. First we have to examine all cells to see if they have the characteristic environment of a neck. Secondly, we have to see if the neck lies adjacent to a group of isolated cells. Please look at the next figure. It contains 8 neck cells.

Cell environments. Every cell for solving touches 8 others:

       123
       4X5
       678

It turns out that there are only four possible necks (related by
rotational symmetry) and the cells for solving form the following
environments:

       1
       4X        14421
        78

         3
        X5       29393
       67

        23
       4X         6545
       6

       12
        X5        4485
         8

There are two examples of each in the figure shown above.

The program assigns the first 8 prime numbers to the locations around each cell. Using the grid traversal routines listed above it visits each of the eight cells around a cell. If the cell is for solving (white in the figures) it multiplies in the corresponding prime number (for example the top one is 3x11x19x23=14421). The values shown next to the necks in the diagram above are their corresponding prime products, or topology_indexes. If a cell with any of these 4 topology_indexes is found we next have to see if it lies adjacent to a block of isolated cells.

Blocks of cells are "isolated" if they are surrounded by sum cells and padding. We test if this is the case by attempting to traverse round the block in exactly 3 turns. Depending on the topology_index we go round in a clockwise or anticlockwise circuit. For example, for index 14421 we go round anticlockwise. When moving we have a primary and a secondary direction. Directions are: left, right, up, down. We always try the primary direction first and only use the secondary if we cannot move in the primary direction. If we cannot move in either we must make a turn. The routines required are outlined below.

Routines

topology(cell_index)

Calculates the topology_index for cell cell_index.

do_range(cell_index)

For each row remember the furthest left and right we have visited.
Ditto columns.

one_move(cell_index, direction)

If the next cell in direction direction is for solving, add its
cell_index to a list and move there - ie make it the new cell_index
Update the ranges using do_range.

to_next_turn(cell_index, primary_direction, secondary_direction)

While we can move in the primary direction, do it using one_move.
When we cannot, try the secondary direction (using one_move).
If that is successful continue using the primary direction.
Continue in this way until we cannot move in either the primary
or the secondary direction.

turn(primary_direction, secondary_direction, circuit)

turn makes the appropriate changes to primary and secondary directions,
depending on the circuit (clockwise or anticlockwise) and their
current values. eg for topology_index 14421 we move anticlockwise
starting with primary_direction = up, secondary_direction = left. At
the first yellow coloured cell in the figure we cannot make progress
so routine turn changes primary_direction to left, and
secondary_direction to down. At the next corner turn switches them to
down and right. At the next to right and up.

get_sum(cell_list)

Cell_list is the list of cell_indexes collected by one_move.
Make lists of the sum_across cells and sum_down cells for these cells.
(Each cell stores the index of its sum_across and sum_down cells.)

Process the sums_across list:
If its leftmost and rightmost cells are both within the range visited
add its sum

Ditto sums_down list.

Subtract the two sums, return the absolute value as the result.

Routine one_circuit puts it all together and attempts to
traverse the neck in 3 turns.

one_circuit(neck_cell_index, topology_index)

cell_index = neck_cell_index

Use the topology_index to choose the circuit (clockwise or anticlockwise)
and the initial primary and secondary directions.

to_next_turn(cell_index, primary_direction, secondary_direction)
turn(primary_direction, secondary_direction, circuit)

to_next_turn(cell_index, primary_direction, secondary_direction)
turn(primary_direction, secondary_direction, circuit)

to_next_turn(cell_index, primary_direction, secondary_direction)
turn(primary_direction, secondary_direction, circuit)

to_next_turn(cell_index, primary_direction, secondary_direction)

if cell_index == neck_cell_index
 neck_cell_solution = get_sum
 WHOOPEE!

i.e. if we get back to the neck_cell_index in 3 turns it is an isolated
block and the resulting value from get_sum is the solution for
neck_cell_index.