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   

Is this an x-constraint?

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

Joined: 27 Nov 2005
Posts: 10
:
Location: Bath, UK

Items
PostPosted: Sun Nov 27, 2005 4:54 pm    Post subject: Is this an x-constraint? Reply with quote

Just to introduce myself.

Since I've come late to disuccing anything about Sudoku on the net I'm way behind you all, but I seem to have come up with some of the techniques that I read about here independently, although described in differnet terminology. (Is there a glossary anywhere?)

My attempt at a solver is at http://www.pepperdine.eclipse.co.uk

Before anypne comments, let me say that I know full well that my implementation of what i've called "nets" is not complete (it ignored bocxes at the moment), and also that the preconditions I give are more strict than necessary.

Also, that what I've called "chains" and "twins" are subsets of various colo(u)ring techniques, but I knew that before finding out what they were today. At least I think so.

My question is where does my rule "chains" fit in to your classifications. It is not clear that it is exclusively an x-constraint, unless the descriptions I've found are incomplete, or I've misunderstood.

If there exists a closed cycle of row/col/boxes such that: the number of links is even, and a candidate V occurs at the vertices of the cycle only in alternate links, then all other occurrences can be removed the remaining links.

Is this included?

An example:
.5. .21 79.
27. ... .51
13. .57 .26

.67 1.. 582
5.2 87. 16.
.81 265 9.7

..5 .12 .7.
72. 5.. .19
.1. 796 2.5
Back to top
View user's profile Send private message
Pep

Joined: 27 Nov 2005
Posts: 10
:
Location: Bath, UK

Items
PostPosted: Sun Nov 27, 2005 6:11 pm    Post subject: I have the answer Reply with quote

Oh dear, what a terrible start. My apologies.

First, I now have the answer. The case is included.

Second, I pasted in the wrong example. The one I meant is:
... .7. 569
5.9 82. 137
..7 9.. ...

4.8 6.9 ..1
.76 ... 9..
9.. 2.7 6.8

.92 7.3 ..6
7.. .6. .9.
6.. .9. ...

and look at candidate 5.
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Nov 28, 2005 4:45 am    Post subject: Re: I have the answer Reply with quote

Pep wrote:
and look at candidate 5.


Interesting puzzle. If r3c5=5, all candidate 5's in box 5 are eliminated. Therefore, r3c5<>5.
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Nov 28, 2005 9:49 am    Post subject: Reply with quote

rkral wrote:
Interesting puzzle.

Agree. With all features in Sudo Cue active, it finds:

- A few line-box interactions.
- A hidden pair {2,8} in box 1.
- Multi-coloring digit 3 eliminating r1c3, r3c5, r5c4

And very unusual, 3 template checks in a row:

- r9c6 eliminated for digit 1 by template check.
- r9c8 eliminated for digit 4 by template check.
- r3c5, r5c5, r5c6, r5c8, r8c6, r9c6, r9c8 eliminated for digit 5 by template check.

First template check that I ever encountered with 7 candidates eliminated.

Ruud.
Back to top
View user's profile Send private message Visit poster's website
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Mon Nov 28, 2005 11:39 am    Post subject: Reply with quote

Ruud wrote:
First template check that I ever encountered with 7 candidates eliminated.

Would you please recommend a discussion or tutorial for that technique?

TIA, Ron
Back to top
View user's profile Send private message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Mon Nov 28, 2005 3:15 pm    Post subject: Reply with quote

Ron wrote:
Would you please recommend a discussion or tutorial for that technique?
Both.

This is the discussion we had on this forum:
http://www.setbb.com/phpbb/viewtopic.php?t=241&postdays=0&postorder=asc&start=0&mforum=sudoku

Here is a link to the "Templates" topic on my Sudo Cue site:
http://home.quicknet.nl/qn/prive/r.vanderwerf/templates.htm

Ruud.
Back to top
View user's profile Send private message Visit poster's website
Pep

Joined: 27 Nov 2005
Posts: 10
:
Location: Bath, UK

Items
PostPosted: Mon Nov 28, 2005 6:00 pm    Post subject: Interesting range of tehniques Reply with quote

There are an interesting range of techniques here. My opinion, if I dare say, is that the templat technique would be fine for generating problems quickly, but not much use to explain to someone how a solution can be derived.

The example I gave, as you have said, is rare. My program found it when I explicitly asked it to search for x-constraints of a certain type. There is a cycle of (row/col/box) through

Code:
r5 - c9 - box9 - r7 - box8 - c4 - r5


where the even numbered ones have 5 restricted to the intersections with the neighbo(u)rs. This forces the elimination of 5 at
Code:
r5c5, r5c6, r5c8, r8c6, r9c6, r9c8


The cycle is unusual in that several of the intersections still have more than one cell where 5 is a candidate. It can only be found using the intersections, and not by following single cell links.
Back to top
View user's profile Send private message
rkral

Joined: 21 Oct 2005
Posts: 233
:

Items
PostPosted: Tue Nov 29, 2005 5:28 pm    Post subject: Re: Interesting range of tehniques Reply with quote

Pep wrote:
My program found it when I explicitly asked it to search for x-constraints of a certain type. There is a cycle of (row/col/box) through

Code:
r5 - c9 - box9 - r7 - box8 - c4 - r5

Nice find. I posted your puzzle in a constraint subsets forum, which you might find to be an interesting read.
Back to top
View user's profile Send private message
Pep

Joined: 27 Nov 2005
Posts: 10
:
Location: Bath, UK

Items
PostPosted: Tue Nov 29, 2005 7:26 pm    Post subject: Reply with quote

Thanks rkral for the reference. Interesting.
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 02, 2005 4:11 pm    Post subject: Reply with quote

pep -- something it took me a while to discover here -- you can EDIT your post after you make it. No need to apologize!

Nice example, though. Sudoku Assistant, http://www.stolaf.edu/people/hansonr/sudoku solves this any number of ways, including, what I think is really nice, just with Y-cycles:

Solving

.5. .21 79.
27. ... .51
13. .57 .26

.67 1.. 582
5.2 87. 16.
.81 265 9.7

..5 .12 .7.
72. 5.. .19
.1. 796 2.5

Cross checking
32 cells left to solve; 49 clues; 597 tidbits of information
[snapshot 10]
Checking block ranges
Checking for subset elimination
Checking for grids
Checking strong chains
14 strong chains
Checking for weak links
37 weak links
69 weak corners
r7c9 ISN'T 3: weak 1/1 corner between linked 0/0 strong chains 8 and 12
r7c7 ISN'T 3: weak 1/1 corner between linked 0/0 strong chains 12 and 14

Done! (16 steps) Y

658 421 793
279 638 451
134 957 826

367 149 582
592 873 164
481 265 937

945 312 678
726 584 319
813 796 245

That snapshot 10 looks like this:

Code:

   |---c1--|---c2--|---c3--||---c4--|---c5--|---c6--||---c7--|---c8--|---c9--
-----------------------------------------------------------------------------
r1 |   468 |     5 |   468 ||   346 |     2 |     1 ||     7 |     9 |   348
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r2 |     2 |     7 |    69 ||    69 |   348 |   348 ||    34 |     5 |     1
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r3 |     1 |     3 |   489 ||    49 |     5 |     7 ||    48 |     2 |     6
   |       |       |       ||       |       |       ||       |       |       
===========================||=======================||=======================
r4 |   349 |     6 |     7 ||     1 |    34 |   349 ||     5 |     8 |     2
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r5 |     5 |    49 |     2 ||     8 |     7 |   349 ||     1 |     6 |    34
   |       |    cC |       ||       |       |       ||       |       |    dD
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r6 |    34 |     8 |     1 ||     2 |     6 |     5 ||     9 |    34 |     7
   |       |       |       ||       |       |       ||       |       |       
===========================||=======================||=======================
r7 |   469 |    49 |     5 ||    34 |     1 |     2 ||  3468 |     7 |   348
   |       |    Bb |       ||    Aa |       |       ||       |       |   *   
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r8 |     7 |     2 |   346 ||     5 |   348 |   348 ||   346 |     1 |     9
   |       |       |       ||       |       |       ||       |       |       
---+-------+-------+-------||-------+-------+-------||-------+-------+-------
r9 |    48 |     1 |   348 ||     7 |     9 |     6 ||     2 |    34 |     5
   |       |       |       ||       |       |       ||       |       |       
-----------------------------------------------------------------------------



r7c9#3 is eliminated due to the Y-cycle starting at r7c4#3A and ending at r5c9#3d.

Very nice!
_________________
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