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   

Almost-locked sets implemented

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Thu Dec 15, 2005 12:48 am    Post subject: Almost-locked sets implemented Reply with quote
Whew! That was fun!

I've now implemented a pretty full complement of "almost-locked set"
analysis in Sudoku Assistant. Do take a look. Suggestions welcome!

http://www.stolaf.edu/people/hansonr/sudoku/index.htm?ALS

In short, I'm impressed. This is a powerful little technique that passes
the "easy to implement" and "succeeds in advancing the solution"
for many puzzles.

Thank you, bennys! I trust it is OK that I've credited you on that site.

I've implemented it both in terms of bennys's cell-based method, which
I am calling Y-type almost-locked sets, and its complement in the
"coloring" plane, which I am calling X-type almost-locked sets.


This turns out to be tricky, for sure, but not too bad. Just an extension
of subset elimination where we are looking for the dimensions of the
matrix being Nx(N+1) instead of NxN.

Very interesting!
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
bennys

Joined: 30 Sep 2005
Posts: 6
:

Items
PostPosted: Fri Dec 16, 2005 7:14 am    Post subject: Reply with quote
How exactly you are looking for ALS?
How you decide which sets to check and what exactly are you checking?
Back to top
View user's profile Send private message
Bob Hanson

Joined: 05 Oct 2005
Posts: 187
:
Location: St. Olaf College

Items
PostPosted: Fri Dec 16, 2005 3:52 pm    Post subject: Reply with quote
Looking for almost-locked sets:

This is in http://www.stolaf.edu/people/hansonr/sudoku/subsets.js

Take a look; you might be able to see how this works. Basically:

1) As explained at http://www.stolaf.edu/people/hansonr/sudoku/explain.htm,
all naked/hidded tuples, all X-wings, swordfish, and other grids are all
found the same way -- by looking for combinations of cells and
candidates (naked/hidden tuples) or columns and rows (X-wings and
such) that form an NxN set. That's the first thing to understand.

2) I just extended this to look for all Nx(N+1) sets.

checking almost-locked sets:

If you look at http://www.stolaf.edu/people/hansonr/sudoku/almostlocked.js
you will see that there are three stages of checking (same for chains).

Stage 1: Pre-Medusa

The first thing Sudoku Assistant looks for is a weak link to a pair of
already weakly linked almost-locked sets. This is implementing your basic idea.
This stage is right after creation. This is checkAlmostLocked(). It is called
by checkAlmostLockedSetsY() and checkAlmostLockedSetsX(), which are
what get run when you click the "+almost-locked sets" checkbox after
either subset elimination (Y) and grid analysis (X), respectively. This is
before any "Medusa" chains have been identified.
Code:

here we are checking for


         X.......X
        /         \
   a---A           B---b
        \         /
         Y...*...Y
 

   * can be eliminated

You might see something like this:

"r6c2#4 is weakly linked to two almost-locked sets already weakly linked by 1: r6c1 and r3c2 r4c2 r5c2"

While we're at it, we look for pairs of mutually linked almost-locked sets.
Code:

here we are checking for


         X.......X
        /         \
   a---A           B---b
        \         /
         Y.......Y

 
both a and b must be TRUE, so their weak nodes are FALSE

This is actually a VERY productive find. Because a and b are guaranteed to
be TRUE. Note that a and b don't refer to specific marks (usually) but
rather GROUPS of marks. So we still may not know WHICH mark to set
true, but we definitely know which marks to set false.

You might get something like this:

"weak link to almost-locked sets r4c5 r5c5 r6c5 and r8c5 mutually doubly-linked by 1,4"

Did you describe that somewhere, bennys? It would be great if you
identified where in this implementation your descriptions match. I sort
of got lost in the flurry of threads there.

Stage 2a: Medusa

As the strong chains are identified, by adding nodes one at a time, we also
add nodes associated with almost-locked sets. This happens in function
addALSWeakNode(), and this finds any elimination that might be caused
by a SINGLE strong chain inconsistency -- a node that is already part of
the chain identified as being in BOTH chain parities, or a node that can't be
added to a chain because it would be weakly linked to BOTH chain parities.

This is based on the idea that if a strong chain node is weakly linked to an
almost-locked set, then it is also weakly linked to ANY other node that is
weakly linked to that almost-locked set. (Whew!)
Code:

         w
         |
     X---A---k ...ichain(iparity)
         |
         z

   add all weak nodes of A except of k to strong chain as weak nodes


Eliminations here look something like this:

Code:

         w
         |
     X---A---k ...4(D)
         |        :
         z.........


"4(D) can be eliminated -- incompatible strong M-cycle involving nodes r5c8#4 chain 4(D) and r6c5#4 chain 4(D)
via ALS 4-Col { r7c1 r8c1 } { r2c4 r5c4 r7c4 r8c4 } { r2c6 r7c6 r8c6 } { r6c7 r8c7 }"

Oooh, this is a nice one! It means that while chain 4(D/d) was being
constructed, the two ends of 4(D) were found to be buddies. They can't
both be TRUE, so that chain parity can be eliminated. The incompatibility
was via one of those weak links to the X-type almost-linked set consisting
of the possibilities for 4 in columns 1, 4, 6, and 7 and rows 2, 5, 6, 7, and 8.
This is what I was referring to as your idea "in another dimension." See
http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#almost
for an explanation.

Also caught here are "weak corners" -- nodes that are weakly linked to
BOTH parities of a developing chain.

Code:

         w
         |
     x---A---k ...5(E)
         |       
         z........5(e)

   weak links to w and x can be eliminated



"r8c9#8 is incompatibly weakly linked to 5(E) involving
nodes r3c5#8 chain 5(e) and r6c9#9 chain 5(E) via ALS r1c9 r5c9 r9c9"

This happens because, for example, we have already identified weak links
to w and x as a weak links to chain 5(e). So when we try to add, say,
another weak link to 5(E), then we can't to it. (I think that's right.)

Stage 2b:

After all the strong chains have been identified and have been found to be
self-consistent, and the additional weak links have been added, we are
basically done. The same system that finds link problems to weakly-linked
strong chains will process these additional links as well. This is done in
weak.js, by functions addWeakCheck() and checkWeakLinks().

At this stage we are implementing Medusa to its full level. This is
where we check for impossible long-range connections, finding things like:
Code:

      x.....1       |
      .     -2*-----2-
      .             |
      .             |
      .             |
      .             |
     -1*----------1---
                   :|
                    2*
                    |

   x can be eliminated


or

Code:

    |
   -3*---3-
    |    -4*--4--
    |          5*
    |         /
    |        /
    3       5  (r3c5)
    |\       :
    | 6*......6 (r3c5)

  r3c5#6 can be eliminated


Unfortunately, because the ALS links have been integrated into the chains,
when multiple-chain links are found, they may not be flagged as having
anything to do with ALS.

This points to one of the odditites of Medusa -- once the chain relationships
are established, one can't easily trace back exactly how a particular
connection was made -- a "cycle". The cycle is there, for sure, but it is
never specifically identified. There are probably lots of different "routes"
from one end to the other, any one of which would constitute a valid
cycle. One might be able to identify the SHORTEST route, but I haven't
taken the time to figure out how to do that.

The eliminations at this stage just look something like this:

"chain 4(d) can be eliminated due to conflicting weak link to chain 3(c)"

or

"r3c3#7 eliminated: weak corner eliminated by both 7(G) and 7(g)--8(h)"

I know, not that helpful.... But a study of the chain table will tease out
what was going on, I think.

One more thing:

In the current implementation, the function checkWeakAlmostLocked()
is called from weak.js during the standard weak link check, just after
addWeakCheck() and just before checkWeakLinks(). But as
far as I can tell, it finds nothing. I don't think there is an error there. I
think this is just redundant. We have already accounted for the almost-
locked sets in terms of strong chains, so now we are beyond that, just
looking for incompatible chain connections.

Caveate:

I think there are still some almost-locked set ideas that are not found
by any of these checks. Things like weakly linked "chains" of almost-locked
sets wrapping around and eliminating something.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving 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