?

Log in

Sun, Dec. 11th, 2005, 12:02 am
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.

Thu, Dec. 15th, 2005 10:51 am (UTC)
taral

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.

Sat, Dec. 17th, 2005 08:02 pm (UTC)
taral

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.

Tue, Jan. 3rd, 2006 03:10 am (UTC)
bramcohen

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.

Tue, Jan. 3rd, 2006 07:06 am (UTC)
taral

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.