Почему переводчик Sudoku медленнее, чем оригинал?

Question

Я переписал свой Java Sudoku solver в python. Все работает, однако решение занимает до 2 минут, в то время как идентичная головоломка занимает всего несколько секунд на Java. Также итерации должны быть равны одному и тому же номеру. Я что-то упускаю?

import numpy as np 
def solve_recursive(puzzle, pos): 
     if(pos == 81): 
      print puzzle 
      return True 
     if(puzzle[pos] != 0): 
      if (not solve_recursive(puzzle, pos+1)): 
       return False 
      else: 
       return True 

     row = np.copy(puzzle[pos//9*9:pos//9*9+9]) 
     col = np.copy(puzzle[pos%9::9]) 
     short = (pos%9)//3*3 + pos//27*27 
     square = np.concatenate((puzzle[short:short+3],puzzle[short+9:short+12],puzzle[short+18:short+21])) 

     for i in range(1,10): 
      puzzle[pos] = i 
      if(i not in row and i not in col and i not in square and solve_recursive(puzzle, pos+1)): 
       return True 

     puzzle[pos] = 0 
     return False 
puzzle = np.array([[0,0,0,0,0,0,0,8,3], 
       [0,2,0,1,0,0,0,0,0], 
       [0,0,0,0,0,0,0,4,0], 
       [0,0,0,6,1,0,2,0,0], 
       [8,0,0,0,0,0,9,0,0], 
       [0,0,4,0,0,0,0,0,0], 
       [0,6,0,3,0,0,5,0,0], 
       [1,0,0,0,0,0,0,7,0], 
       [0,0,0,0,0,8,0,0,0]]) 
solve_recursive(puzzle.ravel(), 0) 

EDIT:

Как было предложено @hpaulj я переработан код для работы с numpy's 2D массивов:

import numpy as np 
def solve_recursive(puzzle, pos): 
     if pos == (0,9): 
      print puzzle 
      raise Exception("Solution") 
     if(puzzle[pos] != 0): 
      if(pos[0] == 8): 
       solve_recursive(puzzle, (0,pos[1]+1)) 
       return 
      elif pos[0] < 8: 
       solve_recursive(puzzle, (pos[0]+1, pos[1])) 
       return 

     for i in range(1,10): 
      if(i not in puzzle[pos[0]] and i not in puzzle[:,pos[1]] and i not in puzzle[pos[0]//3*3:pos[0]//3*3+3,pos[1]//3*3:pos[1]//3*3+3]): 
       puzzle[pos] = i 
       if(pos[0] == 8): 
        solve_recursive(puzzle, (0,pos[1]+1)) 
       elif pos[0] < 8: 
        solve_recursive(puzzle, (pos[0]+1, pos[1])) 
     puzzle[pos] = 0 
puzzle = np.array([[0,0,0,0,0,0,0,8,3], 
      [0,2,0,1,0,0,0,0,0], 
      [0,0,0,0,0,0,0,4,0], 
      [0,0,0,6,1,0,2,0,0], 
      [8,0,0,0,0,0,9,0,0], 
      [0,0,4,0,0,0,0,0,0], 
      [0,6,0,3,0,0,5,0,0], 
      [1,0,0,0,0,0,0,7,0], 
      [0,0,0,0,0,8,0,0,0]]) 
solve_recursive(puzzle, (0,0)) 

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

Answer 1

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

Остановка на pos==46 приводит к 1190 звонкам с небольшой видимой задержкой. Но для 47 счет 416621, с минутой или более бегом.

Предполагая, что он делает какое-то рекурсивный поиск, проблема была квантовый скачок в сложности между 46 и 47.

Да, Python как интерпретируемый язык будет работать медленнее, чем Java. Возможные решения включают выяснение причин такого рода переходов в рекурсивных вызовах. Или улучшить скорость каждого вызова.

Вы установили массив 9x9 numpy, но затем немедленно раритете его. Сама функция затем рассматривает плату как список из 81 значений. Это означает, что выбор строк и столбцов и подматриц намного сложнее, чем если бы массив был еще 2d. По сути, массив - это просто список.

Я могу представить два способа ускорения вызовов. Один из них заключается в том, чтобы перекодировать его для использования списка. Для небольших массивов и итеративных действий списки имеют меньше накладных расходов, чем массивы, поэтому часто быстрее. Альтернатива заключается в том, чтобы закодировать его, чтобы действительно использовать 2d-структуру массива. numpy решения хороши, только если они позволяют numpy использовать скомпилированный код для выполнения большинства действий. Итерация по массиву происходит медленно.

==================

Изменения функции так, что она работает с плоским списком вместо распущенного массива, работает гораздо быстрее. Для max pos 47, он работает в течение 15 секунд по сравнению с 1 м 15 с для вашего оригинала (тот же счетчик и счетчик итераций).

Я очищаю версию массива 2d numpy, но не делаю ее быстрее.

Чистая версия списка также является хорошим кандидатом для быстрого запуска на pypy.

Часть кода, который работает с 2d массив

r,c = np.unravel_index(pos, (9,9))    
    if(puzzle[r,c] != 0): 
     return solve_numpy(puzzle, pos+1) 
    row = puzzle[r,:].copy() 
    col = puzzle[:,c].copy() 
    r1, c1 = 3*(r//3), 3*(c//3) 
    square = puzzle[r1:r1+3, c1:c1+3].flatten() 
    for i in range(1,10): 
     puzzle[r,c] = i 
     if(i not in row and i not in col and i not in square): 
      if solve_numpy(puzzle, pos+1): 
       return True 
    puzzle[r,c] = 0 

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

версия list не выглядит сильно отличается от оригинала, но намного быстрее:

row = puzzle[pos//9*9:pos//9*9+9] 
    col = puzzle[pos%9::9] 
    short = (pos%9)//3*3 + pos//27*27 
    square = puzzle[short:short+3] + \ 
      puzzle[short+9:short+12] + \ 
      puzzle[short+18:short+21] 

http://norvig.com/sudoku.html обсуждает методы решения судоку, с питоном - эксперт AI.

С помощью этого решателя Norvig ваше решение сетки занимает 0.01 сек. Информация хранится в основном в словарях. Ваш случай прост, чем можно решить с помощью его двух основных стратегий назначения. Без поиска решение выполняется очень быстро.