Killer logic

Killer Example

Killer problems are slightly different because they have additional, smaller, Killer Shapes with given sums and they do not normally have any initial characters. All the logic is illustrated by referring to the problem below that appeared in The Times July 12, 2012, #2646. This is the standard 9X9 Cell geometry with numbers 1 through 9 but the logic and the solver program can be applied to any valid Sudoku geometry that has had Killer Shapes overlaid.

 

Check Partitions

An extra bit of logic, check partitions, is required to deal with the Killer Shapes. This simply checks Killer Shape by Killer Shape and Cell by Cell to eliminate any possibilities which cannot still add to the given sum.

Count Overlapping Sums

One can usually start a Killer problem by looking at the overlap of the Shapes as illustrated below.

K-Times 2646, 2012-07-12 1st 3 Cells

Three Cells have already been calculated in the above example as follows:

  1. Add the sums of the Killer Shapes completely contained within the 3X3 box at top right. This gives 21 + 13 + 7 = 41. All Cells in this box must sum to 45 so we can place a 4 in row 3 column 7.
  2. We could also sum all Killer Shapes which are completely or partially contained in the same box, to give 21 + 13 + 7 + 13 = 54. Hence row 4 column 7 must contain a 9.
  3. Now sum  all Killer Shapes which are completely or partially contained in the top 2 rows to give: 18 + 17 + 14 + 21 + 13 + 16 = 99. All Cells in these 2 rows must sum to 90 so the solution in row 3 column 9 must be 9.

Created Shapes and Super Shapes

If the problem contains ANY Killer Shapes the program will start with the above logic.. To be able to do this, especially for example 3, above, We define a new Shape called a “Super Shape”. This can be any combination of 1 through N, non-intersecting, Sudoku Shapes, where N is an adjustable parameter. These are then used to make “Created Shapes”  which come in 2 flavours:

  1. An Inner Created Shape is essentially what is left over from a Super Shape after removing all fully contained Killer Shapes.In the above example the top right 3X3 box is a Super Shape and the Cell at row 3 column 7 is an Internal Created Shape.
  2. An Outer Created Shape is the union of all Killer Shapes that are fully or partially contained within the Super Shape less the Super Shape itself.In the above example there are 2 External Created Shapes
    1. Single Cell at row 4, column 7 with the Super Shape being the top right 3X3 box.
    2. Single Cell at row 3 column 1 with the Super Shape being the top 2 rows.

 

Created Shapes can be one or more Cells up to a maximum which is set as a parameter. The Cells need not be contiguous and values may or may not be allowed to repeat depending on the positioning of the Cells.This is best illustrated by the following 2 examples.

K-Times 2646, 2012-07-12 Problem, Created 56, 37

In the example, above, the 2 Cells at positions (5,6) and (3,7) form an External Created  Shape of size 2 formed from the Super Shape which is the combination of the 2 3X3 boxes at middle right and bottom right. The sum of all the Killer Shapes at least partially contained in this Super Shape is 102 so the sum of Cells  (5,6) and (3,7) is 12. Duplicates are allowed in this Created Shape so we would have to consider the possibility of a 6 in each Cell if we had not already determined the content of Cell (3,7) to be 4.

K-Times 2646, 2012-07-12 Problem, Created 38-58

Here Cells (3,8), (4,8) and (5,8) form an Outer Created Shape of size 3 and sum 17 with duplication not allowed. The Super Shape was column 9.

The completed solution is shown below.
K-Times 2646, 2012-07-12 Solution

Size of Created Shapes and Super Shapes

Both these sizes can be set by parameters during execution. The defaults are

  • Created Shapes: maximum 2 Sudoku Shapes
  • Super Shapes: maximum 4 Cells

Increasing the size of Super Shapes will increase execution time because the possible combinations grow rapidly. If you were soving the above problem by hand you would only consider Super Shapes such as 2 contiguous rows or columns or 3X3 boxes. Because the program is written to be general it does not know whether 2 Cells are contiguous or not so it can produce bizarre Super Shapes as shown in the 2 figures below.

K-Times 2646, 2012-07-12 Super Shape Ex 1

K-Times 2646, 2012-07-12 Super Shape Ex 2

Both are valid Super Shapes but will probably not generate any useful Created Shapes.

Increasing the size of Created Shapes will not increase the calculation time significantly but will have marginal benefit in terms of finding solutions, especially since may of the Created Shapes will allow duplicates so the partition routines will be less effective.

Viewing Created Shapes and Super Shapes

Both these types of Shape are created during execution and are not saved with the solution or template file.

Created Shapes can be viewed after execution via Options>Show Shapes.

Super Shapes are usually deleted as soon as the Created Shapes have been created (they serve no more useful purpose). You must use Step by Step execution to view them.

  • Select Options>Ch. Parms>Logic and select “Show Menu” opposite SXS Setup.
  • Return from the Modify Parms menu and select “Step by Step”. The Stepwise Soln menu which will be displayed allows you to build Created Shapes and continue without deleting the Super Shapes.
  • Now select Options>Show Shapes to see these Super Shapes

Leave a Reply