Relevant hardness of solving techniques

gaby

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/

Lummox JR · 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.

gaby · 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 Smile

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/

Lummox JR · 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:

gaby · 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/

gaby · 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/

Ruud · Site Admin

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.

gaby · 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 Smile

).

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/

Lummox JR · 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.

Ruud · Site Admin

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 Smile

Still need to optimize the code, but it works.

Bob Hanson · 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

gaby · Posted: Tue Oct 25, 2005 10:10 am Post subject:

I'll paste what I have in the comments of my templating code:

Bob Hanson · 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

gaby · 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/