public
Last active

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.

  • Download Gist
sudokubot.py
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346
#! 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!

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.