| View previous topic :: View next topic |
| Author |
Message |
| mike_bike_kite
| | Joined: 13 Oct 2008 | | Posts: 7 | | : | | Location: London |
Items |
|
 Posted: Mon Oct 13, 2008 2:34 pm Post subject: Solving the last 1% of problems |
 |
|
I have my little pet sudoku solver and it will solve anything a normal human can but there are a number of very, very difficult problems that it can't solve and I have no clue how to approach them. Is there some standard technique I can use to solve them?
Typical problems that are causing issues me are:
| Code: | +---+---+---+
|...|...|...|
|...|3.1|...|
|...|7.5|...|
+---+---+---+
|.57|...|34.|
|...|...|...|
|.32|...|17.|
+---+---+---+
|...|1.7|...|
|...|9.2|...|
|...|...|...|
+---+---+---+
+---+---+---+
|1..|...|..2|
|.2.|...|.6.|
|..3|4..|5..|
+---+---+---+
|...|8.5|...|
|..8|.3.|9..|
|...|9.4|...|
+---+---+---+
|..5|..3|4..|
|.7.|...|.1.|
|6..|...|..7|
+---+---+---+
+---+---+---+
|...|76.|...|
|...|4..|.71|
|8..|...|...|
+---+---+---+
|...|...|...|
|..7|...|9..|
|6..|3..|12.|
+---+---+---+
|.7.|...|.4.|
|...|..6|...|
|...|97.|...|
+---+---+---+
|
Any suggestions for how to approach these types of issues. I currently use techniques such as X-Wings, alternating colours with forced chains as a last resort but none of these are helping. I'd like to avoid using brute force if I can as the aim was to have an "intelligent" solver.
Mike Robinson |
|
| Back to top |
|
 |
| daj95376
| | Joined: 05 Feb 2006 | | Posts: 349 | | : | |
Items |
|
| Posted: Mon Oct 13, 2008 3:42 pm Post subject: |
|
|
| Your first puzzle has multiple solutions. Your third puzzle has zero solutions. Neither puzzle qualifies as a valid Sudoku puzzle. Your second puzzle requires complex, and probably recursive, steps to solve it. As far as I'm concerned, it needs a backtrack based solver instead of a logic based solver. |
|
| Back to top |
|
|
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Mon Oct 13, 2008 4:40 pm Post subject: |
|
|
| daj95376 wrote: | | Your first puzzle has multiple solutions. Your third puzzle has zero solutions. Neither puzzle qualifies as a valid Sudoku puzzle. Your second puzzle requires complex, and probably recursive, steps to solve it. As far as I'm concerned, it needs a backtrack based solver instead of a logic based solver. |
I can confirm that.
The first one has only 16 clues, this far no valid 16-clue sudoku was generated, you must have at least 17 clues.
The second one has this solution:
| Code: | 157 396 842
429 758 163
863 412 579
791 865 234
248 137 956
536 924 781
915 673 428
374 289 615
682 541 397 |
The third one has 17 clues, but indeed has no solution.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| mike_bike_kite
| | Joined: 13 Oct 2008 | | Posts: 7 | | : | | Location: London |
Items |
|
| Posted: Mon Oct 13, 2008 5:56 pm Post subject: |
|
|
| Quote: | | Your first puzzle has multiple solutions. Your third puzzle has zero solutions. Neither puzzle qualifies as a valid Sudoku puzzle. Your second puzzle requires complex, and probably recursive, steps to solve it. As far as I'm concerned, it needs a backtrack based solver instead of a logic based solver. |
Thanks guys for the prompt responses. I have been copying and pasting a lot of problems from the net into the program and just seeing which ones it couldn't solve. Problem is the program is much better (and faster) than I am at solving these things so when it said it couldn't do it I had no clue how to proceed. So your feedback is actually very good news to me ! 
| Quote: | | Your second puzzle requires complex, and probably recursive, steps to solve it. As far as I'm concerned, it needs a backtrack based solver instead of a logic based solver. |
Was there some special technique reuired to solve the second one? One odd thing I found about a lot of the published techniques is that they seem to overlap ie X-Wings and alternate colours seem to trap pretty much the same things.
Is there a graded set of problems (in a text based form) for checking programs? that might at least tell me when to stop programming the thing.
Mike |
|
| Back to top |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Mon Oct 13, 2008 8:36 pm Post subject: |
|
|
Sudoku Explainer rated the second puzzle 10.6/10.6 /10.4
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| mike_bike_kite
| | Joined: 13 Oct 2008 | | Posts: 7 | | : | | Location: London |
Items |
|
| Posted: Mon Oct 13, 2008 8:54 pm Post subject: |
|
|
That's Greek to me I'm afraid - I assume that means it's quite tough. Are there any human techniques that can be used to solve it or is it something only a computer could figure out? I'm only really interested in solving the puzzles in a human like fashion but I would like to cover as much as possible.
Mike |
|
| Back to top |
|
|
| Lunatic
| | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
| Posted: Mon Oct 13, 2008 9:15 pm Post subject: |
|
|
| mike_bike_kite wrote: | | I assume that means it's quite tough. |
Indeed. The first solving step to take, according to Sudoku Explainer, is the following:
Dynamic Contradiction Forcing Chains
With this solving technique, it can be proved the two following assertions:
If R3C5 contains the value 7, then R6C5 must contain the value 2
If R3C5 contains the value 7, then R6C5 cannot contain the value 2
Because the same assumption yields to contradictory results, we can conclude that the assumption is false, that is, R3C5 cannot contain the value 7.
Each assertion is proved by a different chain of simple rules. The chains can be dynamic, which means that the conclusions of multiple sub-chains must be combined in some cases.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
|
| garthd
| | Joined: 29 Apr 2006 | | Posts: 32 | | : | |
Items |
|
| Posted: Tue Oct 14, 2008 1:10 am Post subject: |
|
|
| Quote: | | Solving the last 1% of problems |
Hi Mike. By the title of your post, I'd say that you may be searching for the holy grail of sudoku programming - a way to solve any puzzle using logic based techniques. As far as I know, despite the vast range of techniques that have been developed, there are many puzzles which presently can be advanced, but not completely solved, using logic.
As any example, try Andrew Stuart's online solver (www.scanraid.com/sudoku.htm) or Ruud's SudoCue program (www.sudocue.net) and use the top1465 puzzle file ([url]magictour.free.fr/top1465[/url]) to see some of the advanced techniques in action. However, this should show you that even some of the most advanced solvers are not capable of logically solving some really hard puzzles.
| Quote: | | Is there a graded set of problems (in a text based form) for checking programs? that might at least tell me when to stop programming the thing. |
There is definitely overlap between techniques, and a declining rate of return. E.g. the more complex and esoteric techniques that you can code will generally only lead to incremental improvements in the number of very hard puzzles that you can solve (without having to resort to backtracking/brute force). This comes down to the fact that the more complex techniques rely on fairly rare patterns of candidates, which obviously are then only found in relatively few puzzles. There is obviously a genuine challenge in attempting to program as many known techniques as possible, but exactly when to stop implementning solving techniques probably comes down to how much time you have, how proficient a programmer you are, and your overall level of enthusiasm for sudoku and/or programming.
| Quote: | | I'm only really interested in solving the puzzles in a human like fashion but I would like to cover as much as possible. |
It's also somewhat difficult to draw the line as to what techniques are 'human like' as this relies on some kind of judgement as to what techniques a person knows, and how good they are at applying them. But I'd say that techniques like complex colouring, loops and chains etc start to move out of the realm of human style solving (that is, the complexity of these techniques and the number of steps/calculatoins required starts to make these impractical for many human solvers to attempt - but obviously not impossible). But strictly speaking, any logic based technique that can be used in a computer program could also be employed by a human. |
|
| Back to top |
|
|
| mike_bike_kite
| | Joined: 13 Oct 2008 | | Posts: 7 | | : | | Location: London |
Items |
|
| Posted: Tue Oct 14, 2008 1:58 pm Post subject: |
|
|
| Lunatic wrote: | | Dynamic Contradiction Forcing Chains ... Each assertion is proved by a different chain of simple rules. The chains can be dynamic, which means that the conclusions of multiple sub-chains must be combined in some cases. |
I already handle these conditions but I have limits on how far the search can go (PHP is interpreted and running on my small server). I tried turning off the limits and running the puzzle again by hand to see how complex the chain would be ... it turned out to be almost 60 moves long and involved more forced chains on route ... this means I simply can't do this using my existing program. I was hoping there might be some neat tricks to avoid such complexities.
Would a human do this? could a human solve this puzzle? Seeing as I'm trying to solve the puzzles logically then I might be happy accepting that these can't be done. |
|
| Back to top |
|
|
| mike_bike_kite
| | Joined: 13 Oct 2008 | | Posts: 7 | | : | | Location: London |
Items |
|
| Posted: Tue Oct 14, 2008 2:13 pm Post subject: |
|
|
| garthd wrote: | | use the top1465 puzzle file ... to see some of the advanced techniques in action |
Oh dear, it appears my program didn't do very well on most of these  I'm hoping that they all require the sort of "brute force logic" that I'm aiming to avoid. If so then I don't mind too much. If not then I'll have to rename this thread to "Solving the last 50% of problems"
| garthd wrote: | | There is obviously a genuine challenge in attempting to program as many known techniques as possible, but exactly when to stop implementning solving techniques probably comes down to how much time you have, how proficient a programmer you are, and your overall level of enthusiasm for sudoku and/or programming. |
I've spent a month already on this damn program and definitely feel I'm hitting the diminishing returns stage. I'll perhaps put a link in the "programs" section and hopefully you guys can offer a few suggestions.
EDIT : I've put the URL into the software section in just here http://www.setbb.com/sudoku/viewtopic.php?p=10358&mforum=sudoku#10358 |
|
| Back to top |
|
|
| garthd
| | Joined: 29 Apr 2006 | | Posts: 32 | | : | |
Items |
|
| Posted: Wed Oct 15, 2008 5:23 am Post subject: |
|
|
| Quote: | | Oh dear, it appears my program didn't do very well on most of these I'm hoping that they all require the sort of "brute force logic" that I'm aiming to avoid. |
I should have mentioned that the top1465 is often used as a torture test for brute force / backtracking...[/quote] |
|
| Back to top |
|
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
