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