|
View previous topic :: View next topic |
Author |
Message |
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Thu Oct 13, 2005 7:32 pm Post subject: Relevant hardness of solving techniques |
|
|
Following on from some other thoughts, posts and associated websites:
http://vanhegan.net/sudoku/
I'm thinking more about my ratings system. My solver initially had simple techniques like X-wing and number pairs removed, because they were subsumed by generic number chains/disjoint subsets, and my swordfish implementation. In the interests of making a more human like solver, I've added them back in as lower level techniques. I've also made the solver short-cut itself (as soon as it removes a candidate or sets a value it stops that technique and starts at the easy techniques again) which I think is a more human-like way of solving sudoku.
The techniques used are then rolled into a rating for the puzzle (which is described at http://vanhegan.net/sudoku/ratings.php). What I want to know is what people think about the levels I have assigned to the various techniques. Do they seem sane? Is something obviously out of place?
My only thoughts are that perhaps templating should be a level 5 technique, and forcing chains should be a level 4 technique. Being that every puzzle on my site has a unique solution, is there much to be gained from implementing the uniqueness test? I would have that as a level 3 technique. _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Thu Oct 13, 2005 7:47 pm Post subject: |
|
|
I'd bump up templating, tabling, and forcing chains.
Also you really should have coloring on that list. Complete coloring is actually a superset of fishy cycles, and rather easier to handle manually. It's a level 3 technique by that rating system for sure.
Nishio belongs in level 4, but only slightly. It belongs there by dint of being harder than the level 3 methods and easier than the level 5 ones, but it's actually so weak next to even simple coloring, let alone supercoloring, that it's nearly useless among them.
I'd also recommend implementing supercoloring, which would be a level 4 technique. |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Thu Oct 13, 2005 7:58 pm Post subject: |
|
|
Colouring is the last missing item on my list, it's the final 'to do' for my solver The only problem that I have is that I still can't wrap my head around it. Further reading required. Also, looks like I'll be re-rating all my puzzles, but not until colouring is implemented.
I think I agree with you about the up-grading of those three techniques. Templating and tabling are very much level 5 techniques. I would probably put colouring into level 4, so I agree on that also.
Is it worth doing colouring, supercolouring or ultracolouring? Supercolouring would be ideal, either that or DLX. _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Fri Oct 14, 2005 3:29 am Post subject: |
|
|
Coloring is level 3 for sure. It's powerful but fairly easy. Supercoloring on the other hand belongs in level 4, because it's a lot harder to set up the grid and the conjugates, and harder still to find all the transitive exclusions for a large number of colors.
Supercoloring and ultracoloring are the same thing. As usually presented in this forum they assign "non-conjugate" colors to all cells left over after conjugate analysis, but I think that overcomplicates things a bit and at best makes things easy for a computer solver.
To give you a rough overview of coloring, basically you want to find sets of conjugate values and just spread out those conjugates as far as you can. Here's a puzzle where you can use coloring twice:
Code: | . . 9|. . .|. 8 1
. 5 .|. . .|9 . 3
. . .|1 . .|. . .
-----------------
6 . .|5 4 .|8 . .
. . .|. . 6|. . .
3 2 .|. 8 .|1 6 5
-----------------
. 7 8|9 . .|. 1 .
. 6 .|. . .|. . .
. 3 .|8 . .|. 7 6 |
You'll reach a point where you can't go much further without something advanced, so then you can try coloring on the 4's.
Code: | . . .|. . .|. . .
. . .|* . .|. * .
. . .|. . *|. . *
-----------------
. . .|. . .|. . .
. . .|. . .|* * *
. . .|. . .|. . .
-----------------
* . .|. . *|* . *
* . .|* . .|* . .
. . .|. . *|* . . |
Start with the first place you see where there are only 2 places in a box, column, or row where the digit can go. Call one of them a; the other will be A. These are conjugates; if one is true the other is false, and vice-versa. Everywhere you place a color, keep looking for whether only one other spot in a box/column/row will work. Spread out a and A as far as you can.
Just to get started, put a in (4,2) and A in (6,3), (8,2), and (4,5). Each of those form a conjugate with (4,2) in box 2, row 2, and column 4 respectively. The A in (8,2) has more conjugates of its own, in box 3 and column 8, so label (9,3) and (8,5) with a.
Code: | . . .|. . .|. . .
. . .|a . .|. A .
. . .|. . A|. . a
-----------------
. . .|. . .|. . .
. . .|. . .|* a *
. . .|. . .|. . .
-----------------
* . .|. . *|* . *
* . .|A . .|* . .
. . .|. . *|* . . |
Now if you look you'll see more conjugates, so let's also add b and B, and so on.
Code: | . . .|. . .|. . .
. . .|a . .|. A .
. . .|. . A|. . a
-----------------
. . .|. . .|. . .
. . .|. . .|* a *
. . .|. . .|. . .
-----------------
b . .|. . *|* . *
B . .|A . .|* . .
. . .|. . c|C . . |
Because coloring works with conjugates, either the a's or A's must be true, and so on for b and B, c and C. A shares houses with both B (row 8), and c (box 8), so you can say it excludes those colors: A!B and A!c. With exclusions you can also extend them in some cases. If x!y and Y!z, then x!z; that rule comes into play a lot in supercoloring.
If a color excludes itself by appearing twice in a particular house, it's false. You'll see that later. Also, any cell that intersects two conjugate colors (e.g., if it touches both a and A) can't hold the digit.
Now if two colors exclude each other, they can't both be true; they may even both be false. But their conjugates have the opposite situation: They can't both be false, and may even both be true. Since in this example A!B, that means either a or b or both are true. Now you can look for intersections with a and b, and you'll find that they meet at (9,7). Therefore, (9,7)<>4.
Code: | . . .|. . .|. . .
. . .|a . .|. A .
. . .|. . A|. . a
-----------------
. . .|. . .|. . .
. . .|. . .|* a *
. . .|. . .|. . .
-----------------
b . .|. . *|* . -
B . .|A . .|* . .
. . .|. . c|C . . |
After a round of easier tactics, you'll get to a place where you can do coloring on the 2's, and you'll get this result:
Code: | A . .|. . .|a . .
. . .|a . .|. A .
a . .|. . A|. . .
-----------------
. . .|. . a|. A .
. . .|A . .|A * .
. . .|. . .|. . .
-----------------
. . .|. . .|. . .
. . .|. . .|. . .
. . .|. . .|. . . |
A appears twice in column 8, row 5, and box 6. Clearly, A cannot be true. Therefore you can place a 2 everywhere you see an a. |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Fri Oct 14, 2005 4:03 pm Post subject: |
|
|
Thanks for that explanation. I tried to implement it last night (bed at 4am...) and I got something that works, but I'm not totally convinced that it's any good. I'll read more about this (I keep saying this) and tweak it s'more.
On another note, do you reckon Fishy Cycles is a level 4 technique? Based on the complexity, I think it is, although it will get subsumed by tabling. I'm not going to bother with Multicolouring or ultracolouring, as my tabling implementation solves pretty much everything, but I do need a good colouring implementation. _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Sat Oct 15, 2005 1:30 am Post subject: |
|
|
Cracking! Extremely useful examples, thank you. I've now managed to get the first part of colouring in place, and it manages to solve the puzzle you give there in the way expected. I do have one interesting point to note. When it calculates the exclusions, I included the blocks in the intersection calculations. Example:
If 1a excludes 2b, then we look at the intersection of 2a and 1b.
for each cell in 2a X {
for each cell in 1b Y {
Get the row, column and block's worth of cells for X
Get the row, column and block's worth of cells for Y
Then calculate the intersection of
rX and bY
cX and bY
rY and bX
cY and bX
rX and cY
rY and cY
(rX is the row that cell X is in, bY is the block that Y is in, etc)
Add together all these intersections, which gives us the list of cells to remove the candidate number from.
Subtract from this list all the cells in 2a and 1b.
Remove the candidate from the remaining cells
}
}
I found that this didn't quite work in the way that was expected when I included the blocks in the list. When I remove the blocks, it works fine. I can't quite work out why... _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sat Oct 15, 2005 12:43 pm Post subject: |
|
|
Since Gaby also has implemented templates, this would be a nice place to compare the 2 techniques.
Lummox, in your puzzle, after applying basic techniques, I found another coloring opportunity, in the 3s.
A!B => either a or b are true.
Code: | . . .|. * *|. . .
. . .|. . .|. . .
. . .|. . .|. . .
-----------------
. . .|. . A|. a .
. . .|B * .|* * .
. . .|. . .|. . .
-----------------
. . .|. * *|* . .
. . .|b * *|* - .
. . .|. . .|. . . |
After elimination of (8,8), the next elimination (7,5) is obvious:
Code: | . . .|. * *|. . .
. . .|. . .|. . .
. . .|. . .|. . .
-----------------
. . .|. . A|. a .
. . .|B * .|- A .
. . .|. . .|. . .
-----------------
. . .|. * *|* . .
. . .|b * *|* . .
. . .|. . .|. . . |
This could also be achieved by box/column interaction.
My template checker does eliminate (8,8) and (7,5) in a single pass. It obviously could not fit templates with (8,8) filled. Therefore it only found templates with (7,7) or (7,8) filled, effectively eliminating (7,5).
Now I can see no logical way to eliminate (7,5) without looking at (8,8), so the template checker seems to be able to look beyond eliminations that in coloring must be made before you can draw any additional conclusions.
Or am I missing something here?
PS
My solver, impatient as ever, actually found this pattern before the last 2 clues (8,9) and (9,9) were filled, so if the pattern does not match yours, just leave out those 2 clues.
Ruud |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Sat Oct 15, 2005 7:35 pm Post subject: |
|
|
The templating system I have just says "Yes, it's this layout" or "No, there are X possible layouts" for the puzzle. Now that I finally understand colouring, it's made a big difference to my solver. It's a very simple loop, not recursive at all, so it runs fast (and produces nice pretty colours ).
Templaing takes about 10 seconds to run on a partially solved puzzle (in my PHP solver, not the most efficient of routines) so I don't normally bother using it. Unless I've missed something about the concept of templates, I don't find it much fun. It's just brute force, there's no elegance like there is in colouring. _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Lummox JR
| Joined: 07 Sep 2005 | Posts: 202 | : | | Items |
|
Posted: Sat Oct 15, 2005 7:59 pm Post subject: |
|
|
Fishy cycles isn't necessarily subsumed by tabling, but it is by complete simple coloring for sure. Also a valuable insight is that most simple varieties of forcing chains are "4D" equivalents of either fishy cycles or coloring-style eliminations and therefore fall under supercoloring. |
|
Back to top |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Sun Oct 16, 2005 12:49 am Post subject: |
|
|
Thanks to the fine postings by Lummox JR, my solver now supports multicoloring, recognizing the following situations:
1. conjugate pair in a house with other candidates (which can be eliminated)
2. inconsistent color, appearing twice in a house.
3. multiple colors in a house, turning their opposites into connected pairs
Anything I missed?
My single-digit-template-checker should now have lots of spare time
Still need to optimize the code, but it works. |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Mon Oct 24, 2005 11:02 pm Post subject: |
|
|
I think I'm catching on here. Please tell me if I have this right:
1) "simple" coloring focuses on a specific number, generating "conjugate pairs/strong edges" in the plane of the board.
2) "supercoloring" (perhaps) extends this to multiple numbers.
I think what the Medusa chain business is is just a simple way to encode and visualize coloring. Please take a look at
http://www.stolaf.edu/people/hansonr/sudoku
and see if you agree. This application simply identifies all conjugate pair chains and their relationships, looking for inconsistencies.
The aAaA business, I think, is just the alternating nodes on the "strong chains." (a) being (+) and (A) being (-), perhaps.
The aAaA,bBbB business recognizes that there may be multiple chains.
The Medusa idea is simply a way of doing this analysis to the extreme -- in every direction at once.
Can someone tell me what a "template" is, though?
Thank you. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Tue Oct 25, 2005 10:10 am Post subject: |
|
|
I'll paste what I have in the comments of my templating code:
Code: |
* The technique uses a system of pre-calculated templates. If you
* look at a single number, there are 46656 possible ways to arrange
* a single number on the board. For example the number 1 could be
* arranged this way:
*
* 1--------
* ---1-----
* ------1--
* ----1----
* -1-------
* -------1-
* --1------
* --------1
* -----1---
*
* Or they could be arranged this way:
*
* ------1--
* ---1-----
* 1--------
* --------1
* ----1----
* -1-------
* -------1-
* --1------
* -----1---
*
* Take this to it's logical conclusion, and there are 46656 ways
* to arrange the number 1 on the board, ergo there are 46656 ways
* to arrange each number on the board. We are referring to these
* as the templates.
*
* So we look at the state of the puzzle and we work out which
* templates are applicable to each number. We only have a few of
* each number, and many of the templates will have these numbers
* in these locations, so we will have a set of templates that fit
* for each number.
*
* If we manage to fill in a number, then we can restrict the set
* of templates for that number to the ones that have a number at
* that specific location.
*
* If we manage to remove a candidate, then we can remove all the
* templates that have that number at that position from the list.
*
* Finally, we will have a set of templates for each number. Any
* combinations that collide or have numbers in the same positions
* are removed from the list. Eventually we will either have one
* template for each number, or we will have a set of templates
* that describe the multiple solutions for the sudoku.
|
_________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Tue Oct 25, 2005 4:52 pm Post subject: |
|
|
Thanks. Oh, my! Such brute force. Alright--I'll leave templates to others. _________________ Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
Back to top |
|
|
| gaby
| Joined: 02 Jul 2005 | Posts: 120 | : | | Items |
|
Posted: Tue Oct 25, 2005 4:59 pm Post subject: |
|
|
It's brute force, but it's quite a nice approach. It's another method of finding out if there are multiple solutions to a puzzle, by the valid combinations of templates. If there's only one solution, there should only be one valid combination of templates. _________________ Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
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
|