A bot for solving Sudoku Puzzles. Currently works only on linux, and automated OCR is dubious. Accepts user input to discover the board then automates the input of the solution.

sudokubot.py

#! usr/bin/python

"""
A bot for solving Sudoku Puzzles. It uses PyUserInput for cross-platform
keyboard and mouse support. It supplies the pymouse and pykeyboard modules.

Using OCR may be a upcoming feature.

The first step is to define the game window so that the script can click and
type appropriately.

python sudukobot.py -w

After defining the window, you can "play" with the command

python sudokubot.py

and to explore the options:

python sudokubot.py -h

The script will then point to the cells that contain numbers and waits for the
user's input. The solver comes from Peter Norvig, combining simple constraint
propagation followed by search. Once the solver is done, the script will enter
each of the numbers for you.
"""

import numpy
from pymouse import PyMouse
from pykeyboard import PyKeyboard
import argparse
import sys
import time

VARIANCE_THRESHOLD = 1000

if sys.platform == 'win32':  # Windows
    import ImageGrab, Image, ImageOps
    
    def screenshot(upper_bound, lower_bound):
        """
        Acquires a screenshot of the game area and saves it to temp file.
        """
        im = ImageGrab.grab((upper_bound[0], upper_bound[1], lower_bound[0], lower_bound[1]))
        im.save('temp.png')
        return(numpy.array(im))
    
else:  # Linux
    import gtk.gdk
    
    def screenshot(upper_bound, lower_bound):
        """
        Acquires a screenshot of the game area and saves it to temp file.
        """
        w = gtk.gdk.get_default_root_window()
        size = (lower_bound[0] - upper_bound[0], lower_bound[1] - upper_bound[1])
        pb = gtk.gdk.Pixbuf(gtk.gdk.COLORSPACE_RGB,False,8,size[0],size[1])
        pb = pb.get_from_drawable(w,w.get_colormap(),upper_bound[0],upper_bound[1],0,0,size[0],size[1])
        #pb.save('temp.png','png')
        return pb.get_pixels_array()

__version__ = 0.4

#Here is a basic argument parser for the script using argparse
p = argparse.ArgumentParser(description='Sudokubot ArgParser'.format(__version__))
p.add_argument('-v', '--version', action='version',
               version='Sudokubot v{0}'.format(__version__))
p.add_argument('-w', '--window', action='store_true', default=False,
               help='''Launch a utility to define the dimensions of the Sudoku
               game window on your screen.''')
p.add_argument('-V', '--variance-threshold', action='store', default=VARIANCE_THRESHOLD,
               help='''Define the variance threshold for the identification of
               non empty sudoku cells. The default value of {0} is useful for
               most situations, but may need adjustment if the script is
               identifying false-positives or false-negatives for cells.'''.format(VARIANCE_THRESHOLD))
p.add_argument('-n', '--no-click', action='store_true', default=False,
               help='''Some sudoku game interfaces interact unpleasantly with
               a mouse click, use this argument to suppress mouse clicking but
               not mouse pointing.''')
p.add_argument('-d', '--delay', action='store', default=0.1,
               help='''A time delay for click actions, increase if your game
               crashes or freezes due to rapid clicking.''')
args = p.parse_args()  # The parsed args

#Construct a mouse object from pymouse
m = PyMouse()
#Construct a keyboard object from pykeyboard
k = PyKeyboard()

### Sudoku Logic: Norvig Implementation
def cross(a, b):
    return [i+j for i in a for j in b]

digits = '123456789'
cols = digits
rows = 'ABCDEFGHI'
cells = cross(rows, cols)
#Compose a list of row members, column members, and subgrid members
unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
#For every cell, compile a list of its row, column, and subgrid mates
units = dict((s, [u for u in unitlist if s in u])
             for s in cells)
#Compress the previous list to unique members
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in cells)

def grid_values(grid):
    """Map a grid value string onto our cells"""
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    return dict(zip(cells, chars))

def parse_grid(grid):
    """Convert grid to a dict of potentials, {cell: digits}, or
    return False if a contradiction is detected."""
    # To start, every cell can be any digit; then assign values from the grid.
    values = dict((s, digits) for s in cells)
    for s,d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False ## (Fail if we can't assign d to cell s.)
    return values

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

def some(seq):
    "Return some element of seq that is true."
    for e in seq:
        if e: return e
    return False

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a cell s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
        return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
        dplaces = [s for s in u if d in values[s]]
    if len(dplaces) == 0:
        return False ## Contradiction: no place for this value
    elif len(dplaces) == 1:
        # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

def display(values):
    "Display these values as a 2-D grid."
    width = 1+max(len(values[s]) for s in cells)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print(''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols))
        if r in 'CF': print(line)
    print('\n')

def solve(grid):
    return search(parse_grid(grid))

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in cells):
        return values ## Solved!
    ## Chose the unfilled cell s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in cells if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d))
                for d in values[s])
### End Sudoku Logic: Norvig Implementation

def define_game_window():
    """
    Asks for user input to define the dimension of the game window; writes
    these dimensions to the sudoku_box.txt file. For the sake of consistency
    between sudoku presentations, these points should be the bounds of the
    sudoku grid (on the edge of a number-holding cell).
    """
    #Get the upper left corner
    print('''\nPlease place the mouse on the upper left hand corner of the \
Sudoku game grid(grid only for best results). Then press Enter.\n''')
    raw_input('Upper left corner: ')
    mouse_x1, mouse_y1 = m.position()
    print('(X: {0}, Y: {1})'.format(mouse_x1, mouse_y1))
    
    #Get the lower right corner
    print('''\nNow place the mouse on the lower right hand corner of the \
Sudoku game grid(grid only for best results). Then press Enter.\n''')
    raw_input('Lower right corner: ')
    mouse_x2, mouse_y2 = m.position()
    print('(X: {0}, Y: {1})'.format(mouse_x2, mouse_y2))
    
    #Ask if these should be saved
    print('Would you like to save these coordinates?')
    if raw_input('[y/n]') in ['y', 'Y']:
        with open('sudoku_box.txt', 'w') as out:
            for i in [mouse_x1, ',', mouse_y1, '\n', mouse_x2, ',', mouse_y2]:
                out.write(str(i))

def screen_map(box):
    """
    Uses the game window dimensions in sudoku_box.txt to define image windows
    and click points.
    """
    images, clicks = [],[]
    fl, sl = box.readlines()
    upper_x, upper_y = [int(i) for i in fl.split(',')]
    lower_x, lower_y = [int(i) for i in sl.split(',')]
    width = (lower_x - upper_x) / 9.0
    length = (lower_y - upper_y) / 9.0

    for i_y in xrange(9):
        i_col = []
        c_col = []
        for i_x in xrange(9):
            x1 = int(round(upper_x + (i_x + .2) * width))
            x2 = int(round(upper_x + (i_x + .8) * width))
            y1 = int(round(upper_y + (i_y + .2) * length))
            y2 = int(round(upper_y + (i_y + .8) * length))
            mx = int(round(upper_x + (i_x + .5) * width))
            my = int(round(upper_y + (i_y + .5) * length))
            i_col.append(([x1, y1], [x2, y2]))
            c_col.append((mx, my))
        images.append(i_col)
        clicks.append(c_col)
    return upper_x, upper_y, images, clicks
        
def variance_threshold(pixel_array, threshold):
    """If it returns False, ignore the image"""
    #Calculate the mean pixel value, images are loaded in greyscale
    value = 0
    count = 0
    for i in pixel_array:
        for j in i:
            count += 1
            value += j[0]
    mean_value = float(value) / count
    
    #Find the Variance
    variance = 0
    for i in pixel_array:
        for j in i:
            variance += ((j[0] - mean_value) ** 2) / count
    #raw_input(variance)
    if variance > threshold:
        return True
    return False
    
def sudoku():
    """
    The main method for solving sudoku on the screen. It begins by establishing
    the game board/grid by querying human input or using machine OCR. Once it
    has the game board it finds the solution using Norvig's implementation (a
    combination of constraint propagation and search).
    
    Once the solution has been found, it will endeavor to enter the appropriate
    numbers automatically using PyMouse and PyKeyboard.
    """
    #Read the game area dimensions from sudoku_box.txt, quit if undefined
    try:
        sudoku_box = open('sudoku_box.txt', 'r')
    except IOError:
        print('''sudoku_box.txt not found! Run this script with \"--window\" to \
set custom dimensions for the Sudkou window.''')
        sys.exit(0)
    else:
        #Parse the contents of sudoku_box.txt to get image and click positions
        u_x, u_y, image_map, click_map = screen_map(sudoku_box)
        sudoku_box.close()
    board = []
    for i_x in xrange(9):
        col = []
        for i_y in xrange(9):
            pix_array = screenshot(image_map[i_x][i_y][0],image_map[i_x][i_y][1])
            if not variance_threshold(pix_array, args.variance_threshold):
                col.append('0')
                continue
            else:
                m.move(click_map[i_x][i_y][0],click_map[i_x][i_y][1])
                text = raw_input()
            if text.strip():
                col.append(text.strip())
            else:
                col.append('0')
        board.append(col)
    #Flatten the list and convert to string
    grid = ''.join([j for i in board for j in i])
    #Get the solution
    solution = solve(grid)
    #Report failure
    if solution is False:
        print('No Solution could be found!\nThere was probably an error reading the board')
        sys.exit()
    #Click the upper bound spot to make sure the sudoku window has focus
    m.press(u_x, u_y)
    m.release(u_x, u_y)
    #Iterate over the solution dict to operate the cursor and keyboard
    #Also generates a pretty board
    pretty_board = []
    for i in xrange(9):
        row = ''
        for j in xrange(9):
            val = solution[''.join(['ABCDEFGHI'[i], '123456789'[j]])]
            row += val
            if int(board[i][j]):
                continue
            if args.no_click:
                m.move(click_map[i][j][0], click_map[i][j][1])
            else:
                m.press(click_map[i][j][0], click_map[i][j][1])
                m.release(click_map[i][j][0], click_map[i][j][1])
            time.sleep(args.delay)
            k.tap_key(val)
            time.sleep(args.delay)
        pretty_board.append(row)
    #Print the pretty board
    print('Solution:')
    for r in pretty_board:
        print('|'.join([r[0:3], r[3:6], r[6:9]]))
        if pretty_board.index(r) == 8:
            break
        elif not (pretty_board.index(r) + 1) % 3:
            print('------------')

if __name__ == '__main__':
    if args.window:
        define_game_window()
    else:
        sudoku()

A colleague of mine wrote a TesseractTrainer in Python https://github.com/BaltoRouberol/TesseractTrainer last year, whilst interning for my computer vision company. We were using it to recognise text 'in the real world' which lead to http://openplants.co.uk/ . tesseract should be good enough for your job, other people have used neural networks and opencv (line segmentation to find the boxes) to make suduko solvers on iPhones. Good luck!