Two versions of Sudoku

Question

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):
 self.possible[coord].discard(value)
 def q_update(self, coord, value):
 """ updates self.board """
 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):
 self.possible[coord].discard(value)
 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())

• user86624: 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).
• Oscar Smith: 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?
• Oscar Smith: Is there a way I could reformat the numpy brute force guesser to work on a bunch of boards in parallel?
• 13ros27: I was wondering whether you measure the time including imports or not because importing numpy could add that extra few ms
• Oscar Smith: I don't think that is the issue. My guess is that I was just not using the features that make ndarrays fast

Answer 1

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

Yes, you can write the set comprehension as a one-liner. But please use multiple lines, for clarity.

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

You have a bunch of small simple functions, which helps make the code easy to read.