Why Sudoku is boring



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. I grabbed my laptop and started coding a simple branch-and-cut backtracking[1] algorithm. The following code is not the shortest, the meanest, or the coolest Sudoku solver in the world, but it was written in about 6 minutes and solved the hardcoded Sudoku long before the human did it.
S = [
    7, 0, 0, 0, 0, 4, 0, 8, 0,
    0, 0, 0, 0, 0, 1, 3, 9, 6,
    0, 8, 0, 0, 0, 6, 0, 0, 1,
    8, 0, 0, 0, 0, 5, 0, 0, 2,
    0, 3, 0, 0, 8, 0, 0, 0, 0,
    0, 0, 0, 1, 4, 0, 0, 0, 0,
    1, 7, 0, 0, 0, 0, 0, 6, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0,
    2, 5, 0, 0, 9, 0, 0, 4, 8  ]
          
def echo(S):
    for i in range(9):
        print(S[i*9:(i+1)*9])
            
def solve(S):
    if 0 not in S:
        echo(S)
        return
    i = S.index(0)
    col = i % 9
    row = i // 9
    L  = set(S[col:81:9]) 
    L |= set(S[row*9:(row+1)*9])
    col //= 3
    row //= 3
    T  = S[(row*3+0)*9+col*3:(row*3+0)*9+(col+1)*3]
    T += S[(row*3+1)*9+col*3:(row*3+1)*9+(col+1)*3]
    T += S[(row*3+2)*9+col*3:(row*3+2)*9+(col+1)*3]    
    L |= set(T)
    for k in set(range(1,10)) - L:
        S[i] = k
        solve(S)
    S[i] = 0
    
if __name__ == '__main__':
    solve(S)
The idea is fairly simple: The Sudoku is stored as an array of 81 elements, which is created by reading the Sudoku row by row. A zero represents an empty cell. The algorithm is recursive: In each step, it finds an empty cell — if there is none, it already knows that a solution has been found and displays it — otherwise, the algorithm determines all numbers occurring within the same row, column and 9 × 9 square in which the cell resides. It then attempts to place each of the remaining options in that cell and calls itself recursively. So I was easily able to hack down this algorithm, faster by a large amount than it would have taken me to actually solve the Sudoku. Puzzles of this sort do not intrigue me. It's a mindless task, otherwise it could not be translated into a few lines of code this easily. If you do Sudokus to train your mind, I think you'd be better off learning Haskell. That's one hell of a training for the mind. I bet you can solve Sudokus in two lines of Haskell.
  1. Thanks to tobi for pointing out my inaccurate terminology here. [back]

4 Replies to “Why Sudoku is boring”

  1. I really agree with the assessment and this may be a shameless plug but this whole topic is what sparked me to develop an iPhone app called Sudoku Adventure. The way I approached the project was to acknowledge that Sudoku was systematic. Then I broke it down and took things away from the player so their personal system or algorithm was taken away or at least had to be modified. I found this significantly adds to the fun and the challenge. Again sorry for the plug, but this post really resonated with me because I think it is a great way to think about the Sudoku dynamic. Your readers can see what I mean here: https://www.youtube.com/watch?v=B0XRzIk83MM Great work! Scott
  2. Don't worry Scott, I only might pick a quarrel about why $\sqrt 2$ is the villain in your piece. I got no iPhone btw ;). However, I want to support fellow coders best I can, and if that means that $\sqrt 2$ has to be evil, so be it.

Leave a Reply

Your email address will not be published. Required fields are marked *