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

Figure 1. A neck with solution 7. Because the block of cells to the left of the neck are completely isolated from the rest of the grid, the solution for the neck cell is the sum of the sums across minus the sum of the sums down: 19+28+4+3-(21+19+4+3)=7.

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.

Figure 2. This grid contains 8 neck cells: four which can be solved because they lie adjacent to isolated blocks of cells (solutions shown), and four (coloured red) which cannot because their adjacent cells are not isolated.

### 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 prime numbers 3,5,7,11,13,17,19,23 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.

```
Traversal from a neck. Starting at the neck, the program moves anticlockwise, making turns (i.e. changing its primary and secondary directions) at the cells shaded yellow.
```

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

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.

```