# Sudoku solver with Tkinter

The code below is a Sudoku solver using backtracking. There is a fast mode which doesn't display the permutations in the Tk widget in real time; only the solved grid.

This is the second version of a sudoku solver using class inheritance and Tkinter. The first version was a one class version which was much faster (15 times). Can the code be improved to speed things up and match the speed of the previous version?

Is it legible and 'pythonic' enough? Is this the best way to structure the data and class inheritance? does instantiating always mean slower script sacrificing performance for clarity?

#!/usr/bin/python
#Xavier B. 2017

import time as tm
import Tkinter as tk
import cProfile

GRIDA = [
3, 0, 8, 0, 1, 4, 0, 0, 9,
0, 0, 2, 0, 6, 0, 1, 7, 4,
7, 1, 0, 5, 9, 0, 8, 0, 0,
0, 0, 0, 9, 0, 3, 4, 1, 7,
5, 9, 0, 2, 4, 0, 3, 0, 0,
4, 3, 7, 0, 0, 6, 0, 5, 0,
1, 0, 5, 4, 0, 0, 0, 3, 8,
0, 2, 0, 0, 3, 5, 7, 0, 1,
0, 4, 3, 6, 0, 1, 0, 9, 0
]
GRIDNIL = [
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0
]
ULTIGRID = [
0, 0, 0, 0, 0, 4, 2, 0, 0,
2, 0, 0, 5, 1, 0, 0, 0, 0,
7, 8, 0, 0, 0, 6, 4, 0, 0,
5, 9, 0, 0, 0, 7, 0, 0, 0,
0, 4, 0, 0, 0, 0, 0, 8, 0,
0, 0, 0, 2, 0, 0, 0, 9, 5,
0, 0, 7, 4, 0, 0, 0, 3, 2,
0, 0, 0, 0, 3, 9, 0, 0, 1,
0, 0, 3, 1, 0, 0, 0, 0, 0
]
GRIDB = [
0, 0, 5, 8, 0, 0, 0, 0, 2,
8, 0, 0, 0, 0, 0, 4, 0, 0,
0, 0, 9, 5, 0, 0, 0, 7, 8,
7, 0, 0, 3, 0, 0, 1, 0, 0,
0, 4, 0, 0, 0, 0, 0, 8, 0,
0, 0, 6, 0, 0, 8, 0, 0, 3,
6, 9, 0, 0, 0, 3, 7, 0, 0,
0, 0, 2, 0, 0, 0, 0, 0, 9,
1, 0, 0, 0, 0, 7, 2, 0, 0
]

class Solver(object):
def __init__(self, grid, mode):
self._grid = grid
self._mode = mode
solver = Grid(self._grid, self._mode)
Solver.root = tk.Tk()
Solver.root.title('')
Solver.window = tk.Canvas(Solver.root, height=1000, width=750, bg='white')
Solver.window.pack(expand=True)
Solver.root.after(0, solver.draw_grid)
Solver.root.mainloop()

class Grid(Solver):
def __init__(self, grid, mode):
Grid._grid = grid
Grid._cells = []
self._mode = mode
self._labels = {}
self.populate_cells()
self._empty_cells = []
self.empty_cells()
self._iterations = 0

def populate_cells(self):
for ind in range(81):
c = Cell(ind)
self._cells.append(c)

def empty_cells(self):
"""list of empty cells positions and removes those solvable."""
for ind in range(81):
c = self._cells[ind]
if c._value == 0:
c._search_range = c.new_search_range()
self._empty_cells.append(c)
else:
c._solved = True
if len(c._search_range) == 1:
c._value = c._search_range[0]
c._pre_solved = True
del self._empty_cells[-1]

def solve(self, index):
"""main loop iterate through the empty cells and backtrack."""
self._iterations += 1
c = self._empty_cells[index]
c.new_cell_value()
if c._value == None:
c._solved = False
c._value = 0
if self._mode != 'fast':
self._labels[(c._rw, c._col)].config(text=str(' '))
index -= 1  #backtrack to previous empty cell at next iteration
else:
if self._mode != 'fast':
self._labels[(c._rw, c._col)].config(text=str(c._value))
c._solved = True
index += 1
if index<len(self._empty_cells) and index>=0:
Solver.root.after(0, lambda: self.solve(index))
else:
self.update_cells_tags()
Solver.root.update()
print 'solved in {} iterations'.format(self._iterations)
tm.sleep(2)
Solver.root.after(0, self.quit_solve)

def quit_solve(self):
try:
Solver.root.destroy()
except:
pass

def draw_grid(self):
"""draw the grid and create a label for each cell in Tk."""
for i in range(50, 685, 70):
if (i-50)%210 == 0:
lw=5
else:
lw=1
Solver.window.create_line([(50, i), (680, i)],
width=lw,
joinstyle='miter',
capstyle='projecting')
Solver.window.create_line([(i, 50), (i, 680)],
width=lw,
joinstyle='miter',
capstyle='projecting'
)
for c in self._cells:
if c._pre_solved:
txt = str(c._value)
backg = "#fcfce1" # solved before backtracking loop
elif c._solved:
txt = str(c._value)
backg = "#f7d52e" # original grid
else:
txt = ' '
backg = '#ffffff' # empty cells
coloured_sq = Solver.window.create_rectangle(51 + c._y, 51 + c._x,
119 + c._y, 119 + c._x,
fill=backg,
outline=backg)
self._labels[(c._rw, c._col)] = tk.Label(Solver.window,
text=txt,
relief=tk.FLAT,
bg = backg,
font=("Courier", 54))
self._labels[(c._rw, c._col)].place (x=66+c._y, y=55+c._x)
Solver.window.pack(expand=True)
Solver.root.after(0, self.solve(0)) #start looping

def update_cells_tags(self):
for c in self._cells:
self._labels[(c._rw, c._col)].config(text=str(c._value))

def show(self):
"""for testing prints the grid in a pretty format."""
for r in range(9):
if r%3 == 0:
print '+ - - - - + - - - - + - - - - +'
s = ''
for c in range(9):
if c%3 == 0:
s += '|'
if self._cells[r*9+c]._value == 0:
s += ' . '
else:
s += ' '+str(self._cells[r*9+c]._value)+' '
s += '|'
print s
print '+ - - - - + - - - - + - - - - +'

class Cell(Grid):
"""81 cells in a 9x9 sudoku grid."""
def __init__(self, index):
self._grid = Grid._grid
self._rw = index/9
self._col = index - self._rw * 9
self._index = index
self._value = self._grid[index]
self._x = self._rw * 70
self._y = self._col * 70
self._search_range = range(1, 10)
self._pre_solved = False
self._solved = not self._value==0

def new_cell_value(self):
"""the next candidate value and the remaining candidates."""
for v in self._search_range:
if self.check_unique(v): # candidate value is unique one row, column or square
self._search_range.remove(v)
break
else:
v = None # all values already in row, column or square
self._search_range = [1, 2, 3, 4, 5, 6, 7, 8, 9]
self._value = v

def new_search_range(self):
"""the range of possible values for the cell."""
return [n for n in range(1, 10) if self.check_unique(n)]

def check_unique(self, v):
"""no cell with value v exists in the row, column or square."""
if v not in self.row() and \
v not in self.column() and \
v not in self.square():
return True
else:
return False

def column(self):
"""Returns the list of cells in the column."""
return [Grid._cells[self._col+incr]._value for incr in range(0, 81, 9)]

def row(self):
"""Returns the list of cells in the row."""
return [Grid._cells[self._rw*9+c]._value for c in range(9)]

def square(self):
"""Returns the list of cells in the square."""
sq = []
rcorner = (self._rw/3)*3
ccorner = (self._col/3)*3
for r in (0, 1, 2):
for c in (0, 1, 2):
sq.append(Grid._cells[(r+rcorner)*9+c+ccorner]._value)
return sq

def main():
solver = Solver(ULTIGRID, None)

cProfile.run('main()')


The faster/simpler version below:

#!/usr/bin/python
#Xavier B. 2017

import copy
import time

GRIDA = [
[3, 0, 8, 0, 1, 4, 0, 0, 9],
[0, 0, 2, 0, 6, 0, 1, 7, 4],
[7, 1, 0, 5, 9, 0, 8, 0, 0],
[0, 0, 0, 9, 0, 3, 4, 1, 7],
[5, 9, 0, 2, 4, 0, 3, 0, 0],
[4, 3, 7, 0, 0, 6, 0, 5, 0],
[1, 0, 5, 4, 0, 0, 0, 3, 8],
[0, 2, 0, 0, 3, 5, 7, 0, 1],
[0, 4, 3, 6, 0, 1, 0, 9, 0]
]
GRIDNIL = [
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0]
]
ULTIGRID = [
[0, 0, 0, 0, 0, 4, 2, 0, 0],
[2, 0, 0, 5, 1, 0, 0, 0, 0],
[7, 8, 0, 0, 0, 6, 4, 0, 0],
[5, 9, 0, 0, 0, 7, 0, 0, 0],
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[0, 0, 0, 2, 0, 0, 0, 9, 5],
[0, 0, 7, 4, 0, 0, 0, 3, 2],
[0, 0, 0, 0, 3, 9, 0, 0, 1],
[0, 0, 3, 1, 0, 0, 0, 0, 0]
]
GRIDB = [
[0, 0, 5, 8, 0, 0, 0, 0, 2],
[8, 0, 0, 0, 0, 0, 4, 0, 0],
[0, 0, 9, 5, 0, 0, 0, 7, 8],
[7, 0, 0, 3, 0, 0, 1, 0, 0],
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[0, 0, 6, 0, 0, 8, 0, 0, 3],
[6, 9, 0, 0, 0, 3, 7, 0, 0],
[0, 0, 2, 0, 0, 0, 0, 0, 9],
[1, 0, 0, 0, 0, 7, 2, 0, 0]
]

def show(grid):
"""print grid in a pretty format."""
for r in range(9):
if r%3 == 0:
print '+ - - - - + - - - - + - - - - +'
s = ''
for c in range(9):
if c%3 == 0:
s += '|'
if grid[r][c] == 0:
s += ' . '
else:
s += ' '+str(grid[r][c])+' '
s += '|'
print s
print '+ - - - - + - - - - + - - - - +'

class Solve(object):
"""Resolve the sudoku grid using backtracking and print results."""
def __init__(self, grid):
self._grid = grid
self._xy = self.empty_cells()
self._search_ranges = [range(1, 10) for i in range(len(self._xy))]
index = 0
self._iterations = 0

def square(self, (x, y)):
"""Return the list of cells in the square including the cell(x,y)."""
sq = []
rcorner = (y/3)*3
ccorner = (x/3)*3
for r in (0, 1, 2):
for c in (0, 1, 2):
value = self._grid[r+rcorner][c+ccorner]
sq.append(value)
return sq

def row(self, (x, y)):
"""Return the list of cells in the row including the cell(x,y)."""
return [v for v in self._grid[y]]

def column(self, (x, y)):
"""Return the list of cells in the column including the cell(x,y)."""
return [self._grid[c][x] for c in range(9)]

def search_range(self, (y, x)):
r = []
for n in range(10):
if self.unique(n, (x, y)):
r.append(n)
return r

def empty_cells(self):
"""Return the list of tuple coordinates of all empty cells."""
xy = []
for r in range(9):
for c in range(9):
if self._grid[r][c] == 0:
xy.append((r, c))
return xy

def unique(self, n, (x, y)):
if n not in self.row((x, y)) \
and n not in self.column((x, y)) \
and n not in self.square((x, y)):
return True
else:
return False

def new_cellvalue(self, (y, x), search_range):
"""return a candidate n and the remaining candidates for a cell(x,y)."""
for n in search_range:
if self.unique(n, (x, y)):
search_range.remove(n)
break # candidate number isn't in the cell's row, column or square
else:
n = None
search_range = []
return n, search_range

def pre_check(self):
print 'pre checking'
print len(self._xy)
for index, xy in enumerate(self._xy):
if len(self.search_range(xy))==1:
self._grid[xy[0]][xy[1]]=self.search_range(xy)[0]
del self._xy[index]
return

def values(self, index):
self.pre_check()
while index<len(self._xy) and index>=0:
self._iterations += 1
cellvalue = self.new_cellvalue((self._xy[index]),
self._search_ranges[index])
if cellvalue[0] == None:
self._grid[self._xy[index][0]][self._xy[index][1]] = 0
self._search_ranges[index] = [1, 2, 3, 4, 5, 6, 7, 8, 9]
index -= 1  #backtrack to previous empty cell
else:
self._grid[self._xy[index][0]][self._xy[index][1]] = cellvalue[0]
self._search_ranges[index] = cellvalue[1]
index += 1
return self._grid

def main(_grid):
original = copy.deepcopy(_grid)
solvedsoduku = Solve(original)
grid = solvedsoduku.values(0)
print 'original'
show(_grid)
print '\nsolved'
show(grid)

totaltime=0
start_time = time.clock()
main(GRIDB)
totaltime+= time.clock() - start_time
print '{} seconds'.format(totaltime)

• your code has a call to sleep in it, which should almost never be done in a GUI as it freezes the entire GUI. What's the purpose for calling sleep? – Bryan Oakley Feb 3 '17 at 16:00
• So the grid is visible for a while when it is solved. Then, the root is destroyed and the grid disappears. – user2718378 Feb 3 '17 at 17:52

I will be commenting on the first version, since it is the one using Tkinter as per the question title.

A few things on the GUI part for starter:

• Since you only call Grid.draw_grid() once, at the beginning, your cells can be in only two states: empty or solved. This means you only need to define 2 background colors since they will never be updated.
• You try hard to draw extra bold lines in Grid.draw_grid() only to override them with each number's rectangle. You should instead do the opposite: draw the rectangles and then draw the lines. To simplify a bit, I’d draw a big rectangle a bit larger than the area for the border and the inner lines and then draw the 4 missing bolder lines.
• You can get rid of the time module as time.sleep(2) followed by Solver.root.after(0, self.quit_solve) can be replaced by Solver.root.after(2000, self.quit_solve): the waiting will be done in Tkinter. But I don't really understand the need to auto-close the window.
• You don't need a lambda to pass parameters to functions in an after call: everything you put after the function will be passed as parameter. So you can turn Solver.root.after(0, lambda: self.solve(index)) into Solver.root.after(0, self.solve, index).

Now that being said, you don't use classes nor inheritance the proper way. Inheritance, as in class Cell(Grid), is meant to describe an "is a" relationship, where Cell can do whatever Grid is up to plus a bit more. In this case, a cell is not a grid, there is absolutely no need to use inheritance here. However, cells belong to a grid, and that's what you represent in your Grid.populate_cells() method.

Comming from the same kind of misconception, you use class attributes the wrong way (like Grid._cells). What if I want to solve two sudoku in the same program? When instanciating the second one, Grid._cells that contained data for the first one would be overriden. This is wrong.

Cells should know nothing about other cells, only the grid should. Same: the grid should know nothing about the rendering engine (Solver in this case, which is a pretty bad name for a graphical component IMHO), only about its cells and how to solve the grid.

Basically, a cell should only hold information and have next to no action available. I'd just add a method to get the next possible value and a method to reset the cell to an empty state. Something along the lines of:

class Cell(object):
"""81 cells in a 9x9 sudoku grid."""
def __init__(self, value):
self.value = value
self.solvable = value is None
if value is None:
self._possibilities = iter(range(1, 10))
else:
self._possibilities = iter([])

@property
def empty(self):
return self.value is None

@property
def text(self):
return ' ' if self.value is None else str(self.value)

def __str__(self):
return '.' if self.value is None else str(self.value)

def reset(self):
if self.solvable:
self.value = None
self._possibilities = iter(range(1, 10))

def next(self):
return next(self._possibilities)


@property hide a method behind an attribute. So you can do if cell.empty: which is nicer in my opinion. Here the cell hold 4 "attributes": value, solvable, empty, and text. And have 2 possible actions: getting the next value to try for this cell, and resetting the cell to an empty one (only if solvable: i.e. if it didn't have a value in the first place).

Now it's up to the Grid, which will be aware of rows and columns, to implement logic related to getting the right cell and trying the various values in order to solve the grid.

Only after that would the Tkinter part come into play.

My take on that would look like:

#!/usr/bin/python

import Tkinter as tk
import itertools

GRIDA = [
3, 0, 8, 0, 1, 4, 0, 0, 9,
0, 0, 2, 0, 6, 0, 1, 7, 4,
7, 1, 0, 5, 9, 0, 8, 0, 0,
0, 0, 0, 9, 0, 3, 4, 1, 7,
5, 9, 0, 2, 4, 0, 3, 0, 0,
4, 3, 7, 0, 0, 6, 0, 5, 0,
1, 0, 5, 4, 0, 0, 0, 3, 8,
0, 2, 0, 0, 3, 5, 7, 0, 1,
0, 4, 3, 6, 0, 1, 0, 9, 0,
]
GRIDNIL = [
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0,
]
ULTIGRID = [
0, 0, 0, 0, 0, 4, 2, 0, 0,
2, 0, 0, 5, 1, 0, 0, 0, 0,
7, 8, 0, 0, 0, 6, 4, 0, 0,
5, 9, 0, 0, 0, 7, 0, 0, 0,
0, 4, 0, 0, 0, 0, 0, 8, 0,
0, 0, 0, 2, 0, 0, 0, 9, 5,
0, 0, 7, 4, 0, 0, 0, 3, 2,
0, 0, 0, 0, 3, 9, 0, 0, 1,
0, 0, 3, 1, 0, 0, 0, 0, 0,
]
GRIDB = [
0, 0, 5, 8, 0, 0, 0, 0, 2,
8, 0, 0, 0, 0, 0, 4, 0, 0,
0, 0, 9, 5, 0, 0, 0, 7, 8,
7, 0, 0, 3, 0, 0, 1, 0, 0,
0, 4, 0, 0, 0, 0, 0, 8, 0,
0, 0, 6, 0, 0, 8, 0, 0, 3,
6, 9, 0, 0, 0, 3, 7, 0, 0,
0, 0, 2, 0, 0, 0, 0, 0, 9,
1, 0, 0, 0, 0, 7, 2, 0, 0,
]

class Window(object):
def __init__(self, solver):
self.solver = solver
self._root = root = tk.Tk()
self._canvas = tk.Canvas(root, height=750, width=750, bg='white')
self._labels = {}

# Draw background, a bit larger
self._canvas.create_rectangle(
48, 48, 682, 682,
fill='black', outline='black')

# Draw cells
for i, row in enumerate(solver.rows):
for j, cell in enumerate(row):
x = i * 70
y = j * 70
background_color = '#ffffff' if cell.solvable else '#f7d52e'
self.rectangle = self._canvas.create_rectangle(
51 + y, 51 + x, 119 + y, 119 + x,
fill=background_color,
outline=background_color)
self._labels[(i, j)] = label = tk.Label(
self._canvas, text=cell.text, relief=tk.FLAT,
bg=background_color, font=("Courier", 38))
label.place(x=66 + y, y=55 + x)

def draw_line(x1, y1, x2, y2):
self._canvas.create_line(
[(x1, y1), (x2, y2)], width=3,
joinstyle='miter', capstyle='projecting')
draw_line(260, 50, 260, 680)
draw_line(50, 260, 680, 260)
draw_line(470, 50, 470, 680)
draw_line(50, 470, 680, 470)

self._canvas.pack(expand=True)

def run(self, delay=None):
if delay is None:
self._root.after(0, self.iterate_fast)
else:
self._root.after(0, self.iterate, delay)
self._root.mainloop()

def iterate(self, delay):
self.redraw()
if not self.solver.solved:
self.solver.solve()
self._root.after(delay, self.iterate, delay)

def iterate_fast(self):
try:
self.solver.solve()
except IndexError:
self.redraw()
else:
self._root.after(0, self.iterate_fast)

def redraw(self):
for pos, cell in enumerate(self.solver.cells):
self._labels[divmod(pos, 9)].config(text=cell.text)

class Solver(object):
def __init__(self, grid):
self.grid = [
[Cell(c if c else None, i, j) for j, c in enumerate(row)]
for i, row in enumerate(grouper(grid, 9))
]
self.empty_cells = [c for row in self.grid for c in row if c.solvable]
self.index = 0

@property
def cells(self):
return (cell for row in self.grid for cell in row)

@property
def rows(self):
return iter(self.grid)

@property
def columns(self):
return itertools.izip(*self.grid)

@property
def solved(self):
return self.index >= len(self.empty_cells)

def solve(self):
cell = self.empty_cells[self.index]
while True:
try:
current_value = next(cell)
except StopIteration:
self.index -= 1
cell.reset()
break
else:
if self.is_unique(current_value, cell.row, cell.col):
cell.value = current_value
self.index += 1
break

def is_unique(self, value, row, column):
"""no cell with value v exists in the row, column or square."""
square_row = (row // 3) * 3
square_col = (column // 3) * 3

# Current row
if any(value == cell.value for cell in self.grid[row]):
return False

# Current column
if any(value == row[column].value for row in self.grid):
return False

# Current square
for row in self.grid[square_row:square_row+3]:
for cell in row[square_col:square_col+3]:
if value == cell.value:
return False
return True

class Cell(object):
"""81 cells in a 9x9 sudoku grid."""
def __init__(self, value, row, col):
self.row = row
self.col = col
self.value = value
self.solvable = value is None
if value is None:
self._possibilities = iter(range(1, 10))
else:
self._possibilities = iter([])

@property
def empty(self):
return self.value is None

@property
def text(self):
return ' ' if self.value is None else str(self.value)

def __str__(self):
return '.' if self.value is None else str(self.value)

def reset(self):
if self.solvable:
self.value = None
self._possibilities = iter(range(1, 10))

def next(self):
return next(self._possibilities)

def grouper(iterable, n):
"Collect data into fixed-length chunks or blocks"
# grouper('ABCDEFGHI', 3) --> ABC DEF GHI"
args = [iter(iterable)] * n
return itertools.izip(*args)

def print_grid(solver):
separator = '+ - - - + - - - + - - - +'
for i, row in enumerate(solver.rows):
if i % 3 == 0:
print separator
inner_line = ' | '.join(
' '.join(map(str, group))
for group in grouper(row, 3))
print '|', inner_line, '|'
print separator

def main(grid, delay=None):
solver = Solver(grid)
window = Window(solver)
window.run(delay)

if __name__ == '__main__':
import cProfile
cProfile.run('main(ULTIGRID, 1)')


This makes use of the grouper recipe from itertools to extract groups of n elements from an iterable more elegantly than using modulus.