使用多处理的数独解决方案

Question

我尝试了使用回溯的数独解决方案，但输出结果需要大约 12 秒的时间。我试图实现一种多处理技术，但它比回溯要花费更多的时间。我从来没有运行它完全是它太慢了。请建议我错过了什么？如果有人还可以告诉我如何通过我的 GPU 运行就更好了。（使用 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

多重处理不是灵丹妙药。在大多数情况下，回溯比并行穷举搜索更有效。我在我的 32 核 64 线程的 PC 上尝试了运行这段代码，但是需要很长时间。

而且你看起来想用GPGPU来解决这个问题，但我不适合，因为棋盘的状态取决于之前的状态，所以不能有效地拆分计算。

使用多处理的数独解决方案

Sudoku Solution Using Multiprocessing

sudoku

backtracking

python-multiprocessing