6
\$\begingroup\$

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())
\$\endgroup\$
  • 3
    \$\begingroup\$ 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). \$\endgroup\$ – user86624 Aug 2 '16 at 10:43
  • \$\begingroup\$ 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? \$\endgroup\$ – Oscar Smith Aug 2 '16 at 12:21
  • \$\begingroup\$ Is there a way I could reformat the numpy brute force guesser to work on a bunch of boards in parallel? \$\endgroup\$ – Oscar Smith Aug 3 '16 at 12:59
  • \$\begingroup\$ I was wondering whether you measure the time including imports or not because importing numpy could add that extra few ms \$\endgroup\$ – 13ros27 Dec 15 '17 at 21:38
  • \$\begingroup\$ I don't think that is the issue. My guess is that I was just not using the features that make ndarrays fast \$\endgroup\$ – Oscar Smith Dec 15 '17 at 22:00
1
\$\begingroup\$
        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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.