FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Understanding Swordfish Goto page Previous  1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message AndyT Joined: 27 Jan 2006 Posts: 15 : Location: Hong Kong Items Posted: Tue Jan 31, 2006 9:12 am    Post subject: No, it didn't - here's your version: Which to my simple Engineering trained mind tells me that there is another key to this logic. That you can say this strongly suggests that there another key to the construct. Why is my colouring wrong? Why is it that Ruud says you can't use Colours and you say you can? Ta! Back to top angusj Site Admin Joined: 18 Jun 2005 Posts: 406 : Items Posted: Tue Jan 31, 2006 9:17 am    Post subject: AndyT wrote: No, it didn't - here's your version: Phew! The highlighted cell (r3c4) is a 'buddy' with both a bright green and a blue cell. So, because either the bright green or the blue cell must be 'true' the highlighted cell can't be. Back to top AndyT Joined: 27 Jan 2006 Posts: 15 : Location: Hong Kong Items Posted: Tue Jan 31, 2006 9:35 am    Post subject: I give in! Back to top Brian Less Joined: 24 Jul 2005 Posts: 7 : Items Posted: Thu Feb 09, 2006 3:28 pm    Post subject: AndyT wrote: I give in! Andy, Don't give up just yet! First of all, to make things clearer for yourself, you could sort your filtering options out better! Go to Options and make sure 'Show Candidates' is ticked (you have anyway). You also seem to have the 'Show ALL candidates while filtering' option ticked. If you UNTICK that option, that alone will make your task a LOT easier to see what's going on above in your example(s)! Having done that, it's now a matter of logic to work out why SS has selected R3C4 as the cell to remove the candidate 9 from. Let's go back to bare bone basics. In each column, row, and 'box' there must be ONE of each number from 1-9. OK. The program has reached the state above where due to eliminations by other logical processes, there are only the possible candidates remaining. E.g. in Row 1, the only POSSIBLE candidates are 1, 2, 7 and 9. More specifically, at R1C5 only 7 and 9 are POSSIBLE candidates dues to the 1 and 2 in that column. Do you understand WHY these are the only possible candidates first off? Assuming you do, then for visibility sake, we filter on 9's only and then we make some more logical conclusions. Again take row 1 as an example with filtering on 9's switched on. There are only two possible cells that 9 could occupy in row 1, i.e. column 5 or column 7. We don't know which, but one of them absolutely MUST be a 9 in order to satisfy the fundamental rule of Sudoku and also given that there are only 2 columns in that row that are possibilities. We can make the same assertion we made about Row 1 with the candidate 9's: R1C7 / R2C9 and R2C9 / R2C1 etc. etc. These form a 'conjugate chain' of trues / falses coloured blue / green for convenience. We don't know WHICH is true and WHICH is false but we definitely know that ONE of the group of colours MUST be! We eventually arrive at the situation in your image above. How do we know that R3C4 CANNOT be a candidate 9? Let's assume that the GREEN coloured group is the TRUE one so we place a 9 in R1C5, R2C9, R3C3 etc. With a 9 at R1C5 there absolutely cannot be a 9 in R3C4 also otherwise there would be TWO 9's in that box! Let's say instead that the BLUE coloured group is the TRUE one, so we place a 9 in R1C7, R2C1 etc. However, with a 9 at R7C4 there absolutely cannot be a 9 at R3C4 as there would be two 9's in column 4! The logical conclusion therefore is that R3C4 CAN NOT be a possible candidate 9 and we thus eliminate it 9 as a candidate from that cell. Does that make it easier to understand? Last edited by Brian Less on Thu Feb 09, 2006 4:28 pm; edited 1 time in total Back to top AndyT Joined: 27 Jan 2006 Posts: 15 : Location: Hong Kong Items Posted: Thu Feb 09, 2006 3:49 pm    Post subject: Thanks, Brian Yes, I understand the logic of Sudoku and, as an amateur maybe, even think I'm quite reasonable but Colours - pah? What I don't see is the sequence used to build the chain. R3C4 and R3C5 are not blue. If R1C5 is green then its buddy at R3C5 is equally wrong yet the program does not volunteer to remove that 9. I've tried this on a number of puzzles and it "appears" path dependant. I prefer a pencil and paper to the machine. Got 10+ hours on a plane to Auckland tomorrow so open to tips! Andy Back to top Brian Less Joined: 24 Jul 2005 Posts: 7 : Items Posted: Thu Feb 09, 2006 4:13 pm    Post subject: AndyT wrote: Thanks, Brian Yes, I understand the logic of Sudoku and, as an amateur maybe, even think I'm quite reasonable but Colours - pah? What I don't see is the sequence used to build the chain. R3C4 and R3C5 are not blue. If R1C5 is green then its buddy at R3C5 is equally wrong yet the program does not volunteer to remove that 9. I've tried this on a number of puzzles and it "appears" path dependant. I prefer a pencil and paper to the machine. Got 10+ hours on a plane to Auckland tomorrow so open to tips! Andy Hi Andy, It doesn't matter where you start the sequence here. Try it. Start at ANY cell which the program has coloured blue or green and form a conjugate chain from it and you will find that you end up with the same pattern as above. You can only form conjugates if there are exclusively 2 candidates. Yes, R3C5 is a 'buddy' of R1C5 but it's not also a 'buddy' of any blue candidate 9 cells so we can't infer much yet until: If you eliminate R3C4 as a candidate, then we can colour R9C4 green as a conjugate of R7C4, AND you can also colour R3C5 blue as a conjugate of R3C3. This will then enable you to eliminate R9C5 as a candidate (by the use of colouring (logic))! P.S. You can eliminate R4C8 as a candidate 9 by the same process of logic as above. What you end up with is a complete conjugate chain of candidate 9's. Unfortunately, logic then is of no further help to you as you can't say which group - blue or green - is the 'true' one. The program doesn't present you with that - or the previous - solving step because the elimination of R3C4's candidate 9, leaves a naked 5 in that cell putting the colouring process on a 'back burner'. Back to top RVer1 Joined: 08 Feb 2006 Posts: 2 : Items Posted: Fri Feb 10, 2006 9:30 pm    Post subject: Understanding Swordfish I, too, am having problems with understanding swordfish patterns. Here is a screen shot of a problem that I was working. Is this a valid swordfish pattern? If this is a valid pattern based on columns then the candidates in yellow should be able to be excluded. Also if the pattern is based on rows then the candidates in yellow should be able to be removed. Show me where I am missing the logic for this method. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Fri Feb 10, 2006 10:25 pm    Post subject: That is not a swordfish pattern. For a Swordfish pattern in rows, you need 3 rows with candidates for a selected digit in exactly 3 columns. For a Swordfish pattern in columns, you need 3 rows with candidates for a selected digit in exactly 3 rows. Your pattern does not qualify, because there are extra candidates in additional rows and in additional columns. Those are the very same candidates that you are pointing out in your post. Ruud. _________________ Meet me at sudocue.net Back to top vidarino Joined: 10 Feb 2006 Posts: 38 : Location: Haugesund, Norway Items Posted: Fri Feb 10, 2006 10:25 pm    Post subject: I'm afraid there isn't a Swordfish in the above grid at all. Close, though. You only have a Swordfish if the three pairs (either in rows or in columns) are alone in their particular row or column. And if so, it will eliminate other candidates in the affected columns or rows, respectively. To demonstrate; If there hadn't been a 4 in R7C9, you would have a Swordfish in columns 3, 7 and 9. And then you would have been able to eliminate the rest of the 4s in the rows 3, 4 and 6, in this case R3C4, R4C1 and R6C1. Back to top RVer1 Joined: 08 Feb 2006 Posts: 2 : Items Posted: Fri Feb 10, 2006 11:07 pm    Post subject: vidarino wrote: I'm afraid there isn't a Swordfish in the above grid at all. Close, though. You only have a Swordfish if the three pairs (either in rows or in columns) are alone in their particular row or column. And if so, it will eliminate other candidates in the affected columns or rows, respectively. To demonstrate; If there hadn't been a 4 in R7C9, you would have a Swordfish in columns 3, 7 and 9. And then you would have been able to eliminate the rest of the 4s in the rows 3, 4 and 6, in this case R3C4, R4C1 and R6C1. Thank you, So for columns, you can not have other candidates in the columns that make up the swordfish pattern, for rows, you cannot have extra candidates in the rows that make up the pattern. Finally some light. I'll give it a try to see where it goes. Back to top Miles Joined: 29 Dec 2005 Posts: 30 : Items Posted: Sat Feb 11, 2006 10:20 pm    Post subject: Ruud wrote: That is not a swordfish pattern. For a Swordfish pattern in rows, you need 3 rows with candidates for a selected digit in exactly 3 columns. For a Swordfish pattern in columns, you need 3 rows with candidates for a selected digit in exactly 3 rows. Your pattern does not qualify, because there are extra candidates in additional rows and in additional columns. Those are the very same candidates that you are pointing out in your post. Ruud. Depending on the definition, you can replace exactly by at most. One question, for a pattern in rows, for instance, the columns must be in different boxes, no ? Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Sun Feb 12, 2006 1:16 am    Post subject: Miles wrote: Depending on the definition, you can replace exactly by at most Each row involved can have candidates in 2 or 3 columns, but it is essential that the 3 rows together have candidates in exactly 3 columns, because when there are less, you have a serious problem completing the sudoku. Quote: One question, for a pattern in rows, for instance, the columns must be in different boxes, no ? A swordfish requires candidates in at least 3 different boxes, no matter whether it originates from rows or columns. With candidates in less boxes, line-box reductions (locked candidates) would probably occur before you could spot a swordfish pattern. Ruud. _________________ Meet me at sudocue.net Back to top AndyT Joined: 27 Jan 2006 Posts: 15 : Location: Hong Kong Items Posted: Sun Feb 12, 2006 10:01 am    Post subject: I know I started this a Swordfish but then I mixed the Colours, so to speak. Allow me to revert to colours again - you there Brian. This is the hint from Angus' prog: Please, somebody explain how - given we are on 8s here - I can ignore nearly every 8 on the board and pick just those few and thus conclude that R7C7 is not an 8? There has to be another something else going on here. Help, please! Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Sun Feb 12, 2006 11:40 am    Post subject: This is a nice example of multi-coloring. There are only 2 candidates left in row 1, one of them has to be true. There are only 2 candidates left in box 8, one of them has to be true. The blue and purple candidates are in the same column. One of them has to be false. Because either the blue or the purple candidate (or both) has to be false, the implication is that either the orange or the green candidate (or both) has to be true. The candidate R7C7 is either eliminated by the orange or by the green candidate, so it is eliminated under all circumstances. Let it go! Ruud. _________________ Meet me at sudocue.net Back to top Brian Less Joined: 24 Jul 2005 Posts: 7 : Items Posted: Sun Feb 12, 2006 12:20 pm    Post subject: Further to what Ruud said. To explain WHY the program or indeed why YOU would pick those particular conjugates, is that these are the only ones that offer us a possibility to invoke what Angus calls the Type 2 example of multicolouring. This is explained here: http://www.setbb.com/phpbb/viewtopic.php?p=2575&mforum=sudoku#2575 There are only 4 separate sets of conjugates in the example you posted. The ones coloured by the program are the only ones that SHARE a group. In this case it is column 5. Although you could multicolour the other conjugates, in this particular case it would not help you any further. 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 Previous  1, 2, 3  Next Page 2 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