Comparison with False - something I don't understand

[Lie Ryan]

On 12/05/10 15:52, Tim Harig wrote:
> On 2010-12-05, Tim Harig <usernet at ilthio.net> wrote:
>> Another, questionable but useful use, is to ignore the complex accounting
>> of your position inside of a complex data structure.  You can continue
>> moving through the structure until an exception is raised indicating
>> that you have reached a boundary of the structure.
> 
> Here is another example in this vein.  

I had another example where using Exception as a control structure
proves to be the most elegant solution.

The problem was a logic puzzle solver (e.g. for Sudoku, Einstein's Logic
problem, etc). The algorithm used is recursive backtracking solver (yes,
I know there are more efficient constraint-based solver, but that's
besides the point).

The function modifies the `puzzle` list in-place such that after the
call `puzzle` list will contain the solution to the puzzle (if any
exists). The solving "in-place" is important since this solver thread
runs in a "solver thread" and there is another "drawing thread" that
draws the currently tested board asynchronously. This means we do not
make a copy of the game board. No locking is done, since it is fine for
the drawing thread to draw malformed board, and we do not want to
compromise the solver's thread's speed.

The two versions of using return value and exception:

def solve_return(puzzle, index):
    """ return True when puzzle is solved,
        return False when backtracking or when no solution exists
    """
    # recursion base case
    if all cells are filled and puzzle does not violate game rules:
        return True # solution found

    if puzzle violates game rules:
        return False # backtrack

    if puzzle[index] is unfilled:
        for i in possible_candidates(puzzle, index):
            puzzle[index] = i
            if solve(puzzle, index+1):
                # solution already found, unwinding the stack
                return True

        # all candidates failed, backtrack
        puzzle[r][c] = unfilled
        return False
    else: # the current cell is part of the base clue
        return solve(puzzle, index+1) # skip it

def main_return():
    puzzle = [...]
    if solve_return(puzzle, 0):
        print('solution found')
    else:
        print('no solution found')

def solve_raise(puzzle, index):
    """ no return value
        throws SolutionFound when solution is found
    """
    # recursion base case
    if all cells are filled and puzzle does not violate game rules:
        raise SolutionFound

    if puzzle[index] is unfilled:
        for i in possible_candidates(puzzle, index):
            puzzle[index] = i
            if puzzle does not violate game rules:
                solve(puzzle, index+1)

        # all candidates failed, backtrack
        puzzle[r][c] = unfilled
    else: # the current cell is part of the base clue
        solve(puzzle, index+1) # skip it

def main_raise():
    puzzle = [...]
    try:
        solve_raise(puzzle, 0)
    except SolutionFound:
        print('solution found')
    else:
        print('no solution found')


Personally, I've found the logic in the exception version clearer than
the return version. Also, the exception version is easier to extend, if
I wanted to add a smarter algorithm that can deterministically infer
certain cell's value (this creates indirect recursion, solve() may call
either infer() or solve() which may call either infer() or solve()), it
can work beside the existing mechanism without explicitly handling the
return flag when a solution is found.

If we suppose that end-of-line (e.g. the semicolon, in C-like language)
is a single-step forward control structure, the if-statement is a n-step
forward control structure, and looping is a n-step backward control
structure. Now, if we suppose function call as a single-step downward
control structure, and function return as a single-step upward control
structure, then exception is a n-step upward control structure. It
throws control upwards of the function call stack, while doing cleanup
along its way up.