|
View previous topic :: View next topic |
Author |
Message |
| garthd
| Joined: 29 Apr 2006 | Posts: 32 | : | | Items |
|
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) |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sat Sep 16, 2006 12:15 am Post subject: |
|
|
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 |
|
|
| garthd
| Joined: 29 Apr 2006 | Posts: 32 | : | | Items |
|
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? |
|
Back to top |
|
|
| Jean-Christophe
| Joined: 19 Mar 2006 | Posts: 126 | : | Location: Belgium | Items |
|
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 , 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 |
|
|
| Jean-Christophe
| Joined: 19 Mar 2006 | Posts: 126 | : | Location: Belgium | Items |
|
Posted: Sat Sep 16, 2006 11:35 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sat Sep 16, 2006 12:28 pm Post subject: |
|
|
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 |
|
|
|
|
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
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
|