http://www.spoj.pl/problems/SUDOKU/

Problem solved. I encountered it 2 years ago and the problem stayed in my mind till now. It took me two days to code, due to my weak programming skill.

At last I've solved it. Not very fast though. The algorithm used was dancing link, but I'm not sure if this is the main reason for the speed up. Converting Sudoku into SAT seems to help prune the search tree.

Source code available.

http://en.wikipedia.org/wiki/Dancing_links
http://en.wikipedia.org/wiki/Algorithm_X
http://en.wikipedia.org/wiki/Exact_cover#Sudoku

Advertisements