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   

Constraint subsets
Goto page Previous  1, 2
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Wed Dec 21, 2005 9:26 am    Post subject: Reply with quote

Quote:

P(...) has two meanings:
P(R1C2S3) is a straightforward placement
P(Ti) is a mapping of ALL Placements that met by ANY Tests in set Ti

Maybe it is better to use the lowercase "p" for the first meaning.


Mapping of Union ?

I think i am missing something.
I think mapping can be replaced by union without any difference in meaning. (union is a more mathematical term while mapping is more a programmers term, as long as the definition of a mapping is not reduced to a 1 to 1 function / mapping)



After having a good night sleep Rolling Eyes

I think thar Union is a better word to describe it.
P(Ti) is the union of ALL Placements that are met by ANY Tests in set Ti.


If you would like to have it all in set-speak

P(R1C2S3) is the intersection of All placements that meet ALL the tests inbedded in R1C2S3 ; T(R1C2) , T(R1S3), T(C2S3) and T(B1S3)
(and that is only the placement R1C2S3) (the B1 follows out of R1C2)


Reasons for P(...) and T(...)

I want to keep a clear distinghsion between Tests and Placements, I am wary for non-statements like "a test is a union of placements" and "remove from this set of tests the following placements..." (sets can only contain Tests or Placements, not both.)


In my terminology all Graph-speak is gone, maybe that is what makes it easier.


Quote:

This is all very helpful. So is the "729x324 matrix" at

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

about right?

Crashed mine as well...

But if it is 729 x324 not a lot can be wrong.
(except ....)
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Dec 21, 2005 9:42 am    Post subject: Reply with quote

Quote:


P(Ti) is the union of ALL Placements that are met by ANY Tests in set Ti.


don't you mean : the set of all placements ... ?

Quote:


P(R1C2S3) is the intersection of All placements that meet ALL the tests inbedded in R1C2S3 ; T(R1C2) , T(R1S3), T(C2S3) and T(B1S3)
(and that is only the placement R1C2S3) (the B1 follows out of R1C2)



sorry.Placements are sets ? What are their elements ?
give exact definitions first.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Dec 21, 2005 10:39 am    Post subject: Reply with quote

I've been very busy lately, and coming back here surprised to see how this topic has taken off.

Thanks, Bob, for reviving the topic.

A few notes concerning the previous posts:

Attempting to show the matrix in Sudoku Assistant 'hangs' my browser, so there is something left to be done, Bob. I like the exact cover explanation and examples you have placed on your site. However, I'm not sure that the majority will understand it.

Seems like each time we're in the border area of Sudoku and Math, the terminology war flames up. I really don't care what anyone calls this, as long as we are able to expand our knowledge of solving Sudokus.

For me, this has been an exercise with hope of discovering 'new' solving techniques. When all existing techniques can be defined in these terms, we must be able to apply the constraint subset technique to discover uncharted solving methods, rename them and optimize the code to look specifically for those situations. As far as I'm concerned, I'm not interested in the math aspect of this, just in the levels of abstraction that it gives us.


My progress so far:

Since I posted this topic, I've built a new program that solves Sudokus only using an Exact-Cover-Matrix with Constraint-Subsets as the only technique. It is very much in the testing stage, but so far, it works like a charm.

One thing I've been able to use the new program for is to assess the difficulty of a Sudoku. I did always believe that the difficulty of a sudoku was only defined by the solving techniques required, but for the easier Sudokus (the ones you find in puzzle books and newspapers), there must be a classification for Sudokus that require singles only. With this new program, I've been able to determine how many 'rounds' are required to solve a sudoku, and what the minimal complexity in each round is. For clarity: a 'round' contains alle the new candidates you can place or eliminate based solely on the state of the previous round. Testing this on a large number of published Sudokus, gave me the following results:

Easy (*) - 4 rounds average (singles only)
Medium (**) - 6-7 rounds average (singles only)
Hard (***) - 9-10 rounds average (constraint sets size 1 only, singles + locked candidates)
Very Hard (****) - 12-13 rounds (constraint sets upto size 2)

For comparison, I took a few 17 clue sudokus: 16-18 rounds (singles only)

So, even if we think a Sudoku is easy because it does not require any advanced solving techniques, the large public does not know about these techniques. It counts the time spent on searching for openings. A sudoku with only a few rounds has lots of discoveries available to the puzzler. A Sudoku with many rounds requires more time because at various stages there is only a single elimination or placement that will advance the puzzle.

Enhancing the program to discover all constraint subsets is the next phase. Much of the code is already in place, and I will keep you informed of the status.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Wed Dec 21, 2005 11:51 am    Post subject: Reply with quote

dukuso wrote:
Quote:


P(Ti) is the union of ALL Placements that are met by ANY Tests in set Ti.


don't you mean : the set of all placements ... ?

Quote:


P(R1C2S3) is the intersection of All placements that meet ALL the tests inbedded in R1C2S3 ; T(R1C2) , T(R1S3), T(C2S3) and T(B1S3)
(and that is only the placement R1C2S3) (the B1 follows out of R1C2)



sorry.Placements are sets ? What are their elements ?
give exact definitions first.



O Sorry i am less exact than i thought. ( I should fresh up my set speak)

P(...) a placementSET (elements are placements)
placement R1C2S3 an element of a placementSET

P(R1C2S3) a PlacementSET with ONE element, the Placement R1C2S3

Union or set?
OK i must agree with you. ... It is a set.

P(Ti) is the set of ALL Placements that are met by ANY Tests in (test)set Ti.

T(Pj) is the set of ALL Tests that are met by ANY Placement in (placement)set Pj.


P(T(Pj))
Is the set of ALL Placements that are met by ANY Tests in (test)set T, wich is the set of ALL Tests that are met by ANY Placement in (placement)set Pj.
or
Is the set of ALL Placements that are met by ANY Tests that are met by ANY Placement in (placement)set Pj. (This is including all the placements in Pj itself)

Is this correct...?
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Wed Dec 21, 2005 12:09 pm    Post subject: Reply with quote

Soduko, it might be correct, but I don't like it ;-)


Ruud, I'd be interested how this relates to hyper arc consistency:

for each cell x and each candidate s for x
check whether there are valid candidates s1,s2,..,s9 for
the other cells x1,..,x9 in that row,column,block
(including x, assuming x=xi)
such that s_i=s and all the s_j are different.
If not, then you can remove s as a candidate for x


Same for columns, blocks.

(I hope I got this right)
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

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

Items
PostPosted: Wed Dec 21, 2005 12:45 pm    Post subject: Reply with quote

Really! You mean the whole page or just that link? Please tell me more. This is the first anyone has said that. I've been using Opera for development because it is so error-trace friendly. I'll go try a couple of others. Please do tell me what your platform/browser is. I hate to crash browsers!
_________________
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
Bob Hanson

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

Items
PostPosted: Wed Dec 21, 2005 1:21 pm    Post subject: Reply with quote

this forum thread may be corrupted -- First I didn't see my latest response, then when I reply I see that one but not the one before it.

Anyway, in response to crashing browsers -- I see that MSIE was taking huge amounts of time to contatenate all those strings -- I turned the strings into arrays and now MSIE loads the 729x324 matrix very quickly.

Please try it again if you were using MSIE and it was taking a LONG time to load (could be perceived as a browser crash).
_________________
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
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Wed Dec 21, 2005 3:17 pm    Post subject: Reply with quote

dukuso,
I've found this link: http://www.cse.unsw.edu.au/~cs4418/Lectures/cpnotes/krr2.html
It explains hyper-arc consistency a little further. As I said, I'm not a mathematician, but I'll spend some time studying it. The other stuff in this lecture is also very interesting...

It looks like the same principle, but from a single variable (=cell) perspective. In the constraint subset model, multiple constraints are combined in a set and compared to a second set. AFAIK this is not covered by hyper-arc consistency.

Bob,
this forum is just very slow. Then it tends to skip parts. If you're lucky, it skips the ad banners. If you're unlucky, it skips content.

The Matrix on your site is working now. You could (like DLX does) remove rows that were eliminated. You could also (as an option) remove columns for constraints that are satisfied. Remains the matrix of unsolved rows and columns. That is the only part we are interested in, anyway.

One request: could you update the link from your site to my new website http://www.sudocue.net? I've moved all the Sudoku stuff to this new site.

Thanks.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
soduko

Joined: 10 Oct 2005
Posts: 50
:

Items
PostPosted: Wed Dec 21, 2005 3:46 pm    Post subject: Reply with quote

To Bob:

It looks OK but the table is a bit to big

Maybe it is an option to have a second smaller table where:

All Rows (placements) that are blocked are gone
All Rows (placements) that are placed are gone. (they are not needed anymore)

All Collums (tests) that are met are gone (they are not needed anymore)


So that only remains the placements that are under concideration
and the Collumns that are not satisfied

The removal of rows should not be to difficult I hope.
The removal of collumns maybe more difficult.
Back to top
View user's profile Send private message
Bob Hanson

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

Items
PostPosted: Wed Dec 21, 2005 3:58 pm    Post subject: Reply with quote

I did that removal on the "Ruud-like" Very Happy "possibilities" page. I wasn't sure I
should do that on the exact-cover page because the idea there is to end up
(I thought) with all 1s, not all gone. And I kind of like the idea that there
are always 729x324 columns.

I'm quite intrigued that the realization that the recursive function I use on
that site basically takes a subset of the 729x324 matrix and does an exact
cover analysis -- not dancing links, of course, but essentially the exact
cover analysis.

So I see where your intersecting sets business is coming from now. It's all the same thing, istn't it? Just written in different forms.

I'm also intrigued by the fact that the sort of analysis humans do -- subset
elimination and such -- amounts to "permanent" elimination, while the
whole dancing links thing is obviously geared toward reversible elimination.
I guess I don't see why the dancing links wouldn't be improved by a few
"more than singles" analysis that would make some eliminations permanent.

Or, put another way, if one knows (or presumes) that one is working with
a valid puzzle (unique solution), then surely dancing links is overkill.
There is no need to have the capability to find ALL solutions, just one. So I see where your intersecting sets business is coming from now. It's all the same thing, istn't it? Just written in different forms.

Not that I really understand dancing links, yet, but I'm catching on.

Website link is updated. Thanks.
_________________
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
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Dec 22, 2005 1:35 am    Post subject: Reply with quote

I don't think it's overkill for single solution puzzles.
These techniques which make use of it rarely apply.
It's probably not efficient to look for them.

Of course, once you found the solution you can stop.
This typically gives you a speed-factor of 2.

But when you are unlucky the solution appears near the
end of the backtracking and you have to walk through the whole search-space, just as if you were going to prove that there is no solution,
or when you count solutions. Same algo.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Bob Hanson

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

Items
PostPosted: Thu Dec 22, 2005 1:53 am    Post subject: Reply with quote

Knuth showed that judicious choice of starting constraint -- one with the
fewest number of candidates -- dramatically speeds the DLX algorithm. Thus,
clearly, the algorithm can be optimized. This is proven. His choice of
optimization is reasonable, but somewhat arbitrary.

One could therefore imagine that, say, judicious choice of a PAIR of constraints
to cover simultaneously, for example, might especially speed the solution,
particularly when there is a large ratio of "unnecessary:necessary" candidates
present.

There are all sorts of possible optimizations one could do. One could first
look for subsets to eliminate, for example. Who is to say -- without proof --
that this would NOT speed the algorithm.

It would be interesting to see what subset elimination would look like in
the DLX context.
_________________
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
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Thu Dec 22, 2005 5:53 am    Post subject: Reply with quote

Bob Hanson wrote:
Knuth showed that judicious choice of starting constraint -- one with the
fewest number of candidates -- dramatically speeds the DLX algorithm. Thus,
clearly, the algorithm can be optimized. This is proven. His choice of
optimization is reasonable, but somewhat arbitrary.

Not arbitrary at all. This is the only way to ensure that candidates for which one of the 4 constraints is met, immediately takes care the other 3 constraints that the candidate competes in. This behaviour is vital for the DLX algo.

Once the size-1 constraints have been covered, the smallest size is still chosen. Again, not an arbitrary choice, because it would focus on strong pair first, having more impact than constraints with more remaining candidates. It all makes sense.

I've optimized the DLX algorithm to prefer the constraint with the smallest number of candidates, but where these candidates have the largest total number of "competitors" (in the other 3 constraints).
This ensures that each candidate, when "covered", eliminates the maximum number of other candidates. This should reduce the remaining number of iterations.

Quote:
One could therefore imagine that, say, judicious choice of a PAIR of constraints
to cover simultaneously, for example, might especially speed the solution,
particularly when there is a large ratio of "unnecessary:necessary" candidates
present.


I imagine this is what I already do with this optimization.

Quote:
It would be interesting to see what subset elimination would look like in
the DLX context.


I do have an idea what it would look like. The algorithm should, in each iteration of its recursive loop, have an "exit" to apply "advanced" logic, with a local stack of candidates eliminated. This elimination can be done in the same manner as the "cover" method that DLX itself uses.

When backtracking from deeper iterations, the stack is used to reverse the eliminations done in that particular iteration, using the "uncover" method of DLX.

Building the architecture to insert advanced logic into DLX is not the problem. The real problem is how to make these methods fast enough to compete with the mindless speed of DLX. You'd have to implement searches where there were none, even when the search might not yield any result. When we are able to narrow down the search and avoid duplicate searches, then we may have a possible improvement.

Ruud.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Goto page Previous  1, 2
Page 2 of 2

 
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