22 Aug
2010
22 Aug
'10
4:15 p.m.
On Sun, Aug 22, 2010 at 1:18 PM, Daniel Fischer
On Sunday 22 August 2010 20:12:16, Vladimir Matveev wrote:
I think the problem is with terribly inefficient data representation.
Worse, it's a terribly inefficient algorithm. The constraints are applied too late, so a huge number of partial boards are created only to be pruned afterwards. Since the ratio between obviously invalid rows and potentially valid rows is large, the constraints should be applied already during the construction of candidate rows to avoid obviously dead branches.
I've written a sudoku solver myself, and IIRC I used lists. It always gave an answer within a second. So I believe Daniel has correctly identified the problem -- you need to prune earlier. Luke