Изменен поиск судоку на O (1) с O (n) с использованием простых чисел, но при этом не наблюдается значительного ускорения в коде

Question

Я получил код для решения судоку с этого канала на Youtube под названием ComputerPhile. Алгоритм был прост, но я чувствовал, что проверка, может ли число быть в одном месте, может быть сделана быстрее. Код из видео выполняет линейный поиск по вертикальной, горизонтальной осям и соответствующей сетке 3х3.

Я изменил «возможную» проверку, чтобы использовать произведение простых чисел с целью изменения возможной проверки () с O (n) на O (1). Однако я не увидел существенного улучшения времени в моем коде.

Так что, очевидно, моя интуиция алгоритмической сложности c неверна, но было бы здорово, если бы кто-то мог указать, где моя интуиция была выключена.

Вход одинаков для обоих. Я сделал кеширование основных продуктов, но я думаю, что все здесь кошерно, так как я только синхронизирую функцию solve ().

Вот код из видео.

import numpy as np

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

def possible(y,x,n): 
    global grid

    """ linear time algorithm below """

    for i in range(0,9):
        if grid[y][i]==n: 
            return False 
    for i in range(0,9):
        if grid[i][x]==n: 
            return False
    x0 = (x//3)*3 
    y0 = (y//3)*3 
    for i in range(0,3): 
        for j in range(0,3): 
            if grid[y0+i][x0+j] ==n: 
                return False
    return True

def solve(): 
    global grid
    for y in range(9): 
        for x in range(9):
            if grid[y][x] ==0: 
                for n in range(1,10): 
                    if possible(y,x,n):
                        grid[y][x] = n 
                        solve()
                        grid[y][x] = 0
                return
    print(np.matrix(grid))

import time 
t1 = time.time()
solve()
print(time.time() - t1)
#output of 0.00691604614258

измененный код ниже, используя простые числа, чтобы проверить, возможно ли добавить число

import numpy as np 

grid = [
    [7,8,0,4,0,0,1,2,0],
    [6,0,0,0,7,5,0,0,9],
    [0,0,0,6,0,1,0,7,8],
    [0,0,7,0,4,0,2,6,0],
    [0,0,1,0,5,0,9,3,0],
    [9,0,4,0,6,0,0,0,5],
    [0,7,0,3,0,0,0,1,2],
    [1,2,0,0,0,7,4,0,0],
    [0,4,9,2,0,6,0,0,7]
]
primes = [3,5,7,11,13,17,19,23,29]

p = 1
for i in primes: 
    p = p*i

total = p  #3234846615


prime_map = dict(zip(primes,range(1,10)))
int_map = dict(zip(range(1,10), primes))

grid_map = {} 
for i in range (9): 
    for j in range(9): 
        grid_map[(j//3, i//3)] = total

vertical_map = dict(zip(range(0,9),[total]*9))

horizontal_map = dict(zip(range(0,9),[total]*9))


def new_possible(y,x,n):
    global grid_map 
    global grid 
    global vertical_map 
    global horizontal_map 

    """attempted O(1) algorithm here"""

    if vertical_map[x]%n!=0: 
        return False 
    if horizontal_map[y]%n!=0: 
        return False 
    x0 = (x//3)
    y0 = (y//3)
    if grid_map[(y0,x0)]%n!=0: 
        return False
    return True 

def initial_update(): 
    global grid_map 
    global grid 
    global vertical_map 
    global horizontal_map
    global int_map
    for y in range(9): 
        for x in range(9): 
            num = grid[y][x] 
            if num!=0:
                vertical_map[x] = vertical_map[x] // int_map[num]
                horizontal_map[y] = horizontal_map[y] //int_map[num]
                grid_map[(y//3, x//3)] = grid_map[(y//3, x//3)] // int_map[num]
initial_update()

def new_solve(): 
    global grid_map 
    global grid 
    global vertical_map 
    global horizontal_map
    global int_map

    for y in range(9): 
        for x in range(9):
            if grid[y][x] ==0: 
                for n in range(1,10): 
                    if new_possible(y,x,int_map[n]):
                        grid[y][x] = n  
                        vertical_map[x] = vertical_map[x]//int_map[n]
                        horizontal_map[y] = horizontal_map[y]//int_map[n]
                        grid_map[((y//3),(x//3))] = grid_map[((y//3),(x//3))]  //  int_map[n]
                        new_solve()
                        grid[y][x] = 0
                        vertical_map[x] = vertical_map[x]*int_map[n]
                        horizontal_map[y] = horizontal_map[y]*int_map[n]
                        grid_map[((y//3),(x//3))] = grid_map[((y//3),(x//3))] * int_map[n]
                return
    print(np.matrix(grid))

import time
t1 = time.time()
new_solve()
print(time.time() - t1)
# output of 0.00550096549988

Answer 1

Большую часть времени, кажется, проводят в циклах и рекурсии. Используя numpy и некоторую другую оптимизацию, я не смог бы добиться лучшего сокращения времени, чем 50%, без изменения основного цикла / рекурсии. Я бы посоветовал вам сосредоточиться на поиске способа сокращения глубины рекурсии, поскольку ускорение проверки достоверности принесет вам лишь небольшие улучшения.

Например, в этой версии для каждой позиции используется маска, которая идентифицирует все другие позиции, которые «связаны» с ним (то есть та же строка, тот же столбец, тот же блок). Это обеспечивает очень быстрый способ узнать, конфликтует ли число с какой-либо данной позицией.

b      = np.arange(81).reshape((9,9))
rows   = b//9
cols   = b%9 
blocks = (b//9//3)+3*(b%9//3)
mask   = (rows[:,:,None,None]==rows)*1 \
       + (cols[:,:,None,None]==cols)*1 \
       + (blocks[:,:,None,None]==blocks)*1
mask   = mask > 0

def solve2(grid):
    for y in range(9): 
        for x in range(9):
            if grid[y][x] ==0: 
                for n in range(1,10): 
                    if np.any(grid[mask[y,x]]==n): continue
                    grid[y][x] = n
                    if solve2(grid): return True
                    grid[y][x] = 0
                return False
    print(grid)
    return True

Я также добавил логическое возвращаемое значение, чтобы остановить поиск, когда решение найдено.