FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Looking for example of franken X-wing          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message MCondron Joined: 17 Jul 2006 Posts: 35 : Location: Houston, TX Items Posted: Mon Dec 11, 2006 3:53 am    Post subject: Looking for example of franken X-wing Does anyone have a specific example of a puzzle requiring a "franken X-wing"? I've been poking away at a solver program for a few months and recently added this method. I would like to test it, but I can't find any examples of a puzzle that requires it. I've seen plenty of "skeleton" examples of the structure of this configuration, but an actual puzzle requiring it would be very nice. Thanks. BTW -- if my solver is working correctly (TBD) I've generated about 1.01 million puzzles and found exactly zero franken X-wings randomly. So I'm 63% sure it's a one in a million phenomenon and 99.999+% sure it's 1 in 100,000 -- assuming, again, that my code for finding these things is working. Back to top daj95376 Joined: 05 Feb 2006 Posts: 349 : Items Posted: Mon Dec 11, 2006 7:21 am    Post subject: The Sudoku Players' Forum has a lot of discussion and examples of fish. Look here: http://www.sudoku.com/forums/ Back to top Pat Joined: 06 Sep 2006 Posts: 128 : Items Posted: Mon Dec 11, 2006 2:21 pm    Post subject: re: Franken X-wing MCondron wrote: Does anyone have a specific example of a puzzle requiring a Franken X-wing? as far as i can tell, a finless Franken X-wing ( in the sense that the "base" or the "cover" does use a mixture of Box + Line - for example, rb\cc ) is never needed - the same exclusions could be obtained by box-to-line and/or line-to-box! or for box-sizes other than 3x3 - the same exclusions could be obtained by a simpler X-wing, namely: Boxes-to-Lines and/or Lines-to-Boxes (without any mixture) Back to top MCondron Joined: 17 Jul 2006 Posts: 35 : Location: Houston, TX Items Posted: Mon Dec 11, 2006 9:21 pm    Post subject: Thanks, DAJ; I've looked around quite a lot and have found excellent examples of the structure of this configuration, but not an actual puzzle that includes one. I'm looking for something like what is on Ruud's benchmark list, which is a great list but does not include an example of this particular configuration. Back to top MCondron Joined: 17 Jul 2006 Posts: 35 : Location: Houston, TX Items Posted: Mon Dec 11, 2006 10:24 pm    Post subject: Pat, I appreciate your reply, but I'm not sure I follow what you wrote. It seems to me, if I understand the definition of the franken x-wing correctly, that it requires that the candidate value in question must occur exactly once in each of the four sets where the lines intersect the box: Code: I1 I1 I1 | A  A  A |I2 I2 I2 B  B  B  | .  .  . |B  B  B  I3 I3 I3 | A  A  A |I4 I4 I4 ----------------------------- .  .  .  | .  .  . | .  .  .  .  .  .  | .  .  . | .  .  .  .  .  .  | .  .  . | .  .  .  ----------------------------- .  .  .  | .  .  . | .  .  .  .  .  .  | .  .  . | .  .  .  .  .  .  | .  .  . | .  .  .  So, here, for example, rows 1 and 3, along with boxes 1 and 3, make the franken x-wing. The four "I"s indicate each of the four areas in the intersection of the rows and boxes; "A" designates the cells in the rows which are not in the set I (I = I1+I2+I3+I4), and "B" designates the cells in the boxes which are not in I. If I understand this right, the pattern works by saying that if a candidate value -- say 9 here for concreteness -- occurs exactly once in each of the four I subsets, and does not occur in any of the A cells, then you can eliminate 9 from the B cells (or vice versa with respect to the roles of A and B). Of course, this can degenerate into simpler configurations: if the candidates in I1 and I3 are in the same column and the candidates in I2 and I4 are also in the same column, then you have a conventional X-wing. I have read definitions of the franken configuration which do not distinguish the four subsets in the set I've designated "I" here and do not impose the restriction that each of these four subsets contain the candidate value exactly once. In that case, I can see that if, say, all three I1 cells have a 9, and nothing else in that box does, then certainly 9 can be removed from row 1 in the standard line-box fashion. I have assumed when I've read that kind of definition that what was meant was the way I've interpreted it as I just described -- exactly one occurrence of the candidate digit in each of these four I's (and also of course not all lining up like a regular X-wing). In this case, I don't see how a line-box interaction can happen since each box has candidates in two lines. I may not have this definition right, and I may be completely missing something...please correct me if I'm wrong. Thanks, Mike. Back to top Jean-Christophe Joined: 19 Mar 2006 Posts: 126 : Location: Belgium Items Posted: Tue Dec 12, 2006 11:25 am    Post subject: MCondron wrote: I don't see how a line-box interaction can happen since each box has candidates in two lines. As already stated, simple line/box (or box/line) interactions will indeed do the same. Taking your example, this gives First Case : If none of the B have the candidate, then all candidates for row 2 are locked within R2C456 all in block 2, therefore they can't go in A Second case, the other way : If none of the A have the candidate, then all candidates for block 2 are locked within R2C456 all in row 2, therefore they can't go in B If you want to implement some really useful X wings, consider Finned X-Wing (sashimi or not). An even more generalized version is Grouped Turbot Fish. _________________ Jean-Christophe "When you have eliminated the impossible, whatever remains, however improbable, must be the truth." Sherlock Holmes. Back to top MCondron Joined: 17 Jul 2006 Posts: 35 : Location: Houston, TX Items Posted: Tue Dec 12, 2006 3:42 pm    Post subject: Thanks, Jean-Cristophe, for taking the time to explain this very clearly and in detail. Of course, now this makes perfect sense; I should have seen this earlier! This explains why I cannot find any -- my solver would categorize any generated puzzle with this configuration as a line-box and move on. I am indeed working on other related patterns...more to come. Back to top Pat Joined: 06 Sep 2006 Posts: 128 : Items Posted: Wed Dec 13, 2006 11:15 am    Post subject: re(2): Franken X-wing re(2): (finless) Franken X-wing Pat wrote: as far as i can tell, a finless Franken X-wing ( in the sense that the "base" or the "cover" does use a mixture of Box + Line - for example, rb\cc ) is never needed - the same exclusions could be obtained by box-to-line and/or line-to-box! hi MCondron, i see your example uses 2 Boxes and 2 Rows, which may be considered a Franken X-wing but is certainly a very simple case: bb\rr (Boxes-to-Lines) or rr\bb (Lines-to-Boxes); whereas i was looking at a more complex case involving a mixture of Box + Line, such as rb\cc: Code:  ...  X/X  ...  ...  X/X  ...  ...  X/X  ...  ...  *.*  ...  ///  X/X  ///  ...  *.*  ...  ...  *.*  ...  ...  *.*  ...  ...  *.*  ... r5 + box2 can only have the digit in c4,c6 - exclude the digit elsewhere in those columns which merely excludes in one step what would otherwise take two steps - line-to-box: r5 to box5 line-to-box: c5 to box8 try a (finless) Franken Swordfish? ~ Pat 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 Page 1 of 1   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