The New Sudoku Players' Forum

[r.e.s.]

By "brute force", every valid sudoku can be routinely solved (e.g., on my system the Susser typically takes only a fraction of a second -- about 0.9 sec for the so-called toughest sudoku). I'm not sure exactly what steps are being performed, but my question is ... In the worst cases, are there so many steps that a human could not feasibly perform all of them? (E.g., how many steps -- for some reasonable definition of "step" -- might the Susser be performing in that 0.9 sec?)

[udosuk]

This is probably not exactly relevant, but I'm interested in how well a brute force program performs to solve killer sudokus. I mean really really demonic ones (e.g. Magic Killer). I've seen several that took dukuso's program more than 30~45 mins on my 2.4 GHz PC... Is it ever possible (in the near future) for a program to solve such hard killers in ~0.9 sec?

[ab]

This is probably not exactly relevant, but I'm interested in how well a brute force program performs to solve killer sudokus. I mean really really demonic ones (e.g. Magic Killer). I've seen several that took dukuso's program more than 30~45 mins on my 2.4 GHz PC... Is it ever possible (in the near future) for a program to solve such hard killers in ~0.9 sec?

I've written a fairly basic solver, which implements pairs and x wings and gx wings, so there are many killer puzzles which it can't solve. But to brute force them is easy. You just pick a cell and try all the possible candidates. If all the candidates except one lead to a contradiction then you can place that candidate in the cell. Using this technique takes about 30 seconds to solve a puzzle. It takes about 10 minutes to decide if a puzzle has multiple solutions though!

[udosuk]

Thanks ab, if your programming idea works it'd be exactly what I'm looking for! I don't care if the killer puzzle is solved by logical steps, just if you can find the first solution in 30 secs and all solutions in 10 mins for every killer sudoku puzzle it'd be very nice! Do you think you can write a program like that soon? Thanks!

[ab]

I didn't look at the link you referred to before posting. I was talking about fiendish normal sudoku puzzles. Not tried writing a program to solve the type of puzzle you refer to and I'm not sure if what I described would apply to them! Sorry for the misunderstanding.