Create a gist now

Instantly share code, notes, and snippets.

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.
#! 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 -w
After defining the window, you can "play" with the command
and to explore the options:
python -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
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]))'temp.png')
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])'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
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)
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]:
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))
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
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
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.''')
#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)
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):
text = raw_input()
if text.strip():
#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')
#Click the upper bound spot to make sure the sudoku window has focus, 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]):
if args.no_click:
m.move(click_map[i][j][0], click_map[i][j][1])
else:[i][j][0], click_map[i][j][1])
m.release(click_map[i][j][0], click_map[i][j][1])
#Print the pretty board
for r in pretty_board:
print('|'.join([r[0:3], r[3:6], r[6:9]]))
if pretty_board.index(r) == 8:
elif not (pretty_board.index(r) + 1) % 3:
if __name__ == '__main__':
if args.window:

A colleague of mine wrote a TesseractTrainer in Python last year, whilst interning for my computer vision company. We were using it to recognise text 'in the real world' which lead to . 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!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment