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.

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

  1. my computer really is like 5 times slower than yours.. It took indeed about a minute to run the improved code:
    real	1m3.378s
    user	1m3.256s
    sys	0m0.036s
    
  2. To be fair, "my computer" in this case was the server which also powers this website (and a bunch of other stuff). It's a real workhorse, so don't feel bad xD. By the way: I altered the code slightly to abort as soon as a single solution has been found and timed it, that one yields
    rattle@user:~$ time python3 sudoku.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    0m1.878s
    user    0m1.860s
    sys     0m0.020s
    
    So my guess would be, roughly 10 seconds on your machine.
  3. Of course Donald Knuth offers an even better version of backtracking: http://en.wikipedia.org/wiki/Dancing_Links
    1. Dancing links is a technique used to implement a particular backtracking algorithm efficiently. It is not a version of backtracking in general, and I don't think it is applicable here in a sane way.
      1. "version of backtracking" may be imprecise but there are working, fast implementations of sudoku solvers using a “Dancing Links” backtracking algorithm. See for example this one, which is part of sage.

Leave a Reply

Your email address will not be published.