FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in          Games  Calendar Log in to check your private messages    Why Unsolvable Goto page 1, 2, 3  Next          Sudoku Programmers Forum Index -> Solving sudoku View previous topic :: View next topic   Author Message Roger Joined: 28 Dec 2005 Posts: 1 : Items Posted: Wed Dec 28, 2005 7:14 pm    Post subject: Why Unsolvable Hi all I have read a lot of posts here and am very new to sudoku. I am writing a solver/player/creator for sudoku for compact.net frame work in Vb. I read someware here that the sudokus at this url http://www.smackedassintosh.net/sudoku/unsolvable_boards.html were unsolvable and someone was saying they could solve all except these. question Why are they classed as unsolvable is it because you have to force the result. (not using pure logic) My solver can solve (on pocket pc it take a while but they get there in the end.) pc can run the same program in the result is instant. ? I am just confused why there would be or is a problem in solving i have checked the results from my solver and they seam ok. Maybe someone could explain. Thanks in advance Roger Back to top eclark Joined: 28 Dec 2005 Posts: 70 : Items Posted: Thu Dec 29, 2005 12:46 am    Post subject: More than likely it has more then one valid solution then. Right now I have messed up my solved code base or I would test it. Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Thu Dec 29, 2005 1:13 am    Post subject: Roger wrote: I read someware here that the sudokus at this url http://www.smackedassintosh.net/sudoku/unsolvable_boards.html were unsolvable and someone was saying they could solve all except these. Hi Roger, welcome to the forum. Not unfamiliar with the .Net framework and VB myself, I may help you with specific issues, but I'm not familiar with the Compact.Net framework. The 3 posted puzzles on the site are NOT unsolvable. Maybe not by the person who put them there, but I checked them with my Sudo Cue solver, and all 3 have a unique solution. They just require very advanced solving techniques like tabling to break. The second puzzle, this one... Code: . 1 .|. 7 .|. . . . 2 6|. . .|. 5 7 5 . .|. . .|. . 3 -----+-----+----- . . 8|2 . .|. . . . 5 .|. . 4|3 . 2 4 . .|. 3 7|. 8 . -----+-----+----- . . .|. 5 3|4 . . . . 5|. . .|. . 8 . 8 .|. . .|. 9 6 ...seems to be the toughest one of the three. To be unsolvable, a puzzle should have a number of solutions not equal to 1. With 0 solutions, everybody agrees that the puzzle is not correct, but with > 1 solutions, some people claim they're valid Sudokus. I still loooooove this one: http://www.sudoku.org.uk/blunder.htm. Now there's a big unsolvable, carved in stone. Have fun writing your program, Ruud. _________________ Meet me at sudocue.net Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Thu Dec 29, 2005 3:29 pm    Post subject: Can someone please tell me why puzzle "Unsolvable #1" is ratted unsolvable, even by a "human solver"? I checked this puzzle and the only thing I needed to solve it was one loop. We can even go further way from the "end" grid posted in that url with basic steps. I have also checked puzzle #3 and find it even easier. Am I missing something? Or is there some error in the grids (wrong placed numbers)? Carcul Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Sun Jan 01, 2006 3:22 pm    Post subject: Tabling is not required Ruud wrote: They just require very advanced solving techniques like tabling to break. I have now also checked puzzle #2 and it also does not require tabling to be solved: I have reached the solution in 7 steps. Have someone also reached the solution without tabling? I would like to compare different ("human" executable) solutions. Carcul Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Sun Jan 01, 2006 6:39 pm    Post subject: Re: Tabling is not required Carcul wrote: Ruud wrote: They just require very advanced solving techniques like tabling to break. I have now also checked puzzle #2 and it also does not require tabling to be solved: I have reached the solution in 7 steps. Have someone also reached the solution without tabling?Carcul Carcul, I think there are many "human solvers" that don't use forcing chains, or forcing nets, or nice loops ... or anything else that involves chains ... except for pattern-based techniques like xy-wing. Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Sun Jan 01, 2006 6:40 pm    Post subject: Re: Tabling is not required [edit: duplicate deleted] Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Sun Jan 01, 2006 9:57 pm    Post subject: My human solver (which doesn't implement Colouring & full Tables), solves Puzzle 2.... It required Forcing Chains once & Nishio 3 times Back to top rkral Joined: 21 Oct 2005 Posts: 233 : Items Posted: Sun Jan 01, 2006 11:43 pm    Post subject: tarek wrote: My human solver (which doesn't implement Colouring & full Tables), solves Puzzle 2.... It required Forcing Chains once & Nishio 3 times I should not have written "human solvers" (especially with the quotes) as I meant solutions attempted by humans ... rather than computer programs that emulate human techniques of solving sudoku. Back to top Mark Joined: 19 Oct 2005 Posts: 30 : Location: Arizona Items Posted: Mon Jan 02, 2006 1:00 am    Post subject: Re: Tabling is not required Carcul wrote: Ruud wrote: They just require very advanced solving techniques like tabling to break. I have now also checked puzzle #2 and it also does not require tabling to be solved I'm glad you mentioned this, Carcul. I too have seen puzzles here recently that can be easily cracked by inference chains (a.k.a. cycles with conflicting endpoints, forcing chains, nice loops, etc.), yet several of the excellent solvers out there (e.g. Sudoku Susser, Sudo Cue) resort to tabling to handle them. Why is this? One developer wrote me with his opinion that inference chains are simply beyond the capabilities of human solvers. I don't share this opinion anymore. By first mastering XY-Wings, one is able to spot increasingly more complex inference chains. It made me feel good a while back when I was able to solve a puzzle by hand which took Sudoku Susser over 20000 tabling operations to complete! You have some excellent discussions of Nice Loops over on the Players Forum. Hopefully some of the programmers might visit them and realize that tabling isn't necessary in many, many cases. Cheers, Mark Back to top tarek Joined: 31 Dec 2005 Posts: 153 : Location: London, UK Items Posted: Mon Jan 02, 2006 10:33 am    Post subject: I would place Tabling before Nishio when I program it. If Puzzle 2 does not require Tabling (& Nishio), then it must be another technique that my solver still doesn't implement. It would be interesting to know how you made your solution Carcul. Was it colouring ? Back to top Ruud Site Admin Joined: 17 Sep 2005 Posts: 708 : Location: Netherlands Items Posted: Mon Jan 02, 2006 12:19 pm    Post subject: Carcul & Mark, Mark wrote: I too have seen puzzles here recently that can be easily cracked by inference chains (a.k.a. cycles with conflicting endpoints, forcing chains, nice loops, etc.), yet several of the excellent solvers out there (e.g. Sudoku Susser, Sudo Cue) resort to tabling to handle them. Why is this? I can only speak for myself, of course. Many new solving techniques have been in development lately. I've been trying to keep up-to-date with: - Almost Locked Sets (bennys) - BUGs - Nice loops Other promising techniques, like Constraint Subsets, do not seem to survive, while brand new techniques like Broken Wings still need to be fleshed out by the player community. Further more, I've been spending a lot of time at writing a solving manual, building an attractive website, improving my generator that creates the daily Sudokus that I place on my website, setting up a user forum, besides my daytime job and spending some quality time with the family these holidays. As a solver-programmer, my biggest concern is that the solver does solve all Sudokus and without errors. Having a "slash hammer" technique like tabling in the solving suite makes one lazy, I admit. It does scale down the priority for adding new solving techniques. If you think the Sudo Cue solver should be expanded with new solving techniques, or if you have other wishes for improvement of the program, from now on you can post these here at my user forum. I intend to take this wishlist very seriously. Best wishes, Ruud. _________________ Meet me at sudocue.net Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Mon Jan 02, 2006 2:48 pm    Post subject: Mark wrote: I'm glad you mentioned this, Carcul. I too (...).You have some excellent discussions of Nice Loops over on the Players Forum. Hopefully some of the programmers might visit them and realize that tabling isn't necessary in many, many cases. Thanks Mark. In the players forum, I have posted some wile ago a thread entitled "Nice Loops: some exercises", were I presented six puzzles that can be solved using only nice loops. Why dont you see it? If you like to use the bilocation/bivalue technique, I think you will enjoy it. Regards, Carcul Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Mon Jan 02, 2006 2:55 pm    Post subject: Tarek wrote: It would be interesting to know how you made your solution Carcul. Was it colouring ? Hi Tarek. I have used simple nice loops and advanced nice loops in my solution. In fact, I have discovered in puzzle #2 a loop that allows 10 candidates to be eliminated from seven cells: I am saying this because I have never before eliminated so many candidates with the same logical argument. If you are interested in those loops, please consult the players forum, where you can find a lot of information about them. Regards, Carcul Back to top Carcul Joined: 29 Dec 2005 Posts: 50 : Location: Coimbra, Portugal Items Posted: Mon Jan 02, 2006 3:02 pm    Post subject: Hi Ruud. Hi have already take a "look" at your forum: it is very nice, congratulations. Hi have just a small request for you, if you allowd me to do so: I wonder if you could post in this forum the two most difficult puzzles that your Sudo Cue program can generate? Thanks in advance. Regards, Carcul 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