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())

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.