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())
self.boardare 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). \$\endgroup\$ – user86624 Aug 2 '16 at 10:43ndarrays fast \$\endgroup\$ – Oscar Smith Dec 15 '17 at 22:00