Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Programming killer sudoku

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku
View previous topic :: View next topic  
Author Message
garthd

Joined: 29 Apr 2006
Posts: 32
:

Items
PostPosted: Fri Sep 15, 2006 11:19 pm    Post subject: Programming killer sudoku Reply with quote

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)
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Sep 16, 2006 12:15 am    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Visit poster's website
garthd

Joined: 29 Apr 2006
Posts: 32
:

Items
PostPosted: Sat Sep 16, 2006 8:50 am    Post subject: Reply with quote

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?
Back to top
View user's profile Send private message
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Sat Sep 16, 2006 11:08 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message Visit poster's website
Jean-Christophe

Joined: 19 Mar 2006
Posts: 126
:
Location: Belgium

Items
PostPosted: Sat Sep 16, 2006 11:35 am    Post subject: Reply with quote

garthd wrote:
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...


Have a look here :
http://www.setbb.com/sudoku/viewtopic.php?t=913&mforum=sudoku
For regular killer, there is no J#

garthd wrote:
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.


Correct, for larger groups, you'll find a complementary smaller group. eg R12345 is complemented by R6789.

garthd wrote:
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?


I can't answer for Ruud, but I did not hard coded these. I like to have a program as flexible as possible. Anyhow, I had to make it a generalized feature since my program also support such variants as jigsaw killer, extra-groups, diagonals...

Building the list of groups works by searching adjacent groups, which are touching each other. Finding them can be done once, and you can keep their list. The groups may also have flags for the various innies & outies techniques to avoid rechecking groups which have not changed since the previous run.

Please note that some groups may indeed cover the same set of cells eg the top 3 rows = the top 3 nonets for 3x3 killer.
_________________
Jean-Christophe
"When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes.
Back to top
View user's profile Send private message Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Sat Sep 16, 2006 12:28 pm    Post subject: Reply with quote

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
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Exotic sudoku All times are GMT
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron