Sudoku elimination strategy

To make this elimination strategy efficient, you would need to have a data structure that keeps track of the neighbours as you make your moves. Re-computing them for every position every time is going to slow things down rather than improve performance.

Such a structure could be a set of non-conflicting numbers that remain available at each position after making a move or it could be the conflicting numbers to be excluded instead. You also need to make updating this structure as efficient as possible when you make a move or take it back. This can be done by creating a second structure that maps each position to the positions that need to be updated when a number is placed there.

In addition to that, since each position can conflict in 3 dimensions (vertical, horizontal and blocks), you need 3 distinct groups to handle addition/subtraction of neighbours in the sets. So each number placed at a given position has to invalidate other positions on a group basis.

Here is a small version of sudoku solver that uses this exclusion approach:

def shortSudokuSolve(board):  # expects a list of lists as the board
    size    = len(board)
    block   = int(size**0.5)
    board   = [n for row in board for n in row ]      
    span    = { (n,p): { (g,n)  for g in (n>0)*[p//size, size+p%size,
                                 2*size+p%size//block+p//size//block*block] }
                for p in range(size*size) for n in range(size+1) }
    empties = [i for i,n in enumerate(board) if n==0 ]
    used    = set().union(*(span[n,p] for p,n in enumerate(board) if n))
    empty   = 0
    while empty>=0 and empty<len(empties):       
        pos        = empties[empty]
        used      -= span[board[pos],pos]
        board[pos] = next((n for n in range(board[pos]+1,size+1) 
                          if not span[n,pos]&used),0)
        used      |= span[board[pos],pos]
        empty     += 1 if board[pos] else -1            
    return [board[r:r+size] for r in range(0,size*size,size)]

Output:

test =  [ [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, 6,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]
        ]
solution = shortSudokuSolve(test)
printSudoku(test,solution)

╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗ ╔═══╤═══╤═══╦═══╤═══╤═══╦═══╤═══╤═══╗
║ 8 │   │   ║   │   │   ║   │   │   ║ ║ 8 │ 1 │ 2 ║ 7 │ 5 │ 4 ║ 3 │ 9 │ 6 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 3 ║ 6 │   │   ║   │   │   ║ ║ 9 │ 4 │ 3 ║ 6 │ 8 │ 2 ║ 1 │ 5 │ 7 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 7 │   ║   │ 9 │   ║ 2 │   │   ║ ║ 6 │ 7 │ 5 ║ 3 │ 9 │ 1 ║ 2 │ 8 │ 4 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │ 5 │   ║   │   │ 7 ║   │   │   ║ ║ 1 │ 5 │ 6 ║ 9 │ 3 │ 7 ║ 8 │ 4 │ 2 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║   │ 4 │ 5 ║ 6 │   │   ║ ║ 3 │ 8 │ 9 ║ 2 │ 4 │ 5 ║ 6 │ 7 │ 1 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │   ║ 1 │   │   ║   │ 3 │   ║ ║ 7 │ 2 │ 4 ║ 1 │ 6 │ 8 ║ 9 │ 3 │ 5 ║
╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣ ╠═══╪═══╪═══╬═══╪═══╪═══╬═══╪═══╪═══╣
║   │   │ 1 ║   │   │   ║   │ 6 │ 8 ║ ║ 2 │ 3 │ 1 ║ 4 │ 7 │ 9 ║ 5 │ 6 │ 8 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │   │ 8 ║ 5 │   │   ║   │ 1 │   ║ ║ 4 │ 6 │ 8 ║ 5 │ 2 │ 3 ║ 7 │ 1 │ 9 ║
╟───┼───┼───╫───┼───┼───╫───┼───┼───╢ ╟───┼───┼───╫───┼───┼───╫───┼───┼───╢
║   │ 9 │   ║   │   │   ║ 4 │   │   ║ ║ 5 │ 9 │ 7 ║ 8 │ 1 │ 6 ║ 4 │ 2 │ 3 ║
╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝ ╚═══╧═══╧═══╩═══╧═══╧═══╩═══╧═══╧═══╝

Note that this is merely an illustration of the mechanics, while it will quickly solve 9x9 sudoku puzzles, more subtle exclusion/prioritization of number selections would be needed to handle 16x16 or larger sudokus in a reasonable amount of time.

I do have an optimized version of the solver (too large to share here) that determines empty cell priorities, detects dead ends early (any position with all numbers excluded, groups with fewer options than empty cells), and auto-places single number options. That one can solve 16x16 puzzles in under a second and can handle some 36x36 in about a minute.

Here is the printsudoku function i used for the output:

def niceSudo(board):
    side    = len(board)
    base    = int(side**0.5)
    def expandLine(line):
        return line[0]+line[5:9].join([line[1:5]*(base-1)]*base)+line[9:13]
    line0  = expandLine("╔═══╤═══╦═══╗")
    line1  = expandLine("║ . │ . ║ . ║")
    line2  = expandLine("╟───┼───╫───╢")
    line3  = expandLine("╠═══╪═══╬═══╣")
    line4  = expandLine("╚═══╧═══╩═══╝")

    symbol = " 123456789" if base <= 3 else " ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
    nums   = [ [""]+[symbol[n] for n in row] for row in board ]
    lines  = []
    lines.append(line0)
    for r in range(1,side+1):
        lines.append( "".join(n+s for n,s in zip(nums[r-1],line1.split("."))) )
        lines.append([line2,line3,line4][(r%side==0)+(r%base==0)])
    return lines
        
def printSudoku(*boards):
    print(*(" ".join(ss) for ss in zip(*(niceSudo(b) for b in boards))),sep="\n") 

  

To start, lets try rewriting your existing approach, a bit simpler-

def find_best(grid):
    row_counts = [row.count(0) for row in grid]
    col_counts = [col.count(0) for col in zip(*grid)]

    cells_with_scores = ((row_count + col_count, row_idx, col_idx) 
            for row_count, (row_idx, row)  in zip(row_counts, enumerate(grid))
            for col_count, (col_idx, elem) in zip(col_counts, enumerate(row)) 
            if elem)

    score, row_num, col_num = min(cells_with_scores)
    return row_num, col_num

Note that we're just calculating the count of 0's on each row/col, iterating over every cell, and discarding any that are non-zero. We then get the min tuple, which will be one with the smallest row_count + col_count.

Now, this is of course O(N*M), where N is the number of rows, and M the number of columns. This isn't great, but it is simple, and we can improve on it.

To do so, we need to construct a priority queue / min-heap from the priority/coordinate tuples in cells_with_scores (and switch to lists instead of tuples, for reasons we'll see shortly). We can use the builtin heapq module to do this. Then, we can get the min in O(1) time, after initial construction. However, we'll need to update this queue with the new cell scores after making a move, which means for every cell in the same row or column as the assigned cell, we need to decrement the priority key for that corresponding element in the heap by 1.

You can roll your own to do this, or can make a mapping of row_num -> list of cells_with_scores entries, and same for col_num. Then, iterate this list (skip any non-zero cells), and mutate the corresponding count/row/col list to decrease the count (in place), and restore the heap invariant. You can create a function to use this, or if you're willing to use a private / undocumented (and prone to change) method from heapq, use heapq._siftdown. Either way, once all the keys are decremented and the heap invariant restored, you're ready to get the next min.

All together, this approach will take O((M + N) * log(N * M) time.