Bram Cohen ([info]bramcohen) wrote,
@ 2005-12-11 00:02:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
More Sudoku
There's one fairly general technique which I missed from my list of Sudoku-solving techniques. Since a problem composed entirely of 2-clauses (that's statements of the form 'a or b') can be solved in linear time, it makes sense to take the relaxed problem including only the 2-clauses and see if anything can be deduced from that. In the case of Sudoku there are two types of 2-clauses, those of the form 'x appears in one of the two remaining available spots in this row/column/subsquare' and 'x or y are the remaining possible digits in this cell'.

Whether large Sudoku problems have enough 2-clauses to make deductions based on them alone at all common is unclear, but it seems plausible. Since this technique most definitely is not subsumed by the two techniques I gave previously, it should be included for the sake of completeness, practical or no.



(Post a new comment)


[info]taral
2005-12-15 10:51 am UTC (link)
Someone recently pointed me to http://www.menneske.no/sudoku/eng/reducingmethods.html, which lists a method you did not, their DC method. It's very interesting.

(Reply to this) (Thread)


[info]taral
2005-12-17 08:02 pm UTC (link)
So I wrote code to generate the 2SAT relaxation of a Sudoku problem... it turns out that the board structure itself generates 11,664 2-clauses.

(Reply to this) (Parent)(Thread)


[info]bramcohen
2006-01-03 03:10 am UTC (link)
It's still polynomial!

The other 2-clauses come in when the 'each digit must occur in at least one of the cells in a square/row/column' 9-clauses have possibilities removed until they're reduced to 2-clauses.

(Reply to this) (Parent)(Thread)


[info]taral
2006-01-03 07:06 am UTC (link)
Yup, and quite manageable. After many iterations, I have a solver that runs in a few seconds. Still haven't found anything it can't solve without backtracking.

(Reply to this) (Parent)

Along those lines
[info]ryanlrussell
2005-12-20 10:01 pm UTC (link)
http://www.americanscientist.org/template/AssetDetail/assetid/48550?&print=yes#48706

(Reply to this)


Create an Account
Forgot your login or password?
Login w/ OpenID
English • Español • Deutsch • Русский…