Last active
December 11, 2015 20:48
-
-
Save SavinaRoja/4658043 to your computer and use it in GitHub Desktop.
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.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#! 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() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
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!