2017-09-05

I spent all weekend working on the Sudoku solver for the AI nanodegree. It's in Python, so there's been a bit of a disconnect there.

I got the basic constraint propagation done earlier in the week, and was able to solve a lot of puzzles using a reduction process. My reduction was dumb, though: I gave it a max number of iterations, and checked each iteration if the puzzle was solved.

def reduce_puzzle(values, max_iter=32):
    rounds = 0
    while rounds < max_iter:
        rounds += 1
        solved = len([box for box in values.keys()
                      if len(values[box]) == 1])
        if solved == len(values):
            break

        values = eliminate(values)
        values = only_choice(values)
    return values

When I looked at the instructor's solution, they had a much better mechanism. They counted the number of solved cells before and after applying constraints; if they were the same, the reduction was assumed to have stalled:

def reduce_puzzle(values):
    """
    Attempt to reduce the puzzle by applying our constraints:
        1. Removing known values from possible values in each unit (eliminate).
        2. Finding unsolved cells in each unit where a value can only appear
           there (only_choice).

    It tracks the number of solved cells (those with only one value) before and
    after applying the constraints. If the number hasn't changed, the reduction
    is assumed to have stalled (e.g. no further reductions can take place), and
    the reduction is halted.

    As a sanity check, if any cell has had all its possible values removed such
    that it is empty, return False.

    Input:
        - Sudoku in dictionary form.
    Output:
        - Resulting Sudoku in dictionary form after applying constraints, or
          False if any cell has had all possible values removed.
    """

    stalled = False
    while not stalled:
        ## Check how many boxes have a determined value.
        solved_values_before = len([box for box in values.keys()
                                    if len(values[box]) == 1])

        ## Apply the constraints.
        # constraint: if a cell in a unit is solved, remove it from the
        # possibilities for other cells.
        values = eliminate(values)

        # constraint: if a value is a possibility in only one cell in a
        # unit, that's the value of that cell.
        values = only_choice(values)

        # Check how many boxes have a determined value, for comparison.
        solved_values_after = len([box for box in values.keys()
                                   if len(values[box]) == 1])

        # If no new values were added, stop the loop.
        stalled = solved_values_before == solved_values_after

        # Sanity check, return False if there is a box with zero
        # available values:
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
    return values

It pays to think about the problem this way. I think most of the programming I've been doing has been "dumb" programming, in the munitions sense. Maybe a better term is "brute force" programming. My version is shorter, but there is the possiblity (especially with complicated puzzles) that more than 32 iterations are needed; this solution has no way of knowing whether it's making progress, so it just imposes a hard limit on the number of rounds. In this problem, you're either making progress or you're not: the before count will never be less than the after count (unless you have a bug!).

I was happy to note that the two things I was graded on (the diagonal units and the naked twins problem) were relatively easy to figure out and write up. I got good marks on the project I submitted, though the comment that I should include more "inline comments" (on code I had to copy from their base code) was a bit grating.

One thing that's nagging at me is how inefficient this code appears to be on the surface: lots of temporary lists (especially via list comprehensions) and copying the sudoku grid (which is a dictionary of 81 keys mapping to a string value).

I kind of want to try programming this in Rust...


Tags: ,