Действующее судоку: как уменьшить время выполнения - PullRequest
Новая
       104

Действующее судоку: как уменьшить время выполнения

1 голос
/ 02 мая 2020

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

  1. Каждая строка должна содержать цифры 1-9 без повторения.

  2. Каждый столбец должен содержать цифры 1- 9 без повторений.

  3. В каждом из 9 вложенных блоков 3x3 сетки должны содержаться цифры 1-9 без повторения.

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

def isValidSudoku(self, boards: List[List[str]]) -> bool:
    r = {}
    a = {}
    for i in range(len(boards)):
        c = {}
        for j in range(len(boards[i])):
            if boards[i][j] != '.':
                x,y = r.get(boards[i][j]+f'{j}',0),c.get(boards[i][j],0)
                u,v = (i+3)//3,(j+3)//3
                z = a.get(boards[i][j]+f'{u}{v}',0)
                if (x==0 and y==0 and z==0):
                    r[boards[i][j]+f'{j}'] = x+1
                    c[boards[i][j]] = y+1
                    a[boards[i][j]+f'{u}{v}'] = z+1
                else:
                    return False
    return True

1 Ответ

0 голосов
/ 02 мая 2020

Простая оптимизация задания без переосмысления вашего алгоритма сильно ограничивает вашу общую эффективность. Когда вы делаете выбор, вам обычно требуется много времени, прежде чем вы обнаружите противоречие.

Вместо представления «Вот значения, которые я выяснил», попробуйте представить «Вот значения, которые у меня есть». осталось попробовать в каждом месте. " И теперь ваша основная задача: «Устранить это значение с этого места». (Помните, что уменьшение его до 1 приводит к исключению значения из всех его одноранговых узлов, потенциально рекурсивно.)

Назначение теперь «Удалите все значения, кроме этого, с этого места».

И теперь ваша основная операция поиска: «Найти квадрат с наименьшим количеством оставшихся возможностей> 1. Попробуйте каждую возможность по очереди».

Это может показаться тяжелым. Но немедленное распространение ограничений приводит к очень быстрому обнаружению ограничений для остальной части решения, что намного быстрее, чем необходимость экспоненциального количества рассуждений, прежде чем найти логическое противоречие в вашем частичном решении.

I Рекомендую сделать это самостоятельно. Но https://norvig.com/sudoku.html имеет полный рабочий код, который вы можете посмотреть при необходимости.

...