gistfile1.py

# Use a different solved board to generate different tests.
valid = [[5,3,4,6,7,8,9,1,2],
         [6,7,2,1,9,5,3,4,8],
         [1,9,8,3,4,2,5,6,7],
         [8,5,9,7,6,1,4,2,3],
         [4,2,6,8,5,3,7,9,1],
         [7,1,3,9,2,4,8,5,6],
         [9,6,1,5,3,7,2,8,4],
         [2,8,7,4,1,9,6,3,5],
         [3,4,5,2,8,6,1,7,9]]

import random

# Make a copy of a grid so we can modify it without touching the original
def copy (grid):
    return map (lambda x: x[:], grid)

# Assert than a solution remains solvable after mutates-many moves are undone.
# Run iters-many tests of this nature.
def fuzz_true(soln, mutates, iters):
    random.seed()
    for i in range(iters):
        board = copy(soln)
        # Undo a set of moves. This should leave the board solvable
        for mutate in range(mutates):
            x = random.randrange(0,9)
            y = random.randrange(0,9)
            # Might already be 0 in which case we didn't undo "mutates" moves
            # but still generated a reasonable test case
            board[x][y] = 0
        # If this board is invalid the test harness screwed up
        assert check_sudoku(board)
        # If it's unsolvable the solver screwed up
        assert solve_sudoku(board)

# Note: Kinda longish and probably could be cleaner. But it's for a good cause!

# Generates a pair of moves that invalidate the board, then applies some additional
# number of moves and makes sure the board is invalid. Uses all 3 ways a board can be
# invalid.
def fuzz_false (moves, iters):
    if moves > 9*9:
        raise Exception( "Can't make that many moves. Would overflow the board")

    random.seed()
    # 9x9 board of 0's
    empty = [[0] * 9] * 9
    for i in range(iters):
        # Which column to put a duplicate in
        fail_col = random.randrange(0,9)
        # Which row
        fail_row = random.randrange(0,9)
        # Which subgrid
        fail_gridx = random.randrange(0,2)
        fail_gridy = random.randrange(0,2)
        # 3 bad boards
        failures = [col_failure(empty, fail_col), row_failure(empty,fail_row),
                    grid_failure(empty, fail_gridx, fail_gridy)]

        # Make them worse. Subtract 2 to account for the moves made above
        for j in range(moves - 2):
            failures = map(mutate, failures)

        # Now they definitely shouldn't be solvable!
        for x in failures:
            if solve_sudoku(x):
                print x
                assert False

# Generate a failure in the specified column of the board
def col_failure(board, col):
    board = copy(board)
    # I'm sure these aren't randomly distributed, but good enough for government work
    row1 = random.randrange(0,8)
    row2 = random.randrange(row1+1,9)
    fail_digit = random.randrange(1,9)
    board[row1][col] = fail_digit
    board[row2][col] = fail_digit
    return board

# Generate a failure in the specified row
def row_failure(board, row):
    board = copy(board)
    # I'm sure these aren't randomly distributed, but good enough for government work
    col1 = random.randrange(0,8)
    col2 = random.randrange(col1+1,9)
    fail_digit = random.randrange(1,9)
    board[row][col1] = fail_digit
    board[row][col2] = fail_digit
    return board

# Gives board a failure in the specified subgrid
# WARNING: Some boards are completely impossible with this function, so it's clearly not
# exhaustive. Helpful, though? Yes.
def grid_failure(board, gridx, gridy):
    board = copy(board)
    # The starting position of this subgrid
    gridx *= 3
    gridy *= 3
    # How far off the first point is
    dx1 = random.randrange(0,1)
    dy1 = random.randrange(0,1)
    # The second
    dx2 = random.randrange(dx1+1, 2)
    dy2 = random.randrange(dy1+1, 2)
    # Somewhere in that subgrid
    x1 = gridx + dx1
    y1 = gridy + dy1
    # Somewhere else
    x2 = gridx + dx2
    y2 = gridy + dy2
    fail_digit = random.randrange(1,9)
    board[x1][y1] = fail_digit
    board[x2][y2] = fail_digit
    return board

# Fill in an empty position in the board
# WARNING: Assumes board is non-full
def mutate(board):
    fail_digit = random.randrange(1,9)
    while True:
        tryX = random.randrange(0,8)
        tryY = random.randrange(0,8)

        if board[tryX][tryY] == 0:
            board[tryX][tryY] = fail_digit
            return board