## Is "brute force" solution always humanly feasible?

Everything about Sudoku that doesn't fit in one of the other sections

### Is "brute force" solution always humanly feasible?

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?)
r.e.s.

Posts: 337
Joined: 31 August 2005

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?
udosuk

Posts: 2698
Joined: 17 July 2005

udosuk wrote: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!
ab

Posts: 451
Joined: 06 September 2005

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!
udosuk

Posts: 2698
Joined: 17 July 2005

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.
ab

Posts: 451
Joined: 06 September 2005