4
\$\begingroup\$

I made a Sudoku Solver after following some tutorials. Then I made a Sudoku generator and everything works. I also used classes to make it look more organized.

I wanted to know what I can do better to optimize my code.

I would like to make it faster and more readable but not at the cost of performance.

One optimization I can think of is getting all the free spaces (find_empty) at once rather than running it every time.

Here is my code:

'''Sudoku Solver and Generator implemented in Python'''

__author__ = 'Random Coder 59'
__version__ = '1.0.1'
__email__ = 'randomcoder59@gmail.com'

from random import shuffle
import time

board = [
    [8, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 3, 6, 0, 0, 0, 0, 0],
    [0, 7, 0, 0, 9, 0, 2, 0, 0],
    [0, 5, 0, 0, 0, 7, 0, 0, 0],
    [0, 0, 0, 0, 4, 5, 7, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 3, 0],
    [0, 0, 1, 0, 0, 0, 0, 6, 8],
    [0, 0, 8, 5, 0, 0, 0, 1, 0],
    [0, 9, 0, 0, 0, 0, 4, 0, 0]
]

class Sudoku:
    '''Sudoku class for solving and generating boards'''

    @classmethod
    def str_board(cls, board):
        '''Returns a board in string format'''

        str_board = ''
        for y in range(len(board)):
            if y in [3, 6]:
                str_board += '- ' * 11 + '\n'
            for x in range(len(board[y])):
                if x in [3, 6]:
                    str_board += '| '
                if x == 8:
                    str_board += str(board[y][x]) + '\n'
                else:
                    str_board += str(board[y][x]) + ' '
        return str_board

    @classmethod
    def find_empty(cls, board):
        '''Find and returns a empty cell if any, else returns None'''

        for y in range(len(board)):
            for x in range(len(board[0])):
                if board[y][x] == 0:
                    return y, x
        return None

    @classmethod
    def valid(cls, board, num, pos):
        '''Returns if a number is valid on a position on the board'''

        for x in range(len(board[0])):
            if board[pos[0]][x] == num and pos[1] != x:
                return False

        for y in range(len(board)):
            if board[y][pos[1]] == num and pos[0] != y:
                return False

        box_y = (pos[0] // 3) * 3
        box_x = (pos[1] // 3) * 3

        for y in range(box_y, box_y + 3):
            for x in range(box_x, box_x + 3):
                if board[y][x] == num and (y, x) != pos:
                    return False

        return True

    @classmethod
    def solve(cls, board):
        '''Solves a given board and returns the board. Returns False is the board is not solvable'''
        find_result = cls.find_empty(board)
        if not find_result:
            return board
        else:
            y, x = find_result

        for num in range(1, 10):
            if Sudoku.valid(board, num, (y, x)):
                board[y][x] = num
                if Sudoku.solve(board):
                    return board
                board[y][x] = 0
        return False

    @classmethod
    def create_empty(cls, board, number):
        '''Creates empty spaces in board according to number, returns the board'''
        coors = [(y, x) for y in range(9) for x in range(9)]
        shuffle(coors)
        for idx in range(number):
            y, x = coors[idx]
            board[y][x] = 0
        return board

    @classmethod
    def generate_board(cls):
        '''Generates a random Sudoku board and returns it.'''
        numbers = list(range(1, 10))
        board = [[0 for _ in range(9)] for _ in range(9)]
        for y in range(len(board)):
            for x in range(len(board[0])):
                shuffle(numbers)
                for num in numbers:
                    if Sudoku.valid(board, num, (y, x)):
                        board[y][x] = num

                    if Sudoku.solve(board):
                        break

                    board[y][x] = num
        return board

solver = Sudoku()
print('Original board')
print(solver.str_board(board))

t1 = time.time()
solver.solve(board)
t2 = time.time()
print('Solved puzzle')
print(solver.str_board(board))
print(f'Finished in {round(t2 - t1, 3)} seconds')
New contributor
Random_Pythoneer59 is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
0
1
\$\begingroup\$

I am not touching your generate_board. I had actually done similar kinda thing a few months back. Here's the code. It's faster if you exchange speed for memory.

board = [
    [8, 0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 3, 6, 0, 0, 0, 0, 0],
    [0, 7, 0, 0, 9, 0, 2, 0, 0],
    [0, 5, 0, 0, 0, 7, 0, 0, 0],
    [0, 0, 0, 0, 4, 5, 7, 0, 0],
    [0, 0, 0, 1, 0, 0, 0, 3, 0],
    [0, 0, 1, 0, 0, 0, 0, 6, 8],
    [0, 0, 8, 5, 0, 0, 0, 1, 0],
    [0, 9, 0, 0, 0, 0, 4, 0, 0]
]


# This function will decide the least possible value for an empty space, r stands for row index, c for column index
def decide(r, c):
    # As you can see, a and b will decide the native 3/3 square for a particular index
    a, b = r // 3 * 3, c // 3 * 3
    # If a number has index (5, 6) you will get a=3, b=6 this means the 3/3 square extends 
    # over row 3,4,5 and column 6,7,8  
    # After back tracking let's say our value is 5, this loop will check where 6, 7, 8, 9 are fit for being used.
    # If the spot is zero, it just starts from 1 and goes up to 9 until a suitable value if found  
    for i in range(board[r][c]+1, 10):
        for j in range(9):
            # board[r][j] checks whether the number i is there in the row r
            # board[j][c] checks whether the number i is there in the column c
            # board[a+j//3][b+j % 3] try to dry run the values j//3 and j%3 you'll understand. 
            # j//3 will give 0, 0, 0, 1, 1, 1, 2, 2, 2 over the 9 iterations.
            # j%3  will give 0, 1, 2, 0, 1, 2, 0, 1, 2 over the 9 iterations.
            # Let's say you have a=3 and b=6
            # a+j//3 will extend over 3, 3, 3, 4, 4, 4, 5, 5, 5
            # b+j%3 will give        :6, 7, 8, 6, 7, 8, 6, 7, 8
            # Thus we cover the entire 3/3 square, also the row and the column.
            if board[r][j] == i or board[j][c] == i or board[a+j//3][b+j % 3] == i:
                # obviously if any of these is true, the number is not fit 
                break
        else:
            # if a number is found to be fit it is returned immediately
            return i
    # if no solution can be found, zero is returned. This means there has been some mistake with the previous solution, we'll back trace in the solve function and fix thaht.
    return 0


def solve():
    # mutable collects the indices of all the empty spots.
    mutable = [(i, j) for i, row in enumerate(board) for j, element in enumerate(row) if element == 0]
    i = 0
    while i < len(mutable):
        r, c = mutable[i]
        # we send the row and column no. of the empty spot to decide function
        board[r][c] = decide(r, c)
        # If a solution has been found, we just go on, if a zero is returned that means something's been wrong, we backtrace, reduce the value of i by i
        if board[r][c] == 0:
            i -= 1
            continue
        i += 1


def print_board():
    for i in range(len(board)):
        if i % 3 == 0:
            print('-' * 23)
        for j in range(len(board[i])):
            if j != 0 and j % 3 == 0:
                print(' | ', end='')
            print(board[i][j], end=' ')
        print()
    print('-' * 23)


from timeit import timeit
print_board()
time = timeit(solve, number=1)
print_board()
print(f'Finished in {time}s')

This code takes 0.4 seconds to solve the sudoko. Your code took 0.8 seconds on my device. Output:

-----------------------
8 0 0  | 0 0 0  | 0 0 0 
0 0 3  | 6 0 0  | 0 0 0 
0 7 0  | 0 9 0  | 2 0 0 
-----------------------
0 5 0  | 0 0 7  | 0 0 0 
0 0 0  | 0 4 5  | 7 0 0 
0 0 0  | 1 0 0  | 0 3 0 
-----------------------
0 0 1  | 0 0 0  | 0 6 8 
0 0 8  | 5 0 0  | 0 1 0 
0 9 0  | 0 0 0  | 4 0 0 
-----------------------
-----------------------
8 1 2  | 7 5 3  | 6 4 9 
9 4 3  | 6 8 2  | 1 7 5 
6 7 5  | 4 9 1  | 2 8 3 
-----------------------
1 5 4  | 2 3 7  | 8 9 6 
3 6 9  | 8 4 5  | 7 2 1 
2 8 7  | 1 6 9  | 5 3 4 
-----------------------
5 2 1  | 9 7 4  | 3 6 8 
4 3 8  | 5 2 6  | 9 1 7 
7 9 6  | 3 1 8  | 4 5 2 
-----------------------
Finished in 0.4711908s
New contributor
Nothing special is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$
6
  • 4
    \$\begingroup\$ Could you explain your functions? I am compartively now to python. \$\endgroup\$ Sep 14 at 18:36
  • 1
    \$\begingroup\$ ok wait a few minutes, I'll edit the answer. If you don't know about enumerate function, you can google it. Rest of things I'll be explaining in the answer. \$\endgroup\$ Sep 14 at 18:36
  • \$\begingroup\$ I appreciate the effort you took into this and I understood the code now, but my question is what's the point in taking the smallest value possible? How does it help in optimization? \$\endgroup\$ Sep 15 at 3:57
  • \$\begingroup\$ It is a part of back tracking algorithm let's say you test every number from 0 to 9 and make a list of possible ones.... Secondly you go from let's say 5 to 9...so it's faster....now if none of the possibilities work then we conclude that previous empty spot was wrongly filled, we go back and try to fix the previous mistake.... This goes on & on until the board is solved... \$\endgroup\$ Sep 15 at 5:04
  • \$\begingroup\$ Ok now I get it. Thanks! \$\endgroup\$ Sep 15 at 7:37
1
\$\begingroup\$

One optimization I can think of is getting a all the free spaces(find_empty) at once rather than running it everytime.

Things like that would work. There are bigger fish to fry though. The main thing that causes a basic recursive solver like this to sometimes (but not on all inputs) be slow isn't really the implementation details. Of course, they also matter. But the main thing is algorithmic: a basic recursive solver fundamentally spends a lot of time exploring tons of partial solutions that aren't going to be completable, but the solver only detects the conflict very deep in the recursion tree, after spending lots of time on desperately trying to solve the bottom-right cells even though the problem may have been caused by a bad pick in the upper left of the board.

There are some strategies (common to Constraint Programming in general) that you can use to make a more advanced solver:

  1. Propagate the consequences of a choice. In the context of Sudoku, that can mean iteratively checking for Singles (both naked and hidden), both right at the start but also after filling in a cell. There are more advanced propagation techniques, Sudoku can be viewed as three sets of 9 AllDifferent constraints and there are some algorithms related to that, but implementing only iterative Naked Single and Hidden Single detection is already such a huge step up in performance you probably don't need to get so fancy.
  2. Use a better order than left-to-right and top-to-bottom. The order matters: if a cell is impossible to solve due to a bad choice that was made earlier, it's best to detect that conflict ASAP. Any exploration done while that bad choice is on the board, will just be wasted. A common technique to somewhat avoid that effect, is picking an empty cell with with the smallest domain (fewest possible values) first, rather than simple the first empty cell that is found.

Implementing one or both of them would surely help with the cases that are now slow, but not with the cases that are already fast. Unfortunately they would add code and increase the level of complexity, so you can reasonably say that they would hurt readability.

By the way, here is an input that tends to make basic recursive solvers really slow, you can use it to evaluate the effects of implementing the above techniques:

board = [
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,3,0,8,5],
    [0,0,1,0,2,0,0,0,0],
    [0,0,0,5,0,7,0,0,0],
    [0,0,4,0,0,0,1,0,0],
    [0,9,0,0,0,0,0,0,0],
    [5,0,0,0,0,0,0,7,3],
    [0,0,2,0,1,0,0,0,0],
    [0,0,0,0,4,0,0,0,9]
]

Often I would add a performance comparison of a quick and dirty implementation of propagating naked/hidden singles, but I don't have Python installed right now. It is very effective though. The puzzle above may take dozens of seconds to solve with the current solver, and only several milliseconds with a solver that implements naked- and hidden-singles propagation. At least that is what I expect based on my experience with similar solvers.

\$\endgroup\$
1
  • \$\begingroup\$ You can use this online ide but it will most probably be slower. Anyway I understand your point but as I am new to python I dont have much idea of how to implement it. The time you took to type this is very much appreciated but could you post some working code? \$\endgroup\$ Sep 15 at 3:35
1
\$\begingroup\$

In order to squeeze some performance, you could have 9 simple integer sets for different rows, 9 integer sets for different columns, and 9 integer sets for the \$3 \times 3\$ minisquares. Then, when trying to check whether the next digit \$d\$ fits in the solution board cell, all you do is make sure that for that position all corresponding row/column/minisquare sets do not contain the digit. With this optimization I got optimistic results:

class IntSet:
    def __init__(self):
        self.array = [False for i in range(10)]

    def add(self, digit):
        self.array[digit] = True

    def remove(self, digit):
        self.array[digit] = False

    def contains(self, digit):
        return self.array[digit]


class SudokuSolver:
    def __init__(self, board):
        self.board = board
        self.row_set_array = [IntSet() for i in range(9)]
        self.col_set_array = [IntSet() for i in range(9)]
        self.minisquare_set_matrix = [[IntSet() for y in range(3)] for x in range(3)]
        self.solution = [[0 for i in range(9)] for j in range(9)]

        for y in range(9):
            for x in range(9):
                digit = self.board[y][x]
                self.row_set_array[y].add(digit)
                self.col_set_array[x].add(digit)
                self.minisquare_set_matrix[y // 3][x // 3].add(digit)

    def solve(self, x = 0, y = 0):
        if x == 9:
            x = 0
            y += 1

        if y == 9:
            return True

        if self.board[y][x] != 0:
            self.solution[y][x] = self.board[y][x]
            return self.solve(x + 1, y)

        for sign in range(1, 10):
            if not self.col_set_array[x].contains(sign) and not self.row_set_array[y].contains(sign):
                minisquare_x = x // 3
                minisquare_y = y // 3

                if not self.minisquare_set_matrix[minisquare_y][minisquare_x].contains(sign):
                    self.solution[y][x] = sign
                    self.row_set_array[y].add(sign)
                    self.col_set_array[x].add(sign)
                    self.minisquare_set_matrix[minisquare_y][minisquare_x].add(sign)

                    if self.solve(x + 1, y):
                        return True

                    self.row_set_array[y].remove(sign)
                    self.col_set_array[x].remove(sign)
                    self.minisquare_set_matrix[minisquare_y][minisquare_x].remove(sign)

        return False

Typical output

-----------------------
8 0 0  | 0 0 0  | 0 0 0 
0 0 3  | 6 0 0  | 0 0 0 
0 7 0  | 0 9 0  | 2 0 0 
-----------------------
0 5 0  | 0 0 7  | 0 0 0 
0 0 0  | 0 4 5  | 7 0 0 
0 0 0  | 1 0 0  | 0 3 0 
-----------------------
0 0 1  | 0 0 0  | 0 6 8 
0 0 8  | 5 0 0  | 0 1 0 
0 9 0  | 0 0 0  | 4 0 0 
-----------------------
-----------------------
8 1 2  | 7 5 3  | 6 4 9 
9 4 3  | 6 8 2  | 1 7 5 
6 7 5  | 4 9 1  | 2 8 3 
-----------------------
1 5 4  | 2 3 7  | 8 9 6 
3 6 9  | 8 4 5  | 7 2 1 
2 8 7  | 1 6 9  | 5 3 4 
-----------------------
5 2 1  | 9 7 4  | 3 6 8 
4 3 8  | 5 2 6  | 9 1 7 
7 9 6  | 3 1 8  | 4 5 2 
-----------------------
Finished in 0.41106139999999997s
-----------------------
8 0 0  | 0 0 0  | 0 0 0 
0 0 3  | 6 0 0  | 0 0 0 
0 7 0  | 0 9 0  | 2 0 0 
-----------------------
0 5 0  | 0 0 7  | 0 0 0 
0 0 0  | 0 4 5  | 7 0 0 
0 0 0  | 1 0 0  | 0 3 0 
-----------------------
0 0 1  | 0 0 0  | 0 6 8 
0 0 8  | 5 0 0  | 0 1 0 
0 9 0  | 0 0 0  | 4 0 0 
-----------------------
coderodde's output:
-----------------------
8 1 2  | 7 5 3  | 6 4 9 
9 4 3  | 6 8 2  | 1 7 5 
6 7 5  | 4 9 1  | 2 8 3 
-----------------------
1 5 4  | 2 3 7  | 8 9 6 
3 6 9  | 8 4 5  | 7 2 1 
2 8 7  | 1 6 9  | 5 3 4 
-----------------------
5 2 1  | 9 7 4  | 3 6 8 
4 3 8  | 5 2 6  | 9 1 7 
7 9 6  | 3 1 8  | 4 5 2 
-----------------------
Duration 181  milliseconds.

(For entire demonstration code, see this gist.)

\$\endgroup\$

Your Answer

Random_Pythoneer59 is a new contributor. Be nice, and check out our Code of Conduct.

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.