FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Generalized X-Wing - Does this also work for Swordfish? Goto page 1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Tue Nov 01, 2005 4:46 pm    Post subject: Generalized X-Wing - Does this also work for Swordfish? I've not often heard mention on these forums of the Generalized X-Wing notes on this website by jef vandenberghe: http://users.pandora.be/vandenberghe.jef/sudoku/index.html?how2solve. People always talk about finding X-Wing's by searching rows and columns - but never blocks! I guess this is because the Locking Candicates technique (also called Single Unit Candicate) finds the eliminations so the generalised X-Wing technique is not required. I now have 2 questions: 1) Firstly, are there any situations where looking for X-Wings by boxes is useful? That is situations where other methods would not find the same eliminations. and 2) Can looking by boxes also apply to Swordfish patterns, or is this mathematically/logically impossible due to the 2-Dimensional constraint of Sudoku? Kranser. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Tue Nov 01, 2005 7:52 pm    Post subject: First, yes, it is important to look for these. They are basically under the category of "block range exclusions". Second, no, I don't think there is an extension to Swordfish, because a standard 9x9 Sudoku has only 3 3x3 blocks across. That means that while two of those columns may be void of candidate values, leading to the generalized X-wing thing, there is no possibility of all three columns being void. So Swordfish are out -- they would require a fourth column. I guess a 16x16 with 4x4 blocks would have this, though. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Tue Nov 01, 2005 9:02 pm    Post subject: Bob Hanson wrote: First, yes, it is important to look for these. They are basically under the category of "block range exclusions". . So if a solver implements "block range exclusions" (i.e. Locked candidates/Single unit candidate) then there is no need for block-x-wing, correct? Bob Hanson wrote: Second, no, I don't think there is an extension to Swordfish, because a standard 9x9 Sudoku has only 3 3x3 blocks across. That means that while two of those columns may be void of candidate values, leading to the generalized X-wing thing, there is no possibility of all three columns being void. So Swordfish are out -- they would require a fourth column. I guess a 16x16 with 4x4 blocks would have this, though. Yes, I guess if would occur in 16x16 puzzles (onwards and upwards). But would these cases also be like the x-wing case where the situation is already catered for by locked candidates? Actually, do any solvers handle block-x-wing specifically? kranser. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Tue Nov 01, 2005 9:50 pm    Post subject: Well, I think that would depend upon the solver. I had to introduce it independently in the Sudoku Assistant. http://www.stolaf.edu/people/hansonr/sudoku. My notes suggest that there are puzzles that require such. But now I'm not so sure. The problem is this: Code:          block  1          block 2         block 3 row 1 [ ---- x -----] [ ---- x -----] [ ---- x -----] row 2 [ ---- x -----] [ ---- x -----] [ ---- x -----] row 3 [ --- no x ---] [ --- no x ---] [ ---- [b]x[/b] -----] Candidate x is possible in 7 of the nine row subsets of these three rows. But since it is not possible in blocks 1 and 2 row 3, it must be in block 3 row 3. So then it can't be in block 3 rows 1 or 2. Same goes for columns, of course. I had to code for this specially, but that was one of the first codings I did on this, and I'm not proud of it. I'll see if I can find a puzzle that needs this. _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Wed Nov 02, 2005 5:57 pm    Post subject: Bob Hanson wrote: My notes suggest that there are puzzles that require such. Coloring (ala Angus Johnson's Simple Sudoku) will exclude all candidates that x-wing will, so x-wing is not really necessary to solve puzzles. However, x-wing is usually employed in solver programs to "emulate human methods". In general, I agree with your description. However, the alternative diagram below might be helpful to others. Code:  .  .  .  | .  .  .  |  .  .  .  .  .  .  | .  .  .  |  .  .  .  .  .  .  | .  .  .  |  .  .  .  ---------+----------+---------  .  A  .  | .  B  .  |  *  *  *  .  .  .  | .  .  .  |  .  .  .  .  .  a  | .  .  b  |  *  *  *  ---------+----------+---------  .  .  .  | .  .  .  |  .  .  .  .  .  .  | .  .  .  |  .  .  .  .  .  .  | .  .  .  |  .  .  . Aa and Bb represent the conjugate (strong) pairs in box 4 and box 5, respectively. In this example, AB and ab are non-conjugate (weak) pairs on rows 4 and 6, respectively. Since Aa and Bb are known to be conjugate pairs, we already know no other candidates exist in box 4 and box 5. After all, that's presumably how we got the above diagram. If A is true, then candidates may be excluded from r4c7, r4c8, and r4c9. Since A is true, B is false and 'b' must be true, excluding candidates from r6c7, r6c8, and r6c9. If A is false then 'a' is true, again excluding candidates from r6c7, r6c8, and r6rc9. And since 'a' is true, then 'b' is false and B must be true, again excluding candidates from r4c7, r4c8, and r4c9 I'm not aware of any possible exclusions when either A and B are on different rows OR 'a' and 'b' are on different rows. Off topic: I could use a little help in getting started programming "chaining". I've seen terms such as "forced chain", "implication chains", etc. suggesting several methods exist. I generally can follow and understand the examples of others, but I've never found one on my own (leading to an exclusion or a fill). Any suggestions on where and how to start would be greatly appreciated. TIA, Ron Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Wed Nov 02, 2005 6:33 pm    Post subject: Looking at your example: Code: . . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . . -----+-----+----- . A .|. B .|* * * . . .|. . .|. . . . . a|. . b|* * * -----+-----+----- . . .|. . .|. . . . . .|. . .|. . . . . .|. . .|. . . I find that all candidates for row 5 are locked in box 6. This would eliminate the * candidates with a simple line-box interaction check. Ruud. Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Wed Nov 02, 2005 10:02 pm    Post subject: Ruud wrote: I find that all candidates for row 5 are locked in box 6. This would eliminate the * candidates with a simple line-box interaction check. Thanks for pointing that out. My original plan was to post the following example, but decided to "simplify" it at the last minute. Code: . . .|. * .|. . . . . .|. * .|. . . . . .|. * .|. . . -----+-----+----- . A .|. B .|* * * . . .|. . .|. . . . . a|. b .|* * * -----+-----+----- . . .|. * .|. . . . . .|. * .|. . . . . .|. * .|. . . But even here, box 5 has a lock on the candidates for col 5. So I'm now again thinking it is sufficient for x-wing to handle only the classical pattern ... Code: . * .|. . .|. * . . * .|. . .|. * . . * .|. . .|. * . -----+-----+----- . A -|- - -|- a . . * .|. . .|. * . . * .|. . .|. * . -----+-----+----- . * .|. . .|. * . . B -|- - -|- b . . * .|. . .|. * . ...when used in conjunction with locked routines. Do you agree? As before, (*) marks the potential exclusions. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Wed Nov 02, 2005 10:32 pm    Post subject: rkral wrote: So I'm now again thinking it is sufficient for x-wing to handle only the classical pattern ... when used in conjunction with locked routines. Do you agree? Yes. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Wed Nov 02, 2005 11:00 pm    Post subject: I second this opinion. Back to top xyzzy Joined: 24 Aug 2005 Posts: 80 : Items Posted: Thu Nov 03, 2005 12:23 am    Post subject: These row/col and box intersection exist in a complementing nature just like subsets. Suppose for a given digit, a row only intersects one box. Now that digit can be removed from all other rows intersecting that box. Since each box is three rows, "all other rows" will always be two rows. It will also be the case that for the other two boxes that intersect the row, the location for the digit will fall on just two rows. These two rows are the same "all other rows" from above. Now the digit can be cleared from the box other than the two that intersect the rows, which was our original box from before. Call the first row where the intersection happened row R, and the two rows that also intersect the same box rows R'. Call the box where the intersection happened box B, and the two other boxes that intersect the row boxes B'. You can now generalize this rule as: If a digit only exists in R at the intersection of R and B, then it can be cleared from the intersection of R' and B. It will also be the case that the digit will only occur in B' in the intersection of B' and R', and so again it can be cleared from the intersection of B and R', which is of course the same as R' and B. Like subsets, it's only necessary to look for a intersections of size N/2, as any intersection of size > N/2 will have a compliment less than N/2. In 9x9 sudoku there are only three intersections for a row and boxes, so N is 3, and the largest size that needs to be searched for is 3/2 = 1. In 16x16 sudoku N=4, and so both size 1 and 2 need to be searched for. Consider this 16x16: Code: . . * . | . * . . | . . . . | . . . . * . * . | . . . . | * . . * | . . . . . . . . | * * * . | * * . . | . . . . x x x x | x x x x | x x x x | + . + . The *, x, and + are all the places a digit can go. If you look at the first three rows, you'll see that all the locations (the *'s) are in just three common boxes. This means all the locations in those boxes not in those three rows can be eliminated (this is the x's). You can also see the compliment in the fourth box, as all locations in that box (the +'s) are in a single row. This means all the locations in that row not in the box (again the *'s) can be eliminated. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Nov 03, 2005 1:55 am    Post subject: There is one other interesting aspect to these line/box intersections: They automatically take care of hidden/naked subsets that lie within the intersections. These subsets can be pairs or triples. For a 16x16 they could also be quads. Ruud. Back to top kranser Joined: 18 Aug 2005 Posts: 35 : Items Posted: Thu Nov 03, 2005 10:21 am    Post subject: angusj wrote: rkral wrote: So I'm now again thinking it is sufficient for x-wing to handle only the classical pattern ... when used in conjunction with locked routines. Do you agree? Yes. So I assume that as Swordfish and Jellyfish are just extensions to X-Wing, that this truth also applies to Generalised Swordfish and Jellyfish patterns in grids larger than 9x9. So we can all just concentrate on the classical X-Wing patterns! Kranser. Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Thu Nov 03, 2005 12:39 pm    Post subject: kranser wrote: So I assume that as Swordfish and Jellyfish are just extensions to X-Wing, that this truth also applies to Generalised Swordfish and Jellyfish patterns in grids larger than 9x9. I hesitate to generalize, but suspect that is true for the swordfish in a 16x16 and for the jellyfish in a 32x32. (As if anybody has ever ventured into that nigntmare.) But consider the following special case of the swordfish. The restrictions that make it special are: 1) two columns are in the same box, and 2) each row contains a conjugate pair. Code:  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  A  .  | a  .  .  |  .  .  .  ---------+----------+---------  .  *  .  | *  .  *  |  .  .  .  .  .  .  | B  .  b  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  ---------+----------+---------  .  c  .  | .  .  C  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  . If A is true, then B and C are also true. Similarly, if a is true, then b and c are also true. From a coloring perspective, A, B, and C have identical coloring ... and a, b, and c bear the conjugate coloring. Now let's move the 'b' to a different row within box 5 as follows: Code:  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  A  .  | a  .  .  |  .  .  .  ---------+----------+---------  .  *  .  | .  .  b  |  .  .  .  .  *  .  | B  .  .  |  .  .  .  .  *  .  | .  .  .  |  .  .  .  ---------+----------+---------  .  c  .  | .  .  C  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  . As before ... If A is true, then B and C are also true. Similarly, if a is true, then b and c are also true. From a coloring perspective, A, B, and C have identical coloring ... and a, b, and c bear the conjugate coloring. And as with the "classical" swordfish, exclusions of candidates can be made in other rows of the columns that define the pattern. So is the pattern a "4x3 swordfish" or a "4x3 jellyfish"? Neither? If pushed to give it a name, I guess I'd choose "4x3 swordfish". But whatever it is, even a single digit coloring algorithm should make the exclusions(*) shown. Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Thu Nov 03, 2005 1:14 pm    Post subject: rkral wrote: And as with the "classical" swordfish If you think the the "classical" swordfish consists of conjugate pairs in three rows (or columns) then I'll have to disagree with you. A swordfish can have two or three candidate cells in each of the three rows (or columns) and, as with Jellyfish etc, is unrelated to conjugate techniques. Perhaps my recent post giving a "proof" for swordfish may help: http://www.sudoku.com/forums/viewtopic.php?p=13113#13113 I can certainly see why you may consider the pattern you've described above a swordfish, but I would argue it's not. Instead I'd leave it in the conjugate 'colors' group of techniques. Back to top Bob Hanson Joined: 05 Oct 2005 Posts: 187 : Location: St. Olaf College Items Posted: Thu Nov 03, 2005 1:33 pm    Post subject: I think the discussion on this thread is missing an important point. The "classical swordfish" is simply one of several (MANY) 3x3 patterns that fall into the "grid" category. What has been shown in rkral's message is NOT a swordfish. It is instead a circular chain Code:  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  A  .  | a  .  .  |  .  .  .  ---------+----------+---------  .  *  .  | .  .  b  |  .  .  .  .  *  .  | B  .  .  |  .  .  .  .  *  .  | .  .  .  |  .  .  .  ---------+----------+---------  .  c  .  | .  .  C  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  . I think I'm starting to understand this lettering system. What this marking system with AaBbCc does is record the "parity" of every other node in what are called "strong chains". So, for example, Aa here means, for example, that there are two 1's in that row, one where the A is and one where the a is. But it could equally mean that there is 12 in the A square and a 23 in the a square, connected by the common 2. So in that case we are "jumping chains" or doing "Y-cycles" in Glenn Fowler's parlance. If you do restrict this idea to one specific candidate value-- which I think you are doing here, along the lines of swordfish -- then you are missing many, many sorts of similar logical connections. But at the same time I would not recommend thinking of this as a swordfish. Technically what it is is two independent 2x2 grids amounting, in a sense, to something like two XY-wings working together. Code:  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  X  .  | X  .  .  |  .  .  .  ---------+----------+---------  .  *  .  | .  .  Y  |  .  .  .  .  *  .  | X  .  .  |  .  .  .  .  *  .  | .  .  .  |  .  .  .  ---------+----------+---------  .  Y  .  | .  .  Y  |  .  .  .  .  *  .  | *  .  *  |  .  .  .  .  *  .  | *  .  *  |  .  .  . My point is simply that if you identify the smaller 2x2 pattern, you can be just as successful. Or, if you are allowing B to be a different candidate value than A or C, then you are in the realm of Medusa chains, which aren't at all swordfish. See http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#grids _________________ Bob Hanson Professor of Chemistry St. Olaf College Northfield, MN http://www.stolaf.edu/people/hansonr Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         Sudoku Programmers Forum Index -> Solving sudoku All times are GMT Goto page 1, 2, 3  Next Page 1 of 3   Jump to: Select a forum Sudoku----------------Solving sudokuSetting sudokuProgramming sudokuThe mathematics of sudokuExotic sudoku Library----------------PuzzlesSoftwareSudoku elsewhere Not sudoku----------------Random thoughtsForum feedback  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   Powered by phpBB © 2001, 2005 phpBB Group Igloo Theme Version 1.0 :: Created By: Andrew Charron