
View previous topic :: View next topic 
Author 
Message 
 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Fri Oct 28, 2005 8:22 pm Post subject: How to find more sudoku logic 


I was thinking
"How do we know if all sudoku logic is known?"
And came to the following idea:
Make an NON uniqe puzzle.
(a puzzle with only 16 clues for example)
that has at least one solution.
Try to solve it by logic. (excluding uniqueness tests)
This will result in a incomplete solution.
in other words: Some squares will have more than one remaining candidate
Test with T&E if you can make a solution for every remaining candidate in every square.
(solve the puzzle a couple of times and look if there are solutions that have that candidate in that square)
If there is a candidate that does not result in a possible solution there is still more logic possible. 

Back to top 


 Ruud Site Admin
 Joined: 17 Sep 2005  Posts: 708  :  Location: Netherlands  Items 

Posted: Fri Oct 28, 2005 9:02 pm Post subject: 


Wouldn't it be easier to generate a single solution puzzle with a backtracker, and see whether it can be solved with all the logic you have at your disposal? Then you can also include uniqueness tests, which belong to the 'logical' methods.
In dukuso's Top95, there are about 30 that cannot be solved by "user friendly" logic. Maybe some of them can be solved by supercoloring, tabling, Bowman's Bingo, bifurcating chains or other (complex) methods that I haven't implemented yet, but many of these methods are not easy to use without computer backing.
Besides, the line between 'logic' and 'brute force' is not even clear amongst the forum members. When I try every candidate, and dismiss it if it causes errors, I'm not using logic. However, when I make a selection on clearly defined criteria, then check the effects of candidates being true, and dismiss them when they cause 'inconsistencies', then I have used a 'logical' method.
As long as we have single solution grids that cannot yet be solved by pure logic, we can use those to figure out better methods.
Ruud. 

Back to top 


 soduko
 Joined: 10 Oct 2005  Posts: 50  :   Items 

Posted: Fri Oct 28, 2005 10:30 pm Post subject: 


Ruud wrote:  Wouldn't it be easier to generate a single solution puzzle with a backtracker, and see whether it can be solved with all the logic you have at your disposal? Then you can also include uniqueness tests, which belong to the 'logical' methods.. 
No the trick is that the puzzle needs more than one solution so there are unsolved squares (squares with more than one candidate)
and then you can tests if there are solutions with every remaining candidate.
This comes with a pricetag, you cannot use uniqueness tests.
Ruud wrote: 
Besides, the line between 'logic' and 'brute force' is not even clear amongst the forum members. When I try every candidate, and dismiss it if it causes errors, I'm not using logic. However, when I make a selection on clearly defined criteria, then check the effects of candidates being true, and dismiss them when they cause 'inconsistencies', then I have used a 'logical' method.
As long as we have single solution grids that cannot yet be solved by pure logic, we can use those to figure out better methods.

Maybe a (to simplistic) destinction between brute force and logic
Brute force will find a solution even if there is more than one.
Logic will not find a solution if there is more than one.
(in the case of less than two solutions you cannot use this distinction) 

Back to top 




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
