## Why Sudoku is boring

### April 17th, 2013

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. []

1. born Says: