backtracking – nullteilerfrei

It causes me unspeakable agony to see that my post about why sudoku is boring is one of the most frequented posts in this blog, mostly because most of my readers clearly disagree with the title. I recently received an email titled "why sudoku is not all that boring" by an old friend, and he taunted me that the sudoku

S = [
  0, 0, 0, 0, 6, 0, 0, 8, 0,
  0, 2, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 1, 0, 0, 0, 0, 0, 0,
  0, 7, 0, 0, 0, 0, 1, 0, 2,
  5, 0, 0, 0, 3, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 4, 0, 0,
  0, 0, 4, 2, 0, 1, 0, 0, 0,
  3, 0, 0, 7, 0, 0, 6, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 5, 0 ]

would take my 5-minute hack of a backtracking algorithm

real    51m3.656s
user    50m32.260s
sys     0m2.084s

to solve. So, it seems like some sudokus are really hard, even for a computer, right? Wrong wrong wrong wrong wrong. Read how to implement backtracking properly.

I was riding the backseat of a car, a pal of mine with a large Sudoku book on the seat beside me. I glared over at him and remarked that I find Sudokus utterly boring and would feel that my time is wasted on any of them. He looked up at me, clearly demanding an explanation for that statement. I continued to explain that a computer program could solve a Sudoku with such ease that there is no need for humans to do it. He replied that something similar could be said about chess, but still it's an interesting game. And it was then, that I realized why Sudoku is so horribly boring, and chess is not. It was the fact that I could code a Sudoku solver and solve the Sudoku he was puzzling about, and I would be able to do it faster than it would take him to solve the entire thing by hand. This does not apply to chess, evidently. Of course, I confidently explained this to him. »Prove it.«, he said. So I did. Do you want to know more?

Why someone thought that sudoku might not be boring, while actually you should learn how to properly implement backtracking

Why Sudoku is boring