About Bob Hanson's Su-Doku solver

Programs which generate, solve, and analyze Sudoku puzzles

About Bob Hanson's Su-Doku solver

Postby 999_Springs » Fri May 11, 2007 7:46 pm

Does Bob Hanson's solver do locked candidates type 2? I don't think that it does. I think that it finds these eliminations as Medusa strong chains. Could someone please verify this?
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

re: Bob Hanson's SuDoku solver

Postby Pat » Sun May 13, 2007 9:28 am

999_Springs wrote:Does Bob Hanson's solver do locked candidates type 2?

I don't think that it does.
I think that it finds these eliminations as Medusa strong chains.

Could someone please verify this?



perhaps not so many use Bob Hanson's software ?

in another Topic, Pat (2007.Apr.29) wrote:
999_Springs wrote:The solver I use to solve my puzzles is Sudoku Assistant/Solver.

The solver doesn't do locked candidates type 2.
It finds those as Medusa strong chains.
I don't know why.

i haven't tried Bob Hanson's software

from his explanation it appears that he does use both types of "Locked Candidates"
( though his numbering of the 2 types is the reverse of angusj's ).

User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Sudoku Assistant -- News and 4500 method examples

Postby Bob Hanson » Sun Dec 21, 2008 7:28 pm

I've been out of this forum for quite some time -- has it been two years? Maybe. In any case, I've recently gotten back to some Sudoku programming and am interested in discussing a few things.

Recent news:

-- The Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku did have a bug that was preventing it from finding these locked candidates. That's fixed now.

-- The Sudoku Assistant was only minimally finding almost-locked sets. This bugged me, so I went back to this and redesigned the search engine to do that right. To my great delight it now finds LOADS of almost-locked sets, many of which are very simple.

-- Especially noteworthy (I think) is my recent finding that there is something I am now referring to as "bent naked subsets". One subset of these is related to almost-locked sets. These are now being found by the Sudoku Assistant, and they are very interesting. The basic idea is that what people originally referred to as "mutually doubly-linked almost-locked sets" are often just naked subsets that turn a corner.

I would greatly appreciate someone critiquing my analysis of these at
http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#bent

Questions:

1) Have people discussed these? They are incredibly easy to find, and it looks like quite a number of named methods reduce to them (XY-Wing, XYZ-Wing, for instance)

2) Has anyone developed my original idea of a couple of years ago of grid-based analysis (X-Wings, Swordfish, etc.) as simple naked pairs/triples "turned on their side"? ( http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#grid )

3) It turns out that the almost-locked business also extends to grids, and there the idea is incredibly powerful and easy to implement. Sudoku Assistant was sort of doing this, but now it is really doing it right. ( http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#almostgrid )

4) What other solvers handle almost-locked sets -- regular or grid-based?

Finally, I've put together a site with over 4500 method examples. Very interested in comments and suggestions on that. This is just out today. I'm already learning a lot simply scanning it for interesting patterns. See http://www.stolaf.edu/people/hansonr/sudoku/ex_Sh2.htm and associated pages.

please feel free to contact me at hansonr@stolaf.edu, where I am more likely to respond than here.

Bob Hanson
hansonr@stolaf.edu
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby Pat » Tue Dec 23, 2008 12:11 am

Bob Hanson wrote:2) Has anyone developed my original idea of a couple of years ago of grid-based analysis (X-Wings, Swordfish, etc.) as simple naked pairs/triples "turned on their side"? ( http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#grid )



http://forum.enjoysudoku.com/viewtopic.php?t=5017
User avatar
Pat
 
Posts: 3438
Joined: 18 July 2005

Postby Bob Hanson » Tue Dec 23, 2008 1:14 am

Thank, Pat.

The idea also extends to almost-locked sets in a very interesting way.
I'm finding that to be a very humanly useful concept. Presentation of that idea is at http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#almostgrid
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby 999_Springs » Wed Dec 24, 2008 4:39 am

Bob Hanson wrote:has it been two years?

Your last post before you left was in December 2005, so it has been 3 years.

Your almost-grids are the same as finned/sashimi fish, aren't they?

Unfortunately I can't see any of your 10000 method examples at all. I get an error message that says
An error has occurred in the script on this page. As a result, this page may not display or function properly.

Error: 'split(...).1' is null or not an object
Line: 93
URL:http://www.stolaf.edu/people/hansonr/sudoku/ex_Sh2.htm
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Bob Hanson » Wed Dec 24, 2008 5:08 am

can you tell me what browser/platform is saying that?
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby Bob Hanson » Wed Dec 24, 2008 5:14 am

I think I fixed it. If it doesn't work, close and reopen your browser or reload page http://www.stolaf.edu/people/hansonr/sudoku/ex.js a couple of times.
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby Bob Hanson » Wed Dec 24, 2008 5:42 am

999_Springs"][quote="Bob Hanson wrote:has it been two years?

Your almost-grids are the same as finned/sashimi fish, aren't they?

I would say that the "finned xxx" are subsets of these. There are several examples there that are much more interesting.

So, for example,

from http://www.sudopedia.org/wiki/Finned_Fish


the Finned X-Wing would be the 2x3 almost-locked row set {25 125} excluding other marks in column 2, block 4

the Finned Swordfish would be the 3x4 almost-locked column set {2358 258 258} excluding other marks in row 2, block 1

the Finned Jellyfish would be the 4x5 almost-locked row set {12468 2468 2468 2468}

But then you have examples such as

http://www.stolaf.edu/people/hansonr/sudoku/ex_A1g.htm?i520a.518.20

That's a 5x6 almost-locked set

http://www.stolaf.edu/people/hansonr/sudoku/ex_A1g.htm?top1465a.488.30

That's a 6x7 almost-locked set

I think it could go to 7x8 at least, though a cursory glance at that database didn't pop up anything bigger than 6x7.


Bob
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby 999_Springs » Thu Dec 25, 2008 7:25 am

Bob Hanson wrote:http://www.stolaf.edu/people/hansonr/sudoku/ex.js

But this happens...
Windows Script Host wrote:Can not find script file "C:\Documents and Settings\Owner\Local Settings\Temporary Internet Files\Content.IE5\GTGFOVS3\ex[1].js"


As for your 10000 method examples, I can see pictures now but no links.

As for your large almost-locked grids, I think that there is a smaller fish in all cases larger than 4x5. (Could someone please verify this?) But your solver may not find those because {1235 35}, for example, isn't an ALS but gives the same eliminations as {135 35}.

As for your two links giving reference to those big fish, clicking on them somehow closes ALL my windows. AAAARGH!

200th post! Do I get 2 cakes? Well, it's Christmas Day, so I may as well eat as much cake as I possibly can while I have an excuse to do so!!!
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby Bob Hanson » Tue Dec 30, 2008 7:49 am

very sorry -- been out of town, and I didn't properly check that page with Internet Explorer. Firefox loads these pages quite rapidly; I'm sad to see MSIE is so slow with this task. In any case, the link problem should be fixed.

I'd be surprised if the larger grids were subsets of fish -- they have too many interconnected subsets, I think. It would be nice if someone could confirm or refute that.

Bob
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby 999_Springs » Thu Jan 01, 2009 4:00 am

The links are working now, thanks.

I went through some of your larger examples of fish and there does seem to be a smaller fish in all cases. These are some examples:

Here you can use {r2c136 r8c26}.

Here you can use {r1c189 r7c18}.

Here you can use {r6c14 r9c24}.

Here you can use {r2c18 r4c238}.

Here you can use {r5c57 r7c47}.

Some of these aren't ALSs but some are. I think that what you are doing is only using column ALSs and never row ALSs in your solver. Your solver output only ever looks like ALS-X#n-Col...
Hidden Text: Show
Once upon a time I was a teenager who was active on here 2007-2011
999_Springs
 
Posts: 367
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Postby ronk » Thu Jan 01, 2009 4:31 am

999_Springs wrote:I think that what you are doing is only using column ALSs and never row ALSs in your solver. Your solver output only ever looks like ALS-X#n-Col...

Based on just the last two, the solver may not be recognizing sashimi.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Bob Hanson » Thu Jan 01, 2009 6:22 am

999_Springs wrote:The links are working now, thanks.

I went through some of your larger examples of fish and there does seem to be a smaller fish in all cases.

...
Here you can use {r2c18 r4c238}.

...
Some of these aren't ALSs but some are. I think that what you are doing is only using column ALSs and never row ALSs in your solver. Your solver output only ever looks like ALS-X#n-Col...



Ah, interesting!

The solver is checking columns first, then rows, so I think it is finding many column-type that could otherwise be found with simpler row-type checks. It is checking rows, as this search shows:

http://www.stolaf.edu/people/hansonr/sudoku/ex_A1g.htm?search=-Row&n=70

When I disable column checking to force row-type, some are not found. For example:

this one

So I think there may be some that are not reducible -- unless you see a smaller set here as well.

So while it's true that a 5x5 grid is always reducible to something smaller, I'm still not convinced that this is true with grid-based ALS.

As you point out with the above example, there are other ways than ALS to eliminate possibilities. Sashimi is one. Sudoku Assistant is not checking for sashimi. Interesting problem. I see how to do it with almost-locked sets. It should be a very simple addition to the code.
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Postby Bob Hanson » Thu Jan 01, 2009 1:09 pm

Here we go...

http://www.stolaf.edu/people/hansonr/sudoku/ex_A1s.htm

Thanks for the sashimi comment. Adding a sashimi check does in fact make a huge difference in solving these puzzles. I'll be redoing all the ALS examples, but I thought I would add this preliminary set of examples now (263 examples from just the first 312 "impossible520" puzzle set) just to get the discussion going and demonstrate that sashimi is, in fact, one more very nice application of almost-locked sets.

I'm very pleased that adding sashimi to Sudoku Assistant required only five lines of code. That's what I like to see! (find "sashimi" in http://www.stolaf.edu/people/hansonr/sudoku/almostlocked.js)

Bob
Bob Hanson
 
Posts: 75
Joined: 04 December 2005

Next

Return to Software