0
\$\begingroup\$

I can't improve the performance of the following Sudoku Solver backtracking solution. I know there are 3 loops here and they probably cause slow performance but I can't find a better/more efficient way.

I tried to isolate "board" from mutation but it hasn't changed the performance. I also tried to use list comprehension for the top 2 "for" loops (i.e. only loop through rows and columns with zeros), tried to find coordinates of all zeros, and then use a single loop to go through them - hasn't helped.

I think I'm doing something fundamentally wrong here with recursion - any advice or recommendation on how to make the solution faster?

def box(board,row,column):
    start_col = column - (column % 3)
    finish_col = start_col + 3
    start_row = row - (row % 3)
    finish_row = start_row + 3
    return [y for x in board[start_row:finish_row] for y in x[start_col:finish_col]]

def possible_values(board,row,column):
    values = {1,2,3,4,5,6,7,8,9}
    col_values = [v[column] for v in board]
    row_values = board[row]
    box_values = box(board, row, column)
    return (values - set(row_values + col_values + box_values))

def solve(board, i_row = 0, i_col = 0):
    for rn in range(i_row,len(board)):
        if rn != i_row: i_col = 0
        for cn in range(i_col,len(board)):
            if board[rn][cn] == 0:
                options = possible_values(board, rn, cn)
                for board[rn][cn] in options:
                    if solve(board, rn, cn): 
                        return board
                    board[rn][cn] = 0
                #if no options left for the cell, go to previous cell and try next option
                return False
    #if no zeros left on the board, problem is solved
    return True

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

solve(problem)
\$\endgroup\$
3
  • \$\begingroup\$ See my answer at codereview.stackexchange.com/questions/268007/… \$\endgroup\$
    – coderodde
    Jul 27 at 15:13
  • \$\begingroup\$ @coderodde thanks, this is useful. I tested your solution and another solution from a comment above in that thread - although they're faster than mine, they are both not fast enough to pass Codewars's kata tests without timeout (codewars.com/kata/55171d87236c880cea0004c6/train/python). I conclude Codewar's timeout is too restrictive so backtracking solution will not work there (despite the fact the tasks asks for it!) \$\endgroup\$
    – profarvin
    Jul 27 at 16:09
  • 1
    \$\begingroup\$ Processing the squares in order (e.g., top-left to bottom-right) is not an efficient way to search the solution space. It is more efficient to find squares with the fewest possibilities and do them first. In a best case, you find one that only has 1 possibility. Pick it and adjust the possible values for that row, column, and square. If the minimum has more that one possibility, then pick one and try it, If it doesn't work, try the others. If none work, backtrack like you do now. Lather, rinse, repeat. \$\endgroup\$
    – RootTwo
    Jul 27 at 23:52

1 Answer 1

1
\$\begingroup\$

Code with significantly improved performance (thanks to @RootTwo for the hint). It's not ideal but it passes the required performance tests:

def solve(board, i_row = 0, i_col = 0):
    cells_to_solve = [((rn, cn), possible_values(board,rn,cn)) for rn in range(len(board)) for cn in range(len(board)) if board[rn][cn] == 0]
    if not cells_to_solve: return True
    
    min_n_of_values = min([len(x[1]) for x in cells_to_solve])
    if min_n_of_values == 0: return False
    
    best_cells_to_try = [((rn,cn),options) for ((rn,cn),options) in cells_to_solve if len(options) == min_n_of_values]
    
    for ((rn,cn),options) in best_cells_to_try:
        for board[rn][cn] in options:
            if solve(board, rn, cn): 
                return board
            board[rn][cn] = 0
        return False
\$\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.