FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Not resorting to brute force...:)          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message gaby Joined: 02 Jul 2005 Posts: 120 : Items Posted: Tue Jul 19, 2005 10:10 pm    Post subject: Not resorting to brute force...:) Here's a sudoku that I'm trying to solve using logic only, and my PHP based solver. It's the only one that I can't break without using brute force: Code: -2------- ---6----3 -74-8---- -----3--2 -8--4--1- 6--5----- ----1-78- 5----9--- -------4- Here is as far as I get using logic alone: Code: -26--7--8 89562--73 -74-8---- 457193862 983246517 612578--4 2-9-1-78- 5487-9--- 7-18-2-4- What's the next move? Brute forcing a value into [1,1] of either 1 or 3 either solves the puzzle immediately or breaks the puzzle. Am I missing a logical step? What's the next form of analysis to try on this? Gaby[/code] _________________ Free daily sudoku - Online puzzle database http://vanhegan.net/sudoku/ Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Tue Jul 19, 2005 10:31 pm    Post subject: Re: Not resorting to brute force...:) Look for an xy-wing starting from (1,5). Back to top gaby Joined: 02 Jul 2005 Posts: 120 : Items Posted: Wed Jul 20, 2005 11:18 am    Post subject: I think I understand XY-wings, and have yet to read up properly on forcing chains, but I can see how it works. However, looking at my candidate grid, I can't see the XY you suggest. My candidate grid looks like this: Code: { 13 }{ 2  }{ 6  }|{349 }{ 35 }{ 7  }|{149 }{ 59 }{ 8  } { 8  }( 9  }{ 5  }|{ 6  }{ 2  }{ 14 }|{ 14 }{ 7  }{ 3  } { 13 }{ 7  }{ 4  }|{ 39 }{ 8  }{ 15 }|{1269}{259 }{169 } ------------------|------------------|------------------ { 4  }{ 5  }{ 7  }|{ 1  }{ 9  }{ 3  }|{ 8  }{ 6  }{ 2  } { 9  }{ 8  }{ 3  }|{ 2  }{ 4  }{ 6  }|{ 5  }{ 1  }{ 7  } { 6  }{ 1  }{ 2  }|{ 5  }{ 7  }{ 8  }|{ 39 }{ 39 }{ 4  } ------------------|------------------|------------------ { 2  }{ 36 }{ 9  }|{ 34 }{ 1  }{ 45 }|{ 7  }{ 8  }{ 56 } { 5  }{ 4  }{ 8  }|{ 7  }{ 36 }{ 9  }|{1236}{ 23 }{ 16 } { 7  }{ 36 }{ 1  }|{ 8  }{356 }{ 2  }|{369 }{ 4  }{569 } Is the XY-wing a hidden one or is it visible? Gaby _________________ Free daily sudoku - Online puzzle database http://vanhegan.net/sudoku/ Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 20, 2005 11:51 am    Post subject: gaby wrote: Is the XY-wing a hidden one or is it visible? It's right there, though it has a "flat" shape. If (1,5) is 3, then (3,4) is 9, then (1,4) is not 9. If (1,5) is 5, then (1,8) is 9, then (1,4) is not 9. So remove 9 from the candidates for (1,4). It's easy from there. Back to top gaby Joined: 02 Jul 2005 Posts: 120 : Items Posted: Wed Jul 20, 2005 1:16 pm    Post subject: I see, I see... I was looking for the xy component. I had the 12 part, but couldn't find a matching 1x, 1y and xy part from the starting point you suggested. It transpires that the xy not necessary after all in this case. It also took me a little while to work out that when you're talking (a,b) you mean row a column b, rather than my [a,b] which would mean column a row b (standard X,Y coordinate system, starting top left). That fooled me for a while. I think I need to read up on forcing chains, see if I can get a more general solution together for it. Gaby _________________ Free daily sudoku - Online puzzle database http://vanhegan.net/sudoku/ Back to top Nick70 Joined: 08 Jun 2005 Posts: 160 : Items Posted: Wed Jul 20, 2005 3:32 pm    Post subject: gaby wrote: I see, I see... I was looking for the xy component. I had the 12 part, but couldn't find a matching 1x, 1y and xy part from the starting point you suggested. It transpires that the xy not necessary after all in this case. Yes, the original example in the other thread is a bit too restrictive. And I stuck to the "xy-wing" name but if I were to choose one, "y-wing" might probably be more appropriate, because the pattern is really made of only three cells, like the x-wing is made of four. You have a XY cell where you start from. That cell is connected to two other cells XZ and YZ. Then you can remove Z from all intersections of units that contain XZ and YZ (like in x-wing you remove a number from other cells in the same rows/colums as the 4 x-wing cells). Often times the xy-wing imediately allows you to place a big number, but this isn't necessarily the case, just like x-wing doesn't always immediately allow you to place a big number. 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