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: |
|
|
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 |
|
|
|