Sudoku Solution Using Multiprocessing

Question

I tried sudoku solution using backtracking, but it was taking a lot time around 12sec to give output. I tried to implement a multiprocessing technique but it's taking lot more time than that of backtracking. I never ran it completely it's too slow. Please suggest what am I missing? Even better if someone can also tell me how to run this through my GPU. (using CUDA).

import concurrent.futures
import copy

A = [[0]*9 for _ in range(9)]
A[0][6] = 2
A[1][1] = 8
A[1][5] = 7
A[1][7] = 9
A[2][0] = 6
A[2][2] = 2
A[2][6] = 5
A[3][1] = 7
A[3][4] = 6
A[4][3] = 9
A[4][5] = 1
A[5][4] = 2
A[5][7] = 4
A[6][2] = 5
A[6][6] = 6
A[6][8] = 3
A[7][1] = 9
A[7][3] = 4
A[7][7] = 7
A[8][2] = 6

Boards = [A]

L = []
for i in range(9):
    for j in range(9):
        if A[i][j] == 0:
            L.append([i,j])
            
def RC_Check(A,Value,N):
    global L
    i,j = L[N]
    
    for x in range(9):
        if A[x][j] == Value:
            return False
        if A[i][x] == Value:
            return False
    return True

def Square_Check(A,Value,N):
    global L
    i,j = L[N]
    
    X, Y = int(i/3)*3,int(j/3)*3
    for x in range(X,X+3):
        for y in range(Y,Y+3):
            if A[x][y] == Value:
                return False
    return True

def New_Boards(Board,N):
    global L
    i,j = L[N]

    Boards = []
    with concurrent.futures.ProcessPoolExecutor() as executor:
        RC_Process = executor.map(RC_Check,[Board]*10,list(range(1,10)),[N]*10)
        Square_Process = executor.map(Square_Check,[Board]*10,list(range(1,10)),[N]*10)

        for Value, (RC_Process, Square_Process) in enumerate(zip(RC_Process,Square_Process)):
            if RC_Process and Square_Process:
                Board[i][j] = Value+1
                Boards.append(copy.deepcopy(Board))

    return Boards

def Solve_Boards(Boards,N):
    Results = []
    with concurrent.futures.ProcessPoolExecutor() as executor:
        Process = executor.map(New_Boards,Boards,[N]*len(Boards))

        for new_boards in Process:
            if len(new_boards):
                Results.extend(new_boards)

    return Results

if __name__ == "__main__":
    N = 0
    while N < len(L):
        Boards = Solve_Boards(Boards,N)
        N+=1
        print(len(Boards),N)
print(Boards)

Answer 1

Multi processing is NOT a silver bullet. Backtracking is pretty more efficient than exhaustive search parallelly in most cases. I tried running this code on my PC which has 32 cores 64 threads, but it takes long time.

And you look like to want to use GPGPU to solve this problem, but i doesn't suit, Because state of board depends on previous state, so can't split calculation efficiently.