# Two versions of Sudoku

I have written two versions of a sudoku solver. Both can solve 9x9 sudoku boards in <200 ms. One of the implementations uses numpy. I am looking for feedback on both, but particularly on why my version using numpy is ~50% slower than the one using a list of lists.

Regular:

from time import time
from itertools import product

class board:
def __init__(self, state):
self.board = state
self.size = len(state)
self.possible = dict()
for coord in self.empty():
self.possible[coord] = {guess for guess in range(1, 10) if self.valid_move(coord,guess)}

def update(self, coord, value):
""" updates self.board and self.possible """
self.board[coord[0]][coord[1]] = value
for coord in self.row(coord)|self.col(coord)|self.square(coord):

def q_update(self, coord, value):
self.board[coord[0]][coord[1]] = value

def check(self, coord):
""" what is coord's value """
return self.board[coord[0]][coord[1]]

def row_vals(self, row):
""" values for each  square in row """
return self.board[row]

def col_vals(self, col):
""" values for each  square in col """
return [self.board[i][col] for i in range(self.size)]

def square_vals(self, coord):
""" values for each  square in box """
x, y = coord[0]//3*3, coord[1]//3*3
return self.board[x + 0][y:y + 3] + self.board[x + 1][y:y + 3] + self.board[x + 2][y:y + 3]

def row(self, coord):
""" coords where row is empty """
return {(coord[0], col) for col in range(self.size)
if self.check((coord[0], col)) == 0 and (coord[0], col) != coord}

def col(self, coord):
""" coords where col is empty """
return {(row, coord[1]) for row in range(self.size)
if self.check((row, coord[1])) == 0 and (row, coord[1]) != coord}

def square(self, coord):
""" coords where box is empty """
x, y = coord[0]//3*3, coord[1]//3*3
return {(row, col) for row in range(x, x + 3) for col in range(y, y + 3)
if self.check((row, col)) == 0 and (row, col) != coord}

def empty(self):
""" coords where board is empty """
return [(row, col) for row in range(self.size) for col in range(self.size)
if self.check((row, col)) == 0]

def valid_move(self, coord, value):
""" if a value at a coord is valid? """
return (self.check(coord) == 0 and value not in self.row_vals(coord[0])
and value not in self.col_vals(coord[1]) and value not in self.square_vals(coord))

def valid_moves(self, coord):
""" all valid moves for a coord """
return set(range(10)).difference((self.row_vals(coord[0]) + self.col_vals(coord[1]) + self.square_vals(coord)))

def valid_board(self):
""" is board solved? """
for row, col in product(range(self.size), range(self.size)):
value = self.board[row][col]
self.board[row][col] = 0
if not self.valid_move((row, col), value):
return False
self.board[row][col] = value
return True

def __repr__(self):
return "".join(' '.join(str(row)[1:-1:3]) + '\n' for row in self.board)

def solve(board):
changes, change_num, i = 1, 0, 0
while changes != 0:
changes = 0
for coord in board.empty():
if len(board.possible[coord]) == 1:
board.update(coord, list(board.possible[coord])[0])
changes -= 1
change_num += 1
else:
for value in board.possible[coord]:
if not all(({1 for square in board.row(coord) if value in board.possible[square]},
{1 for square in board.col(coord) if value in board.possible[square]},
{1 for square in board.square(coord) if value in board.possible[square]})):

board.update(coord, value)
changes -= 1
change_num += 1
break
print(change_num)
empty, possible = board.empty(), dict()
while i < len(empty):
possible[empty[i]] = board.valid_moves(empty[i])
if len(possible[empty[i]]):
board.q_update(empty[i], min(possible[empty[i]]))
change_num += 1
else:
while len(possible[empty[i - 1]]) == 1:
i -= 1
board.q_update(empty[i], 0)
i -= 1
change_num += 1
possible[empty[i]].remove(min(possible[empty[i]]))
board.q_update(empty[i], min(possible[empty[i]]))
i += 1
print(board)
print(change_num)

t1=time()
trial = board([
[3, 0, 0, 0, 0, 7, 0, 0, 9],
[0, 0, 8, 0, 0, 0, 5, 0, 7],
[2, 7, 4, 0, 8, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 4],
[0, 0, 7, 4, 0, 3, 1, 0, 0],
[5, 0, 0, 0, 7, 0, 0, 0, 0],
[0, 0, 0, 0, 6, 0, 4, 9, 8],
[4, 0, 9, 0, 0, 0, 3, 0, 0],
[1, 0, 0, 8, 0, 0, 0, 0, 0]
])
print(trial)
solve(trial)
print(1000*(time()-t1))
print(trial.valid_board())


Numpy:

from time import time
from itertools import product
import numpy as np

class board:
def __init__(self, state):
self.board = np.asarray(state)
self.size = len(state)
self.vals = set(range(self.size+1))
self.possible = dict()
for coord in self.empty():
self.possible[coord] = self.valid_moves(coord)

def update(self, coord, value):
""" updates self.board and self.possible """
self.board[coord] = value
for coord in self.row(coord) | self.col(coord) | self.square(coord):

def square_vals(self, coord):
""" values for each square in box """
x, y = coord[0]//3*3, coord[1]//3*3
return self.board[x:x+3, y:y+3]

def row(self, coord):
""" coords where row is empty """
#return list(zip(*(self.board[coord[0]] == 0).nonzero()))
return {(coord[0], col) for col in range(self.size)
if self.board[(coord[0], col)] == 0 and (coord[0], col) != coord}

def col(self, coord):
""" coords where col is empty """
return {(row, coord[1]) for row in range(self.size)
if self.board[(row, coord[1])] == 0 and (row, coord[1]) != coord}

def square(self, coord):
""" coords where box is empty """
x, y = coord[0]//3*3, coord[1]//3*3
return {(row, col) for row in range(x, x + 3) for col in range(y, y + 3)
if self.board[(row, col)] == 0 and (row, col) != coord}

def empty(self):
""" coords where board is empty """
return list(map(tuple, np.transpose(np.nonzero((self.board == 0)))))

def valid_move(self, coord, value):
""" if a value at a coord is valid? """
return (self.board[coord] == 0 and value not in self.board[coord[0]]
and value not in self.board[:, coord[1]] and value not in self.square_vals(coord))

def valid_moves(self, coord):
""" all valid moves for a coord """
return self.vals.difference(np.concatenate(
(self.board[coord[0]], self.board[:, coord[1]], self.square_vals(coord).flatten())))

def valid_board(self):
""" is board solved? """
for row, col in product(range(self.size), range(self.size)):
value = self.board[(row, col)]
self.board[(row, col)] = 0
if not self.valid_move((row, col), value):
return False
self.board[(row, col)] = value

return True
def __repr__(self):
return "".join(''.join(str(row)[1:-1]) + '\n' for row in self.board)

def solve(board):
changes, change_num, i = 1, 0, 0
while changes != 0:
changes = 0
for coord in board.empty():
if len(board.possible[coord]) == 1:
board.update(coord, list(board.possible[coord])[0])
changes -= 1
change_num += 1
else:
for value in board.possible[coord]:
if not all(({1 for square in board.row(coord) if value in board.possible[square]},
{1 for square in board.col(coord) if value in board.possible[square]},
{1 for square in board.square(coord) if value in board.possible[square]})):
board.update(coord, value)
changes += 1
change_num += 1
break
print(change_num)
empty, possible = board.empty(), dict()
while i < len(empty):
possible[empty[i]] = board.valid_moves(empty[i])

if len(possible[empty[i]]):
board.board[empty[i]] = min(possible[empty[i]])
change_num += 1
else:
while len(possible[empty[i - 1]]) == 1:
i -= 1
board.board[empty[i]] = 0
i -= 1
change_num += 1
possible[empty[i]].remove(min(possible[empty[i]]))
board.board[empty[i]] = min(possible[empty[i]])
i += 1
print(board)
print(change_num)

t1 = time()
trial = board([
[3, 0, 0, 0, 0, 7, 0, 0, 9],
[0, 0, 8, 0, 0, 0, 5, 0, 7],
[2, 7, 4, 0, 8, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 0, 4],
[0, 0, 7, 4, 0, 3, 1, 0, 0],
[5, 0, 0, 0, 7, 0, 0, 0, 0],
[0, 0, 0, 0, 6, 0, 4, 9, 8],
[4, 0, 9, 0, 0, 0, 3, 0, 0],
[1, 0, 0, 8, 0, 0, 0, 0, 0],
])
print(trial)
solve(trial)
print(1000*(time() - t1))
print(trial.valid_board())

• Some guesses as to why numpy is slower: you're using very little of numpy actual features, such as vector-wise addition. Most operations on self.board are still single element. For the few where there is some vector-wise operation, the array is really small to be efficient: 9x9 is very small. If you have a 900000x900000 board, you might see some speed up. Add to that conversions between numpy arrays and tuples or lists, and you have overhead going from numpy to plain Python and vice versa. In short: use numpy when it matters, not because it may be faster (for that, try Cython instead).
– user86624
Aug 2, 2016 at 10:43
• I was hoping that the faster element access would be worth it, is there any way you can think of that would reduce conversion/overhead? Aug 2, 2016 at 12:21
• Is there a way I could reformat the numpy brute force guesser to work on a bunch of boards in parallel? Aug 3, 2016 at 12:59
• I was wondering whether you measure the time including imports or not because importing numpy could add that extra few ms Dec 15, 2017 at 21:38
• I don't think that is the issue. My guess is that I was just not using the features that make ndarrays fast Dec 15, 2017 at 22:00

        self.possible[coord] = {guess for guess in range(1, 10) if self.valid_move(coord,guess)}

Further down in solve() you have some one-liners that should stay that way, to clearly contrast row & col.