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

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. Let me introduce you to the technique of backtracking. Yea, you can read all about it at wikipedia, but I have an important point to make they don't have there. Solving a sudoku is a good example of where and how to apply this technique, so let's do this by example. Say you have a partially solved sudoku. In any empty box of the sudoku, you have a certain set of choices from among the numbers $1$ to $9$. There are some numbers you can not pick because the rules of sudoku don't allow it in this box. If you have an empty box and no choices at all, the sudoku is unsolvable. In a backtracking algorithm, you pick any empty box in your partially solved sudoku and for each option you have, you create a new partially solved sudoku where that box is filled with that option. Then you ask your algorithm recursively for a solution of each of these partially solved sudokus. At some point, your algorithm will either have no more empty box to choose, which means that you have solved the sudoku - or your algorithm will be at an empty box with no options. In the latter case, the actual backtracking occurs and the algorithm goes back to the previous recursion step. Now, there is one important design aspect for backtracking algorithms that you should always follow: > Keep your decision tree as thin as possible. In other words, do not let your algorithm choose just any empty box. Always choose the empty box with the least number of options. To explain why this makes sense, assume that you have a box $b_1$ with options $\{1,3,4,6,7\}$ and a box $b_2$ with options $\{5,8\}$. What you do not know yet, this sudoku is only solvable with $b_1=7$ and $b_2=8$. If you work on $b_1$ in the current recursion step, then for each of the choices $1$, $3$, $4$ and $6$ you will work on large decision subtrees which will never yield a solution. If you had begun working on $b_2$ however, you will only have to work through one fruitless decision subtree for $b_2=5$. At a later recursion level in the tree, you might already be able to see that the only option for $b_1$ is $7$. Bottom line: I did not adhere to that design aspect in my 5 minute sudoku solver hack which I wrote on the backseat of a car. So. I spent an entire ten minutes on redesigning my sudoku solver. Code later, first the triumphant benchmarks:

rattle@hodor:~\$ time python3 sudoku_old.py
[9, 4, 7, 1, 6, 5, 2, 8, 3]
[8, 2, 3, 9, 7, 4, 5, 1, 6]
[6, 5, 1, 3, 2, 8, 9, 4, 7]
[4, 7, 8, 5, 9, 6, 1, 3, 2]
[5, 1, 6, 4, 3, 2, 8, 7, 9]
[2, 3, 9, 8, 1, 7, 4, 6, 5]
[7, 6, 4, 2, 5, 1, 3, 9, 8]
[3, 8, 5, 7, 4, 9, 6, 2, 1]
[1, 9, 2, 6, 8, 3, 7, 5, 4]

real    10m42.555s
user    10m41.490s
sys     0m0.030s

rattle@hodor:~\$ time python3 sudoku_new.py
[9, 4, 7, 1, 6, 5, 2, 8, 3]
[8, 2, 3, 9, 7, 4, 5, 1, 6]
[6, 5, 1, 3, 2, 8, 9, 4, 7]
[4, 7, 8, 5, 9, 6, 1, 3, 2]
[5, 1, 6, 4, 3, 2, 8, 7, 9]
[2, 3, 9, 8, 1, 7, 4, 6, 5]
[7, 6, 4, 2, 5, 1, 3, 9, 8]
[3, 8, 5, 7, 4, 9, 6, 2, 1]
[1, 9, 2, 6, 8, 3, 7, 5, 4]

real    0m14.911s
user    0m14.880s
sys     0m0.000s

so with my new code, solving that "hard" sudoku would take one minute (as opposed to almost one hour) on my friend's computer. And here is the code:

# Recursive backtracking SUDOKU<gasp> solver
# (c) Jesko Hüttenhain
# Published under YouMayOnlyStareAndMarvelInAwePL

def echo(S):
    for i in range(9):
        print(S[i*9:(i+1)*9])
   
# Compute the indices of all boxes which depend on the box with index i. A box
# depends on another if they cannot contain the same value in a legal sudoku.
def affected(i):
    r,c = divmod(i,9)
    I = set(range(c,81,9)) | set(range(r*9,(r+1)*9))
    c //= 3
    r //= 3
    I |= set(range((r*3+0)*9+c*3,(r*3+0)*9+(c+1)*3))
    I |= set(range((r*3+1)*9+c*3,(r*3+1)*9+(c+1)*3))
    I |= set(range((r*3+2)*9+c*3,(r*3+2)*9+(c+1)*3))
    return I

# This is the recursive solver. It expects as its arguments a partially solved
# sudoku S and a list of sets. For each index i, O[i] contains the options that
# are available for box i. 
def _solve(S,O):
    if 0 not in S: # We have found a solution.
        yield [x for x in S]
        return
    # In the following, we find the index "target" of the box with the least
    # number of options still remaining.
    target, best = 0, 10
    for i in range(81):
        if S[i]==0 and len(O[i]) < best:
            target,best = i,len(O[i])
    # Compute all indices that depend on target.
    A = affected(target)
    A.discard(target)
    for k in O[target]:
        # For each option k, we update the list of options, call _solve 
        # recursively and then restore the original state of the array O.
        I = [ i for i in A if k in O[i] ]
        S[target] = k
        for i in I: O[i].remove(k)
        for solution in _solve(S,O): yield solution
        for i in I: O[i].add(k)
    S[target] = 0
   
# This is a wrapper function for solve which generates the initial list of 
# lists of options for the boxes in S.
def solve(S):
    getoptions = lambda i: set(range(1,10)) \
       - set(S[k] for k in affected(i))
    return _solve(S,[getoptions(i) for i in range(81)])
   
if __name__ == '__main__':
    for solution in solve([
        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
    ]): echo(solution)

As the old code did, this also enumerates all solutions. The algorithm will be much faster if you terminate after one single solution has been found. Anyway, I think the numbers speak for themselves: Keep your trees thin and for the love of god, start solving problems other than sudokus.