Programming killer sudoku

garthd · Posted: Fri Sep 15, 2006 11:19 pm Post subject: Programming killer sudoku

Does anyone know a good site where I could find some hard killer sudoku for testing purposes (in string format would be good..)

Also, I'm trying to come up with a way of efficiently coding the '45 rule' in vba. Any ideas - especially for testing various combinations of mini grids (rows and columns are easier)

Ruud · Site Admin

Hi garthd,

You can find several tough Killers on my Assassin page.
I also have a page with links to sites that publish killers of excellent quality.

The '45' rule covers several techniques. I have implemented "sumgroup" objects, which cover 1 or more adjacent rows/columns or nonets. For each of these sumgroups, I keep track of the "border cages", which lie partially inside the sumgroup. For each sumgroup, record the sum of all cages that lie fully inside the group, and the sum of the border cages. Now you can identify innies and outies by inspecting the border cages. Solved cells will adjust the totals.

These are some of the elementary '45' techniques:

- Find single innie or outie.
- Split a cage for groups out innies or outies.
- Check combinations in split cages.
- Calculate innie-outie difference to determine minimum-maximum sums.

Naked pairs on the border can be isolated, since their total sum is fixed. Very complex innies or outes can be formed when not all cells can see each other.

In short, there is no single '45' rule to implement.

cheers,
Ruud
_________________
Meet me at sudocue.net

garthd · Posted: Sat Sep 16, 2006 8:50 am Post subject:

Hi Ruud

This is great - but are you able to explain how the string format works on your assassin page so I can work out how to import puzzles into the program I'm putting together (entering kilers manually is a bit time consuming...

I understand that there are a number of different 45 rules. I was interested in finding the most efficient way to scan different combinations of rows/columns and nonets to find innies and outies. Rows and columns seem fairly easy - e.g. search rows 1-9 individually, then rows 1 and 2, 2 and 3, 3 and 4 etc (and keep doing this for both rows and columns). Am I right in thinking that you only need to search for innies/outies in single rows/columns, two adjacent rows/columns and so forth up until you reach four adjacent rows/columns? This should be reasonably easy to manage. I was more interested in stuff like testing three nonets in an L shape for innies/outies. Does that mean that your "sumgroup" objects are hard coded (e.g. that you've worked out all the various ways in which nonets can be combined) and then use these? Or is there some better way of doing this?

Jean-Christophe · Posted: Sat Sep 16, 2006 11:08 am Post subject:

Hi,

You'll also find several killer links on my site

I implemented the various '45' somehow like Ruud.
Please note that you may get different results :
A single cell, this is the simplest case and you can solve the cell directly.
Several cells which are buddies of each other, which "can see" each other cell. ie these may not hold duplicated numbers
Some of the cells are not buddies, they may hold duplicated numbers. This is more common with outies. eg R1C4+R4C1 = 4 may be 2+2
With combined outies & innies, you get a difference of cells : some are added, some are subtracted.
The 'overlap' technique may even give you a formula where some cells add up or subtract twice (or even several times)

I use an innies/outies "builder engine" which combines the different "sum pieces" :
- rows, columns, blocks/nonets/boxes... which sum = 45 = (N * (N+1)) / 2
- cages, incl. previouly "splitted" cages
- solved cells
This engine contains a sum and a formula of cells which I implemented as a map from cells to integer coefficients. eg :
R1C1+R1C2 = 10 gives sum = 10, formula = {R1C1 -> 1, R1C2 -> 1}
R1C4-R2C3 = -2 gives sum = -2, formula = {R1C4 -> 1, R2C3 -> -1}
2*R1C4-3*R2C3 = 15 gives sum = 15, formula = {R1C4 -> 2, R2C3 -> -3}

This engine has methods to add or subtract these pieces :
- those which unsolved cells are entirely within the current set of cells
- those intersecting, which unsolved cells are mainly within the current set of cells
- for the complex cases, methods to "simplify" the resulting formula with other formulas previously computed. This is the most complex one.

With such an engine, it's easier to implement the various innies and outies.
eg for innies :
Start with an empty formula (empty map), sum = 0
Add up all cells in the group(s) (rows, columns...), update sum accordingly
Subtract all given cages which unsolved cells are entirely in, update sum
Subtract all previously splitted cages which unsolved cells are entirely in the current set of cells, update sum
Subtract all solved cells, naked pairs, triplets...

Warning : Isolating naked pairs, triplets... is only valid for cells which are buddies of each other, which "can see" each other cell. Otherwize, these are indeed not forming a naked pair.

With the hardest killers, the "Ruudiculously hard" ones Wink

, all these techniques will find relations between cells which are not always useful, which are just a consequence of each other. It's not an easy task to find the useful relations among these, the relations which will actually make progress.

BTW Law of Leftovers (LoL) for jigsaw is very similar. Indeed I implemented it using the same engine.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.

Jean-Christophe · Posted: Sat Sep 16, 2006 11:35 am Post subject:

Ruud · Site Admin

Excellent replies, JC.

Because I also support Jigsaw Killers in my program, the sumgroups are dynamically constructed after the puzzle is loaded or manual setup is finished. All combinations of upto 4 houses are considered, but only when it does not leave a "gap" that is already defined as a sumgroup.

Here is the PS format description, which I use for my Assassins:

a single string is used, no blanks or line breaks allowed (SumoCue doesn't care about that)
a colon is placed after each field.
3 mandatory fields to begin with:

1. Format: "3x3" (I don't know or use any other formats)
2. Diagonals: "" or "d"
3. Killer: "k"

For normal killers, the string always starts with "3x3::k:"

Next are 81 fields, containing a number: (cageID * 256) + cageSum

where cageID is a unique number identifying the cage.

And the SumoCue format is:

"SumoCueV1"
followed by "D" when diagonals are constraints,

followed by 81 entries, which can be:
"=nn" (the left-top cell of a cage, nn is the sum, can be zero for jigsaws and killers with unspecified areas)
"+nn" (a cell that belongs to a cage. nn is the 0-based cageID)
each entry is followed by "J0" through "J8" for jigsaws and jigsaw killers.

I only use SumoCue format for jigsaw (killers), because PS is recognized by multiple killer programs.

Crossword killers have a different format and start with "SumoCueV2"

Ruud