View previous topic :: View next topic |
Author |
Message |
| Pep
| Joined: 27 Nov 2005 | Posts: 10 | : | Location: Bath, UK | Items |
|
Posted: Sun Nov 27, 2005 4:54 pm Post subject: Is this an x-constraint? |
|
|
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 |
|
|
| Pep
| Joined: 27 Nov 2005 | Posts: 10 | : | Location: Bath, UK | Items |
|
Posted: Sun Nov 27, 2005 6:11 pm Post subject: I have the answer |
|
|
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 |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Mon Nov 28, 2005 4:45 am Post subject: Re: I have the answer |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
Posted: Mon Nov 28, 2005 9:49 am Post subject: |
|
|
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 |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Mon Nov 28, 2005 11:39 am Post subject: |
|
|
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 |
|
|
| Ruud Site Admin
| Joined: 17 Sep 2005 | Posts: 708 | : | Location: Netherlands | Items |
|
|
Back to top |
|
|
| Pep
| Joined: 27 Nov 2005 | Posts: 10 | : | Location: Bath, UK | Items |
|
Posted: Mon Nov 28, 2005 6:00 pm Post subject: Interesting range of tehniques |
|
|
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 |
|
|
| rkral
| Joined: 21 Oct 2005 | Posts: 233 | : | | Items |
|
Posted: Tue Nov 29, 2005 5:28 pm Post subject: Re: Interesting range of tehniques |
|
|
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 |
|
|
| Pep
| Joined: 27 Nov 2005 | Posts: 10 | : | Location: Bath, UK | Items |
|
Posted: Tue Nov 29, 2005 7:26 pm Post subject: |
|
|
Thanks rkral for the reference. Interesting. |
|
Back to top |
|
|
| Bob Hanson
| Joined: 05 Oct 2005 | Posts: 187 | : | Location: St. Olaf College | Items |
|
Posted: Fri Dec 02, 2005 4:11 pm Post subject: |
|
|
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 |
|
|
|